정렬 알고리즘 - 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 기수 정렬, 계수 정렬

이 글은 기술면접대비 CS전공 핵심요약집의 일부분인 알고리즘 부분의 내용을 가져와 작성하였습니다.
구글 도서 검색 을 통해 전체 페이지 240 중 102페이지를 미리보기 하실 수 있습니다.
개인적으로 아래 내용은 위키 백과를 함께 보시길 굉장히 추천 드립니다.
애니메이션이 이해에 많은 도움이 되었습니다.
버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 기수 정렬, 계수 정렬

정렬 알고리즘

정렬 알고리즘은 ‘비교하는 정렬 알고리즘’과 ‘비교하지 않는 정렬 알고리즘’으로 구분할 수 있다. 비교하는 정렬에는 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 힙 정렬, 퀵 정렬 등이 있고, 비교하지 않는 정렬에는 계수 정렬과 기수 정렬 등이 있다.

버블 정렬 (bubble sort)

비교 기반 정렬 알고리즘인 버블 정렬은 양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬한다. 버블 정렬하면 배열의 뒤에서부터 정렬된다.

오름차순으로 버블 정렬을 수행할 때 작동 방식은 다음과 같다. 정렬하려는 배열에서 연속된 인덱스의 두 값을 차례대로 a와 b라고 했을 때 b가 a보다 크면 정렬되었다고 판단한다. 반면에 b가 a보다 작으면 a와 b의 위치를 바꿔 정렬을 수행한다. 이 작업을 정렬이 완료될 때까지 수행한다.

배열의 첫 번째 요소부터 n번째 요소까지 오름차순으로 버블 정렬을 수행하면 해당 범위의 최댓값이 n번째에 위치하게 된다. 배열의 n번째 요소를 정렬하는 데 n-1번을 비교하므로 배열의 모든 요소를 정렬하려면 (n-1) + (n-2) + … + 2 +1 = n(n-1) / 2 만큼 연산을 수행해야 한다. 따라서 시간 복잡도 O(n^2)이 소요된다. 버블 정렬은 비교적 느린 정렬이지만, 별도의 메모리 공간이 필요하지 않다.

선택 정렬 (selection sort)

비교 기반 정렬 알고리즘인 선택 정렬은 배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값을 선택해 위치시킨다. 오름차순으로 정렬한다면 배열의 첫 번째 자리에는 최솟값을 위치시키고, 배열의 두 번째 자리에는 배열에서 최솟값 다음으로 작은 값을 위치시킨다.

선택 정렬의 작동 방식은 다음과 같다. 인덱스 i에 들어갈 값을 선택하는 경우에 인덱스 i-1까지는 정렬이 완료된 상태다. 따라서 인덱스 i부터 마지막 인덱스까지의 요소 중 최솟값을 선택한다. 선택한 최솟값과 인덱스 i에 담긴 값의 위치를 교ㅕ환한다. 이러한 방식으로 배열을 순회하면서 마지막 인덱스까지 정렬을 수행한다.

선택 정렬은 배열을 순회하면서 각 인덱스에 최솟값을 위치시킨다. 배열의 크기를 n이라고 할 때, 각 인덱스 i에 들어갈 숫자를 찾기 위해 n-i개의 값을 비교한다. 따라서 배열 전체에 대한 정렬을 완료하려면 (n-1) + (n-2) + … + 2 + 1 = n(n-1) / 2번 연산을 수행하므로 O(n^2)의 시간 복잡도가 소요된다. 버블 정렬과 마찬가지로 수행 시간은 느린 편이지만, 별도의 메모리 공간이 필요하지 않고 구현도 비교적 간단한 편에 속한다.

삽입 정렬 (insert sort)

비교 기반 정렬 알고리즘인 삽입 정렬은 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식이다.

오름차순으로 정렬할 때 삽입 정렬의 작동 방식은 다음과 같다. 인덱스 i에 있는 a를 정렬할 차례일 때, 인덱스 0부터 i-1까지는 이미 정렬된 상태이다. 이때 배열의 정렬된 부분에서 a보다 작거나 같은 수와 a보다 큰 수 사이에 a를 삽입한다.

삽입 정렬은 전체 배열을 순회하며 각 순회에서 인덱스 i 요소를 적절한 위치에 삽입하기 위해 최대 n-i번을 탐색한다. 따라서 1 + 2 + … + (n-2) + (n-1) = n(n-1)/2번 연산을 수행하며, 시간 복잡도는 O(n^2)이 된다.

합병 정렬 (merge sort)

비교 기반 정렬 알고리즘인 합병 정렬은 재귀를 이용하는 분할 정복 알고리즘이다. 분할은 배열을 쪼개는 것이고, 정복은 분할한 배열을 정렬하면서 하나로 합병하는 것을 의미한다. 그래서 정렬하려는 배열을 크기가 0 또는 1이 될 때까지 절반식 분할한다. 분할된 각각의 배열은 다시 하나의 배열로 합쳐지면서 정렬을 수행한다.

합병 정렬하려면 먼저 재귀함수를 호출해 배열을 분할한다. 배열 크기가 1 이하가 되면 분할을 종료한다.

분할을 마친 각 배열을 다시 하나로 합병하면서 정렬을 수행한다. 이때 합병하려는 두 배열과, 두 배열을 합친 크기의 빈 배열이 필요하다. 합병하려는 두 배열은 정렬이 완료된 상태이며, 각 배열의 앞에 있는 요소부터 비교하면서 정렬한다. 오름차순이면 두 배열의 앞에 있는 요소 중 작은 숫자를 빈 배열에, 내림차순이면 큰 숫자를 빈 배열에 넣는다. 이러한 방식으로 분할한 배열을 다시 합병하면서 정렬한다. 연산이 끝나면 오름차순으로 정렬된 하나의 배열을 얻을 수 있다.

