버블 정렬(Bubble Sort)

2. 버블정렬

Bubble Sort는 가장 기본적이고 초보적인 Sorting 방법으로써, 서로 인접한 데이터들을 뒤에서부터 자리바꿈하면서 정렬하는 방법이다.

(Selection Sort는 앞에서부터 정렬한다.)

효율성은 떨어지나, 구현이 간단하여 속도가 별로 중요하지 않은 경우에 널리 쓰이는 방법이다.

 

입력자료 :

4

7

3

1

5

8

2

6

1. 4와7을 비교한다. 7이 더 크므로 변화 없다.

-->	4	7	3	1	5	8	2	6
	↑	↑

2. 7과 3을 비교한다. 3이 더 작으므로 바꾼다. 

-->	4	7	3	1	5	8	2	6
		↑	↑

3. 7과 1을 비교한다. 1이 더 작으므로 바꾼다.

-->	4	3	7	1	5	8	2	6
			↑	↑

4. 7과 5를 비교한다. 5가 더 작으므로 바꾼다.

-->	4	3	1	7	5	8	2	6
				↑	↑

입력자료 :

4

7

3

1

5

8

2

6

5. 7과 8을 비교한다. 8이 더 크므로 변화 없다.

-->	4	3	1	5	7	8	2	6
					↑	↑

6. 8과 2을 비교한다. 2가 더 작으므로 바꾼다. 

-->	4	3	1	5	7	8	2	6
						↑	↑

7. 8과 6을 비교한다. 6이 더 작으므로 바꾼다.

-->	4	3	1	5	7	2	8	6
							↑	↑

Pass 1 결과 : 4   3   1   5   7   2   6   8

Pass 1을 거치면 마지막 부분이 완전히 결정되어 더 이상 정렬대상이 되지 않는다. 따라서 마지막 부분을 뺀 나머지 7개의 숫자를 가지고 다시 Bubble Sort를 반복한다. 이 Pass 2 과정이 끝나면 마지막에서 두 번째 부분도 완전히 결정된다. 이런식으로, 정렬대상이 가장 처음의 숫자가 될 때까지 위의 계산을 반복한다.

1  첫번째 레코드와 두번째 레코드를 비교한다. 2  두번째 레코드값이 더 크면 바꾸지 않고 3  두번째 레코드값이 더 작으면 바꾼다. 4  두번째 레코드값과 세번째 레코드값을 비교한다. 5  이를 n번째 레코드까지 반복한다. 6  그러면 제일 큰값이 n번째에 위치하게된다. 7  첫번째 레코드와 두번째 레코드를 비교한다. 8  두번째 레코드값이 더 크면 바꾸지 않고 9  두번째 레코드값이 더 작으면 바꾼다. 10 두번째 레코드값과 세번째 레코드값을 비교한다. 11 이를 n-1번째 레코드까지 반복한다. 12 그러면 그다음으로 큰값이 n-1번째에 위치하게 된다. 13 이를 반복한다.

Sorting Method
     for(i는 n-1에서 1보다 클동안 i--)
         for(j는 0에서 i보다 작을동안 j++)
             if(j번째 레코드가 j+1번째 레코드보다 크면)
                 j번째 레코드와 j+1번째 레코드를 바꾼다.