버블 정렬

[버블 정렬에 대한 개요]

버블 정렬은 0번째 배열을 기준으로 시작하여 자기 오른쪽 배열의 값과 비교한다. 

만약 자신이 더 작다면 변경을 하지 않고 기준을 자기 오른쪽 배열로 바꾼다. (즉, 기준이 0번째 배열에서 1번째 배열로 옮겨진다.)

만약 자신이 더 크다면 옆의 값과 바꾸고 기준을 옮겨진 자기 자신으로 한다. (즉, 기준이 0번째 배열에서 1번째 배열로 옮겨진다.)

위 과정을 반복하여 최대값을 가장 뒤로 밀어낸다.

선택 정렬과 달리 과정이 끝나면 다시 0번째 배열을 기준으로 값을 옮기러 다닌다는 점이 다르다.

(버블 정렬은 끝점이 줄어든다.)

선택 정렬의 시간 복잡도를 계산하자면, 전체 배열의 크기를 n이라 할 때

0번째 배열은 자기 자신을 제외한 모든 값을 비교하므로 (n-1)이 pass 1에서의 복잡도라 할 수 있다.

pass 2 때는 1번째 배열부터 자기 자신을 제외한 이후 값을 비교하는 것이므로 (n-2)이 복잡도가 된다.

위의 과정을 (n-n)이 될 때까지 반복한다.

이를 표현하면 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2이 되므로 O(n^2)이 시간 복잡도가 된다.

시간 복잡도로만 따지면 선택 정렬과 같지만 실제로는 대부분 선택 정렬이 좀 더 빠르다.

선택정렬의 문제점은 값이 이동되는 범위가 자신의 옆 밖에 없다는 점이다.

또한 move가 아닌 swap 방식을 사용하는 정렬이기 때문에 move보다 3배 많은 자료 이동이 발생한다.

(move에 비해 3배의 이동이 일어나는 이유는 t = x, x = y, y = x 형태의 swap이 발생하기 때문이다.)

좌우로 값이 밀리면서 정렬하기 때문에 이미 최종 위치에 있는 값이 이동될 때가 많다.