합병 정렬의 시간 복잡도는 O(n log n)으로 수행 시간 면에서 효율적이다. O(n)은 배열이 정렬되는 데 걸리는 시간 복잡도이고, O(log n)은 배열의 분할 또는 합병 시 걸리는 시간 복잡도이다. 합병 단계에서 배열의 정렬이 일어나므로 합병 정렬하는 데 총 O(n log n)이라는 시간 복잡도가 소요된다.

퀵 정렬 (quick sort)

비교 기반 정렬 알고리즘인 퀵 정렬(quick sort)은 합병 정렬과 마찬가지로 분할 정복 알고리즘이다. 배열에서 피봇(pivot)이라는 특정 값을 선택해 피봇보다 작은 값으로 구성된 배열과 피봇보다 큰 값으로 구성된 배열로 분할해 정렬하는 방식이다. 피봇은 일반적으로 배열의 첫 번째 요소나 마지막 요소를 선택한다. 피봇을 기준으로 배열에서 피봇보다 작은 값은 피봇의 왼쪽으로, 피봇보다 큰 값은 오른쪽으로 옮기면서 배열을 두 개로 분할해 정렬한다.

퀵 정렬을 수행할 때 low와 high라는 변수를 두어 피봇보다 작은 수와 피봇보다 큰 수를 분리한다. low는 배열의 첫 번째 요소에서 시작해 오른쪽으로 한 칸씩 이동한다. log가 가리키는 값이 피봇보다 작으면 오른쪽으로 한 칸을 이동하고, 피봇보다 크면 이동하지 않는다. low와 high 둘 다 이동하지 않을 때 두 변수가 가리키는 값을 교환해 배열의 왼쪽에는 피봇보다 작은 값이, 배열의 오른쪽에는 피봇보다 큰 값이 위치하도록 한다.

분할은 배열의 크기가 1 이하가 될 때까지 반복해서 수행한다. 이와 같이 분할 정복을 기반으로 한 퀵 정렬의 평균적인 시간 복잡도는 O(n log n)이다. 하지만 평균적인 시간 복잡도가 되려면 피봇을 기준으로 배열을 균등하게 분할할 수 있어야 한다. 만약 역순으로 정렬된 배열에서 첫 번째 요소를 피봇으로 선택하는 경우 (역순으로 정렬이기 때문에 첫 번째 요소는 가장 큰 요소이다.) 시간 복잡도는 O(n^2)이 될 수 있다. 따라서 피봇으로 어떤 값을 선택하느냐에 따라 퀵 정렬의 성능이 좌우된다.

힙 정렬 (heap sort)

비교 기반 정렬 알고리즘인 힙 정렬은 최대 힙이나 최소 힙 자료구조를 이용해 정렬을 수행한다. 최대 힙으로 오름차순 정렬을, 최소 힙으로 내림차순 정렬을 할 수 있다. 힙 정렬 과정은 크게 배열을 힙으로 만드는 힙 생성 알고리즘 과정과 힙에서 요소를 꺼내 정렬하는 과정으로 나뉜다. 힙 생성 알고리즘(heapify)

은 특정 노드의 두 자식 노드 중 우선순위가 더 높은 자식 노드와 위치를 교환하는 방식이다.

먼저 배열을 힙으로 만드는 과정을 수행한다. 그리고 생성한 (최대) 힙에서 삭제 연산을 이용해 정렬을 수행한다. 삭제 연산으로 꺼낸 루트 노드의 값을 힙의 마지막 노드가 있던 자리로 이동한다. 이 과정을 노드 개수만큼 반복하면 정렬이 완료된다. 이와 같이 힙 정렬을 수행하면 시간 복잡도는 O(n log n)이다. 힙 생성 알고리즘을 수행하는 데 O(log n)이, 전체 요소가 n개여서 전체 정렬하는 데 O(n log n)이 걸린다.

기수 정렬 (radix sort)

기수 정렬은 비교하지 않는 정렬 알고리즘으로, 낮은 자리수부터 정렬을 수행한다. 십진수에서 각 자릿수에는 0부터 9까지 숫자가 올 수 있다. 그래서 숫자별로 버킷(bucket)이라는 큐를 생성한다. 정렬하려는 숫자들의 각 자릿수에 해당하는 숫자를 각각의 버킷에 넣어 정렬하고 이를 자릿수만큼 반복한다. 각 버킷은 큐 방식으로 동작한다.

데이터 개수를 n, 최대 자릿수를 d라고 할 때 기수 정렬의 시간 복잡도는 O(dn)으로 빠른편에 속한다. 하지만 버킷을 구성하기 위한 추가 메모리가 필요하고, 정렬할 수 있는 데이터 타입이 한정적이라는 단점이 있다.

계수 정렬 (counting sort)

비교하지 않는 정렬 알고리즘인 계수 정렬(counting sort)은 이름 그대로 데이터의 개수를 세서 정렬하는 방식이다. 정렬하려는 데이터의 범위를 인덱스로 갖는 빈 배열을 생성하는데, 데이터 범위가 0부터 99까지라면 크기가 100인 빈 배열을 생성한다. 이후 정렬하려는 배열을 순회하면서 데이터에 해당하는 인덱스의 값을 1씩 증가시킨다. 따라서 계수 정렬은 데이터의 범위가 0 또는 양의 정수여야 한다는 제약 조건이 있다.

정렬하려는 데이터의 개수를 n, 데이터의 최댓값을 k라고 할 때, 계수 정렬의 시간 복잡도는 O(n+k)가 된다. 데이터의 최댓값이 시간 복잡도에 영향을 주며, 데이터 범위만 한 크기의 배열을 생성해야 하므로 추가로 사용하는 메모리 공간이 필요하다.