기초적인 정렬 알고리즘 두번째는 버블정렬에 대하여 소개하겠습니다.
버블정렬(Bubble Sort) -오름차순 기준
버블정렬은 "큰 것들을 미리 뒤로 보낼래요"라고 생각하면 된다. 먼저, A[0~N]배열이
있다 가정해보자. A[N]까지 정렬이 이뤄지기 위해서는 A[0] A[1]비교, A[1] A[2] 비교부터
....A[N-1] A[N]까지의 비교를 통해서 큰 값이 뒤로가는 형태로 정렬이 된다.
만약, A[0]과 A[1]을 비교 후 큰값이 나오는것을 뒤로 보내면된다. 그리고 그 큰값은 A[2]와 비교하고 또 여기서나온 큰값은 N개 까지 이어갈 것 이다. 조금 더 구체적으로 살펴보면,
6개의 정렬이 되지않은 배열이 있다 생각해보자.
A[6] = { 4, 9, 7, 2, 5, 3 };
1회과정..
4 9 7 2 5 3 => 9는 4보다 이미크다. 즉, 자리교환이없다. ( A[0], A[1] 비교 )
4 9 7 2 5 3 => 9는 7보다 크다 즉, 자리교환실행 ( A[1], A[2] 비교 )
4 7 9 2 5 3 => 자리교환 ( A[1], A[2] 자리 교환)
4 7 9 2 5 3 => 9는 2보다 크다. 즉, 자리교환실행 ( A[2], A[3]비교 )
4 7 2 9 5 3 => 자리교환 ( A[2], A[3] 자리 교환)
4 7 2 9 5 3 => 9는 5보다 크다. 즉, 자리교환실행 ( A[3], A[4] 비교 )
4 7 2 5 9 3 => 자리교환( A[3]과 A[4] 자리 교환)
4 7 2 5 9 3 => 9는 3보다 크다. 즉, 자리교환실행 ( A[4], A[5] 비교 )
4 7 2 5 3 9 => 최종결과.
우리가 1회 과정만을 살펴봤을때 간단한 특징이 있다. 바로 맨 끝에 가장 큰 값이 들어가는것이다. 그럼 그 다음은 2번째로 큰수가 맨뒤 앞에 올것이다.
이런식으로 정렬이 진행된다면....
2회 과정 => 4 2 5 3 7 9
3회 과정 => 2 4 3 5 7 9
4회 과정 => 2 3 4 5 7 9
5회 과정 => 2 3 4 5 7 9 >> 정렬이 완성된다.
이 과정들을 보면 가장 큰 값은 N번, N-1번, N-2번 ... 3번 2번까지의 순서로 쌓이게 된다.
(2번에 큰값이 온다는것은 마지막 1번과의 비교가 있었으므로 2번에서 마무리가 됨.)
마지막 과정의 정렬까지 이루어지기 위해서는 에서는 N개, N-1개, N-2의 비교가 필요하고,
그 비교들은 배열의 총 갯수 N개에 비례. 즉, 배열의 갯수에 수행시간이 영향을 받는다는 것을 알 수 있다. 그리고 이 수행시간은 Theta(N제곱)이 되는 것 이다.
하지만 자세히 보면 4회 과정에서는 이미 정렬이 끝낸상태이다. 그럼에도 불구하고 4, 5회 까지의 과정들을 진행한다. 만약에 우리가 이미 정렬이 끝낸상태가 되었을때, 종료하는
방법은 없을까? 물론있다! 단 하나의 과정만 표시하면된다.
바로 흔적을 남기는것이다. 우리가 각 회 과정을 보면 큰값이 뒤로가는 형태, 즉 하나의 값이라도 움직인다면 표시를 해둔다. 어떻게 하느냐? 생각해보면 "아차!" 할 것이다.
하나의 값이라도 움직인다 라는말은 "큰값이 앞에있다" 즉, "정렬을 하는중이다" 라고 생각하면 된다. 정렬이 마무리가 되지 않았기 때문이다. 반대로 정렬이된 상태라면 움직임이
없을것이다. 그럼 우리가 표시를 안하게 되고 그 표시가 안되어있으면
"어? 움직임이 없는걸보니깐 이미 정렬된상태구나!" 라고 생각해두면 훨씬 수월할것이다.
결국 3회의 과정에서 끝나므로 더 효과적인 버블정렬이 완성되는 것이다.
알고리즘을 알아보자!
<tok는 위에서 말했던 이미 정렬이 되었을경우 프로그램을 종료시키는 장치>
▶ 장치를 추가하기 전의 버블정렬 결과
▶ 장치를 추가한 후의 버블정렬 결과
