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)

 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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;     }

 다른 정렬 알고리즘 공부하기!!

2017/11/07 - [Study/알고리즘] - 07 정렬 알고리즘 - 힙 정렬 (Heap Sort)

2017/09/29 - [Study/알고리즘] - 06 정렬 알고리즘 - 기수 정렬(Radix Sort)

2017/09/25 - [Study/알고리즘] - 05 정렬 알고리즘 - 병합 정렬 (Merge Sort)

2017/09/21 - [Study/알고리즘] - 04 정렬 알고리즘 - 퀵 정렬 (Quick Sort)

2017/09/15 - [Study/알고리즘] - 02 정렬 알고리즘 - 삽입 정렬 (Insetion Sort)

2017/09/14 - [Study/알고리즘] - 01 정렬 알고리즘 - 선택 정렬(Selection Sort)