그렇다면 첫 번째 정렬 방식인 Bubble Sort(버블 정렬)에 대해서 배워보도록 하겠습니다.
버블 정렬을 간략히 말하자면 다음과 같습니다.
서로 인접한 두 원소를 순회하며 검사하여 정렬하는 알고리즘
다음과 같은 예시를 통해 이해를 해 보도록 합시다.
아래에 정렬되지 않은 리스트가 있습니다.
우선 가장 앞에 위치한 두 개의 값을 비교하게 됩니다. 그래서 만약 정렬되어 있지 않다면, 즉 다시 말해서 왼쪽의 값이 오른쪽의 값보다 크다면 두 숫자를 바꿔주게 됩니다.
위 그림에서는 첫 비교가 5와 4이기 때문에 5와 4를 비교했을 때 왼쪽 값이 더 크기 때문에 두 값의 위치를 바꾸어 줍니다.
그 다음 5와 1을 비교 연산하여 이 역시도 위치가 바뀌게 되고 이런 방식으로 한 칸씩 계속 옮겨 가며 정렬을 진행해 줍니다.
이 연산을 리스트의 가장 끝까지 진행하게 되면 다음과 같은 그림처럼 됩니다.
한 cycle을 진행할 때는 리스트 크기보다 1 작은 index까지 진행해야 합니다.
배열의 마지막 index는 비교할 다음 인덱스가 없기 때문.
이 행위가 리스트의 가장 끝까지 진행이 되었다면 한 cycle 동안 진행 된 것으로 보고 이때 리스트의 가장 마지막 위치에 들어있는 값은 리스트의 모든 데이터 중에서 가장 큰 값이 되는 것을 볼 수 있습니다.
하지만 이 값을 제외한 앞의 값들은 여전히 정렬되지 않은 상태입니다. 따라서 버블 정렬로cycle 정렬을 하더라도 완전히 정렬되지 않을 수 있는 것입니다.
그렇다면 다시 처음부터 버블 정렬을 시작합니다(2 cycle). 그러면 또 마지막을 제외한 index까지 정렬을 하면 다음과 같이 남은 데이터들 중 가장 큰 수가 마지막에서 두 번째에 위치하게 될 것입니다.
그렇게 해서 한 cycle을 마무리 할 때마다 남은 리스트 에서 가장 큰 값이 뒤부터 하나씩 채워지게 됩니다. 다음 그림을 봅시다.
위와 같은 과정으로 진행되어 남은 리스트의 데이터가 하나 남았을 때는 더 이상 정렬할 것이 없는 것으로 보고 모든 값들이 정렬이 된 상태가 됩니다.
2. 버블 정렬의 진행과정
인접한 두 element 값을 비교한다.
두 값이 정렬되어 있지 않다면(즉, 왼쪽 값 > 오른쪽 값이면) 두 element의 위치를 교환한다.
정렬이 완료된 elements를 제외하고 위의 과정을 계속 반복한다.
만약 처음에 배열의 크기가 3 이라면 2번 비교를 하게 되고 4 이면 3번 비교를 하기 때문에n개의 데이터가 있다면 n-1 번의 비교를 하게 된다. 그 후로 데이터가 하나씩 줄어들기 때문에 n-2, n-3, ... , 2, 1 번의 순서대로 비교를 하게 되는 것이다. 이는 다음과 같은 식으로 표현 된다.