03 정렬 알고리즘 - 버블 정렬 (Bubble Sort)

버블정렬 (Bubble Sort)

두 인접한 배열요소를 차례대로 검사를 하여 정렬을 하는 방식

 

 

■ 정렬 방식 

1. 배열의 가장 앞에서 인접한 두 개의 요소에 대하여 비교를 한다.

(배열의 첫 번째 요소와 두 번째 요소) 

2. 배열의 다음 인접한 요소(두 번째와 세번째를 비교를 한다.)

3. 배열의 끝까지 반복을 한다. 한 사이클이 끝나면 배열의 맨 끝에는 정렬된 요소 하나가 정렬이 된 채 자리잡는다.

4. 정렬이 된 마지막 요소를 제외한 나머지에 대하여 1,2,3 번 과정을 반복한다.

 

 

정렬이 된 상태

 

비교 원소

 

5

4

3

2

1

최초 정렬이 이루어지지 않은 상태의 배열입니다.

5

4

3

2

1

첫 번째 요소와 두 번째 요소를 비교합니다. 4가 더 작으므로 둘의 위치를 교환합니다.

4

5

3

2

1

다음 인접 두 요소에 대해서도 같은 작업을 합니다. 3이 더 작으므로 교환합니다.

4

3

5

2

1

다음 인접 두 요소에 대해서 반복해주고 2가 더 작으므로 5와 교환합니다.

4

3

2

5

1

1과 5를 교환합니다. 배열의 끝 요소에 도달 했으므로 한 사이클이 종료됩니다.

4

3

2

1

5

한 사이클이 종료되니 5만 자기 자리를 찾아 간 상태입니다. 다시 처음부터 위의 과정을 반복하는데 마지막 4번째 요소가 배열의 마지막 요소가 됩니다.

4

3

2

1

5

첫 번째 요소와 두 번째 요소를 비교합니다. 3이 더 작으므로 교환합니다.

3

4

2

1

5

다음 두 인접 요소에 대해서 비교를 합니다. 2와 4의 위치를 교환합니다.

3

2

4

1

5

다음 두 인접 요소에 대해서 비교를 합니다. 1과 4의 위치를 교환합니다.

3

2

1

4

5

 

4도 제 위치에 자리 잡았습니다. 이런 식으로 나머지 과정에 대해서도 수행을 하면 정렬이 완료가 됩니다.

 

■ 특징

1. 시간 복잡도는 O(n＾2)으로 느린 편입니다.

2. 코드 구현이 간단합니다.

 

■ 소스코드(Source Code)

 

    public int[] Bubble_Sort(int[] data,int num)
    {
        int tmp;
        for(int i=0;i<num-1;i++)
        {
            for(int j=0;j<=num-2-i;j++)
            {
                if(data[j]>data[j+1])
                {
                    tmp=data[j+1];
                    data[j+1] = data[j];
                    data[j] = tmp;
                }
            }
        }
        return data;
    }

 

출처 : https://lktprogrammer.tistory.com/30?category=672214