정렬이란 레코드들을 키값의 순서에 맞게 재배열하는 것입니다. 데이터 구조에 따라 어떤 정렬 방법을 사용하느냐가 효율성에 큰 영향을 줍니다.
💡구현의 난이도와 효율성의 상대적인 비교에 따른 분류
단순하지만 비효율적인 방법:
선택 정렬, 삽입 정렬, 버블 정렬 등
복잡하지만 효율적인 방법:
퀵 정렬, 합병 정렬, 기수 정렬 등
💡안정성에 따른 분류
버블 정렬, 삽입 정렬, 합병 정렬, 기수 정렬, 계수 정렬 등
안정성이란 같은 키값을 가진 레코드의 상대적인 위치가 정렬 후에도 변하지 않는 것을 말합니다.
💡평균 시간복잡도에 따른 분류
📌편의를 위해 평균을 기준으로 분류했어요 :D
📌코드 없이 전체적인 작용 원리, 장점, 단점 위주로 적었습니다 : )
📍버블 정렬
버블 정렬은 인접한 2개의 레코드를 비교하여 크기 순서가 아니라면 교환하는 과정을 전체가 정렬될 때까지 반복하는 알고리즘입니다. 즉 모든 사이클마다 모든 레코드를 비교-교환합니다.
장점: 안정적인 방법이고 구현이 비교적 쉽다.
단점: 비교-교환 과정에서 순서에 맞지 않은 요소를 이동시킬 수 있다.
📍선택 정렬
선택 정렬은 배열에서 최솟값을 찾아 배열의 첫 요소와 교환하는 알고리즘입니다. 이 과정을 전체 요소의 수 - 1 만큼 반복하면 전체가 정렬됩니다.
한 패스당 한 번의 교환을 위해 작은 값의 위치를 index변수에 저장해두고 업데이트를 하다가 한 패스가 끝나면 index에 저장된 값을 배열의 첫 요소와 swap하는 것입니다.
장점: 이동 횟수가 미리 결정된다.
단점: 안정적이지 않아 같은 키값을 가진 레코드들의 상대적인 위치가 정렬 후에 바뀔 수 있다.
📍삽입 정렬
삽입 정렬이란 카드를 정리하듯 정렬된 부분과 비교하며 삽입할 위치를 정하는 알고리즘입니다. 두 번째 요소부터 시작하여 삽입 위치를 정한 후 요소들을 뒤로 옮기고 그 자리에 삽입하는 것입니다. 즉 정렬된 부분과 정렬되지 않은 부분이 나뉘므로 정렬된 부분에서의 요소 삽입은 매우 효율적입니다.
장점: 첫 원소를 정렬이 됐다고 가정 후 시작하여 정렬된 부분에서의 삽입은 효율적이다. 안정적인 방법이다.
단점: 요소들이 이웃한 위치로만 이동하기 때문에 최종 위치가 멀리 있을 시 많은 이동을 해야한다.
장점을 바탕으로 단점을 보완한 정렬 방법이 아래의 쉘 정렬입니다.
📍쉘 정렬
쉘 정렬은 삽입 정렬이 어느정도 정렬된 배열에서는 효율적이라는 점을 바탕으로 만든 알고리즘입니다. 삽입 정렬과 달리 리스트를 비연속적으로 나눠 여러개의 부분리스트로 만듭니다.
이때 간격K를 기준으로 나누며 나눠진 부분리스트는 삽입 정렬로 정렬됩니다. 이러면 1번의 패스가 끝난 것이고 다음 패스부터는 간격k를 절반으로 줄인 다음 간격k가 1이 될 때까지 반복합니다.
쉘 정렬의 시간 복잡도는 O(n^1.5)로 쉘 정렬보다 효율적입니다.
📍합병 정렬
합병 정렬은 분할 정복 알고리즘을 기반으로 한 정렬 알고리즘입니다.
*분할 정복 알고리즘?
: 문제를 작은 2개의 문제로 분리 후 각각을 해결하고 모아서 원래 문제를 해결하는 방법. 문제가 충분히 작지 않다면 더 나눈다.
재귀를 통해 전부 나눈 후 2의 배수로 합치면서 정렬하는 과정을 반복합니다. 즉 합치는 순간에 정렬을 하므로 정렬된 배열끼리 정렬을 하게 되는 것입닙다. 이때 정렬 결과를 담아둘 임시 배열이 필요합니다.
장점: 안정적인 방법이다. 최악, 평균, 최악의 경우에도 같은 O(nlogn)의 시간 복잡도를 가진다.
단점: 임시 배열이 필요하므로 추가적인 메모리 공간을 쓰게 된다.
📍퀵 정렬
퀵 정렬도 분할 정복 알고리즘을 기반으로 한 정렬 알고리즘입니다. 합병 정렬과 다른 점은 1. 리스트를 불균형하게 분할합니다. 2. 추가적인 메모리 공간이 필요 없습니다. 3. 나누는 과정이 곧 정렬 과정입니다. 즉 나누면서 정렬합니다.
리스트를 분할할 때 피벗이라는 요소를 선택하여 피벗보다 더 작은 값은 왼쪽, 더 큰 값은 오른쪽으로 이동시키며 이렇게 나뉜 부분리스트에 대해 순환 호출로 분할-정렬을 리스트의 크기가 0이나 1이 될 때까지 반복합니다.
장점: 불필요한 데이터의 이동을 줄이고 먼거리의 데이터를 교환할 뿐만 아니라 한 번 결정된 피벗은 다음 정렬 연산에서 제외된다.
단점: 불균형 분할의 특징이 정렬된 리스트에서는 단점으로 작용한다.
📍힙 정렬
힙 정렬은 최대힙, 최소힙을 이용해 정렬하는 알고리즘입니다. 오름차순은 최소힙, 내림차순은 최대힙을 구성하면 됩니다.
이때 힙 정렬을 하기 위해 요소 하나씩 heapify를 해준 후 루트노드에 도달한 최솟값, 최댓값을 마지막 노드와 swap하고 정렬된 부분(swap된 노드)을 제외 하면 됩니다. heapify의 시간 복잡도 는 O(logn) 이며 모든 노드의 수(n)만큼 반복하니까 시간 복잡도는 O(nlogn)이 됩니다.
장점: 추가적인 메모리 공간이 필요 없고 항상 O(nlogn)의 시간 복잡도를 가진다. 가장 큰 값 또는 작은 값 몇 가지만 필요할 때 유용하다.
📍기수 정렬
기수 정렬은 다음에 나올 계수 정렬과 같이 비교연산을 하지 않는 정렬 알고리즘입니다.
기수란 수의 자릿수를 의미합니다. 즉 자릿수를 기준으로 각각의 버킷에 맞게 넣었다 빼는 동작을 반복합니다. 10진수의 경우 0~9의 총 10개의 버킷만 있다면 2자리수도 정렬이 가능합니다.
이때 낮은 자릿수부터 정렬한 다음 높은 자릿수를 정렬하면 됩니다. 또한 버킷은 큐 형식으로 구현합니다. 즉 버킷에 해당 자릿수를 enqueue 하고 dequeue하는 것입니다.
장점: 비교 연산을 하지 않아 다른 알고리즘 보다 빠르며 안정적인 방법이다.
단점: 버킷을 구현해야하므로 추가적인 메모리 공간이 필요하다. 또한 버킷의 크기를 모든 케이스에 맞게 정의하기 어렵다.
📍계수 정렬
계수 정렬은 기수 정렬과 같이 비교연산을 하지 않는 정렬 알고리즘입니다.
수의 범위 조건이 있는 경우 사용하는 정렬 알고리즘으로 각 수가 몇 번 나오는지를 수의 크기를 기준으로 카운트 해뒀다가 그 값들을 배열에 인덱스로 사용해 출력하는 방법입니다.
배열의 인덱스는 양수만 존재하기 때문에 계수 정렬 사용 시 조건이 있습니다.
1. 리스트 내의 모든 수는 음수, 소수가 아닌 정수다.
2. 값의 범위가 메모리 사이즈를 넘으면 안 된다.
장점: 안정적인 방법이다.
단점: 추가적인 메모리 공간이 필요하고 가장 큰 수에 영향을 받아 시간 복잡도까지 달라진다.
