선택 vs 버블 vs 합병 정렬 알고리즘

정렬 알고리즘은 배열의 데이터를 순서에 맞게 정렬할 때 사용되는 알고리즘이다.

 

선택 정렬 (Selection sort)

배열의 순번을 차례대로 순회하면서 데이터의 순서를 재정렬하는 것이 선택 정렬이다. 선택 정렬에서는 데이터를 순서대로 재배치하기 위해 배열을 반복해 돌면서 가장 작은(또는 큰) 값을 임의로 기억해 두었다가 마지막 인덱스까지 도달한 다음 그 값을 알맞은 위치로 이동시킨다.

 

반복문에서 찾은 값이 인덱스 j에 있었다고 가정할 때, 배열의 앞쪽인 인덱스 i로 이동시킬 땐 단순히 배열[i]에 있던 값과 자리를 바꾼다. 한번 자리를 바꾼 후에는 인덱스 i에 있는 값은 이미 정렬된 값이라고 볼 수 있기 때문에 그 다음 반복문부터는 i + 1 인덱스부터 배열을 순회하면 된다.

 

이런 방식으로 데이터를 정렬하게 되면 인덱스 0부터 n - 1까지의 데이터를 전부 확인해야 하고, 또 이 과정을 n번 반복하게 된다. 따라서 선택 정렬 알고리즘으로 데이터를 정렬하는 경우 O(n²) 시간이 걸린다.

 

버블 정렬 (Bubble sort)

버블 정렬은 선택 정렬에서 배열을 정렬하기 위해 배열을 0번 인덱스부터 n - 1번 인덱스까지 반복적으로 순회했던 것보다는 더 적은 단계로 데이터를 정렬하는 방식이다.

 

버블 정렬에서는 i와 i + 1번 인덱스에 위치한 값을 비교한 뒤 정렬이 필요할 경우 위치를 바꾼다. 그 다음엔 i + 1과 i + 2, i + 3과 i + 4 등... 다음 인덱스의 값들을 차례대로 비교한다. 이렇게 배열의 마지막 인덱스까지 한 쌍씩 데이터를 정렬해나가고, 배열이 전부 정렬됐음을 확인할 수 있을 때까지 과정을 반복한다.

 

이 알고리즘은 배열의 앞쪽부터 시작해서 순서가 나중인 값을 계속 오른쪽으로 밀어내는 패턴을 보이는데, 꼭 물방울이 올라오는 모양새 같다고 해서 버블 정렬이라고 한다. 선택 정렬과는 다르게 배열을 순회하면 할수록 값들이 점점 자기 위치를 찾아가기 때문에 조금 더 빠른 알고리즘이라고 할 수 있지만, 그건 best case였을 때의 얘기고 일반적으로는 선택 정렬과 같이 O(n²) 시간이 걸린다고 한다.

 

합병 정렬 (Merge sort)

합병 정렬은 앞서 나온 정렬 알고리즘들보다 훨씬 효율적으로 데이터를 정렬할 수 있는 알고리즘이다. 이진 검색(binary search) 알고리즘처럼 배열을 반씩 나눠서 더 작은 배열의 데이터를 먼저 정렬해간다.

 

합병 정렬에서는 우선 한 쌍의 데이터부터 비교할 수 있을 때까지 배열을 좌우로 반씩 쪼갠다. 잘게 나눠진 하위 배열들이 정렬된 후에는 하위 배열끼리 비교하게 될텐데, 배열끼리 비교할 땐 각 배열의 i번 값부터 비교해서 더 먼저 오는 값을 따로 뺀 후에 데이터가 빠진 하위 배열의 다음 인덱스의 값을 비교해나가면 된다.

 

큰 문제를 작게 나누고 나눠서 작은 문제부터 해결하는 분할 정복(divide and conquer) 방식의 알고리즘으로, 일반적으로 O(n * log₂n) 시간이 걸린다.