정렬에 관하여... (삽입, 선택, 버블, 셸, 퀵, 합병, 힙, 기수)

이 글은 알고리즘과 정보처리기사 두가지 모두 해당하는 글입니다.

 

정렬 알고리즘은,

시간복잡도, 구현복잡도, 메모리사용량 등으로

효율성을 따질 수 있는데,

 

이 중 나머지는 큰 의미가 없고 주로 시간복잡도로만

그 효율성을 따집니다.

 

※글을 읽는 분께는 죄송하지만,

 

이 글은 토론 및 발표 때 참고자료용으로 작성한 거라,

작성자가 직접 말로 설명하는 부분이 많아서,

그림만 보고는 이해가 어려울 수도 있습니다.

 

 

삽입정렬 (Insertion Sort)

최적 시간복잡도 : O(n)

평균 시간복잡도 : O(n²)

최악 시간복잡도 : O(n²)

 

가장 구현하기 쉬운 정렬법의 하나입니다.

 

매 회전마다 각 자릿수의 인덱스와,

각 자릿수보다 앞선 인덱스를

처음부터 순서대로 비교해서,

더 작은 수를 맞는 위치에 삽입하는 방식으로 정렬합니다.

 

사람의 눈으로 보기엔 빨라보이지만,

실제 연산에서는 매 반복마다 삽입이 이루어지면,

뒤에 있는 원소들은 자리바꿈이 계속 일어나고,

비교 또한,앞선 인덱스의 모든 원소들과 비교를 하기 때문에,

속도가 느린 수행방법입니다.

 

 

선택정렬 (Selection Sort)

최적 시간복잡도 : O(n²)

평균 시간복잡도 : O(n²)

최악 시간복잡도 : O(n²)

 

매 회전마다

남아있는 모든 자릿수를 비교해서,

가장 작은 값을 선택한 뒤,

지금 비교하는 인덱스에 오도록 하고,

다음 회전이 되면 그 다음 인덱스를 비교값으로 합니다.

 

삽입정렬과 마찬가지로,

반복마다 모두 비교하고,

값이 수없이 교환되기 때문에

수행시간이 느린 정렬 방법입니다.

 

 

버블정렬 (Bubble Sort)

최적 시간복잡도 : O(n²)

평균 시간복잡도 : O(n²)

최악 시간복잡도 : O(n²)

 

매 회전마다

모든 인덱스를 옮겨가며,

맞닿은 두 수를 비교해서

더 작은 값이 작은 인덱스로 오도록 합니다.

 

그러면 마지막 비교값은 가장 큰 값이 되기 때문에,

매 회전의 마지막 인덱스는 정렬이 된 상태가 됩니다.

 

bubble에는 거품, 둥근 덮개 라는 뜻이 있는데,

두 값을 거품처럼 씌워서

비교한다고 생각하시면 기억하기 좋을 것 같습니다.

 

 

셸정렬 (Shell Sort) -사람 이름입니다.

최적 시간복잡도 : O(n)

평균 시간복잡도 : O(n¹·⁵) 또는 그것보다 나음.

최악 시간복잡도 : O(n²)

 

매 반복마다,

배열을 절반으로 나누고,

그 절반의 길이를 gap 이라고 합니다.

 

gap 만큼 떨어진 값끼리 정렬을 한 뒤,

다시 gap 을 반으로 나눠서 정렬하는 것을 반복합니다.

 

이것을 gap 이 1 이 될 때까지 반복하면 정렬이 완료됩니다.

 

삽입정렬에서 부분리스트가 정렬이 된 상태라면

수행시간이 확 줄어드는 것을 발견한,

도널드 L 셸 이라는 사람이 고안한 정렬법입니다.

 

 

퀵정렬 (Quick Sort)

최적 시간복잡도 : O(nlog₂n)

평균 시간복잡도 : O(nlog₂n)

최악 시간복잡도 : O(n²)

 

퀵정렬은 정렬 방식중에 가장 빠르고,

최악 시간복잡도가 n제곱인 이유는,

이미 정렬된 배열일 경우엔

분할이 불균형해져서,

수행시간이 길어지기 때문입니다.

 

배열의 원소들 중에서

임의의 피벗 (pivot) 을 지정해, 

(중심점이라는 뜻)

 

그보다 작은 값들과 큰 값들을 분류하는 방식으로 정렬하고,

분류된 값에서 다시 피벗을 정하고 분류하는 방식으로,

그것을 반복해서

더 이상 나눌 수 없게 되면 정렬이 완료됩니다.

 

그리고 이건 글씨가 작아서,

이미지를 확대해서 보시길 권유드립니다.

 

 

합병정렬 (Merge Sort)

최적 시간복잡도 : O(nlog₂n)

평균 시간복잡도 : O(nlog₂n)

최악 시간복잡도 : O(nlog₂n)

 

병합정렬, 2-Way 정렬, 모두 같은 말입니다.

배열을 계속해서 반씩 나누고,

더이상 나눌 수 없으면 다시 합치고,

합친 값을 정렬하고 다시 합치는 과정을 반복해서,

리스트의 개수가 다시 1개가 되면 정렬이 완료됩니다.

 

이름처럼 병렬의 형태를 띄고 전부 나눴다가 다시 합치면서 정렬됩니다.

그 유명한 폰 노이만이 고안한 정렬법입니다.

 

 

힙정렬 (Heap Sort)

최적 시간복잡도 : O(nlog₂n)

평균 시간복잡도 : O(nlog₂n)

최악 시간복잡도 : O(nlog₂n)

 

완전 이진 트리의 구조를 이용하는 정렬입니다.

(Complete Binary Tree)

트리의 부모를 Root, 자식을 Leaf 라고 합니다.

 

노드의 역순으로 리프와 루트를 비교해,

큰 값을 루트쪽으로 오게 교환합니다.

이것을 반복해 최대힙을 만들고,

 

완성된 최대힙에서,

맨 위 루트를 마지막 노드와 교환하고, 

 

다시 최대힙을 만드는데,

마지막 노드는 비교에서 제외하는 방식으로 정렬합니다.

 

이진 트리는, 하나의 부모에 0 ~ 2개의 자식이 있는 것이고,

정 이진 트리는, 하나의 부모에 0개 혹은 2개의 자식이 있는 것을 말합니다.

완전 이진 트리는, 하나의 부모에 0 ~ 2개의 자식이 있는 것이고,

추가로 자식 노드가 왼쪽부터 채워져야 완전 이진트리라고 할 수 있습니다.

그리고 포화 이진 트리는, 모든 부모가 자식을 전부 2개씩 다 갖고 있는 것을 말합니다.

 

 

기수정렬 (Radix Sort) = Bucket Sort

최적 시간복잡도 : O(nw) w는 Bucket 의 개수입니다.

평균 시간복잡도 : O(nw)

최악 시간복잡도 : O(nw)

 

 

Queue 자료구조를 이용해서 자릿수 (Digit) 별

버킷을 먼저 만들고,

낮은 자릿수부터 정렬을 진행하는데,

(1의자리 -> 10의자리 -> 100의자리)

 

배열의 순서대로

각 자릿수와 일치하는 버킷에 담은 뒤,

 

빼낼 때는 큐의 순서대로 빼내서

정렬하는 방식입니다. 

 

버킷이라는 걸 이용해서 수행시간을 엄청나게 줄인
굉장히 단순하고 효율적이며 재밌는 방식입니다.