정렬 알고리즘

 

 

Selection sort

 

리스트의 i번째까지 정렬된 상태에서 나머지 n-i개의 리스트를 훑는다

그중 가장 작은 원소를 찾아 i+1번째에 놓는다

나머지가 없어질 때까지 반복

 

 

Insertion sort

 

리스트의 i번째까지는 정렬된 상태에서 리스트의 i+1번째 원소를 본다

이미 정렬된 길이 i의 리스트를 훑으면서 i+1원소가 들어갈 위치를 찾아 넣는다

n번째 원소까지 반복

 

 

Bubble sort

 

이웃한 두 원소를 비교해서 정렬한다

한칸씩 이동하며 n-1번 반복하면 가장 큰 원소 하나가 리스트 끝에 온다.

n개의 원소가 모두 정렬될 때까지 위를 반복

 

 

단순히 (n-1)C2번의 모든 비교를 수행하는 selection, insertion, bubble의 시간복잡도는 n^2이다

리스트의 처음부터 끝까지 훑는 작업을 n번 하기 때문

대신 list 내에서 원소들을 비교하며 바꾸므로 추가적으로 메모리를 쓰진 않는다.

시간은 넉넉하고 메모리가 부족할 때 쓰면 좋을 것 같다.

 

 

 

Merge sort

 

이미 정렬된 2개의 리스트를 하나로 합쳐 정렬하는 알고리즘을 짠다

리스트를 2개의 리스트로 나누는 재귀 과정을 반복

쪼개다보면 길이 1의 리스트(=이미 정렬된 리스트)가 되니 위에 짜둔 합침 알고리즘을 적용할 수 있다.

점점 합쳐가며 새 리스트에 저장을 반복하면 정렬된 리스트가 된다.

 

 

Quick sort

 

merge와 마찬가지로 리스트를 2개의 리스트로 소분하여 재귀적으로 작동한다.

리스트를 둘로 자르는 기준은 pivot이라는 임의로 정한 한 원소와의 대소관계이다.

 

 

Heap sort

 

힙이란 모든 부모자식간에 일련의 대소관계가 적용되는 구조를 말한다.

부모>자식을 만족하는 힙이라면 제일 위에 있는 원소가 최댓값이고,

부모<자식을 만족하는 힙이라면 제일 위가 최솟값일 것이다.

때문에 최댓값 혹은 최솟값을 구하기가 아주 쉽다.

인풋받은 리스트를 힙의 형태로 만든다.

최댓값을 list[-1]로 뽑아내고 힙의 맨 막내(원래 -1에 있던 원소)를 조부모 자리에 앉힌다.

위로 올라온 막내가 힙내 대소관계에 의해 자기가 있을만한 자리까지 미끄러져 내려가면,

다시 맨 위에는 최댓값이 위치한다.

즉, list[-1]에는 힙으로부터 뽑힌 최댓값이 있고, list[0:n-1]은 다시 힙의 형태가 되었다.

list[0:n-1]에서 다시 최댓값을 뽑아 list[-2]에 앉힌다. 의 반복

 

 

merge, quick, heap은 nC2가지의 모든 원소간 비교를 다 따지진 않고 적절한 거름을 거친다. 따라서 selection, insertion, bubble보다 속도가 더 빠르다.

 

merge는 길이 n짜리 새 리스트를 만들어서 거기에 정렬된 원소들을 저장하므로, n의 메모리가 필요하다.

적당한 메모리가 있다면 단순비교정렬들보단 빠른 일정한 속도로 결과를 낼 수 있을 것이다.

 

quick은 merge처럼 리스트를 소분하여 정렬하고 다시 합치지만, 임의의 pivot in list를 분할의 기준으로 삼는다. 따라서 정렬해야 할 list의 컨디션에 따라 속도와 메모리 사용량이 달라진다.

속도는 정렬 방향의 완전 역방향(오름차순 정렬해야하는데 인풋이 내림차순, 혹은 그 반대)인 최악의  경우라면 단순 비교 정렬과 마찬가지로 nC2가지의 모든 비교를 다 해야하기 때문에 n^2의 시간복잡도가 나올 것이다.

메모리는 일반적으로 merge의 n보다는 덜 쓸 것이지만 최악의 경우 n만큼도 쓸 것이다. 즉 메모리 사용량은 단순비교 <= qucik <= merge 이고, 속도는 merge <= quick <= 단순비교이다.

 

heap은 단순비교처럼 정렬된 원소를 리스트의 구석에 보관하므로 추가적으로 메모리를 쓰진 않는다. 또한 nC2가지의 모든 경우를 비교하지도 않으므로 속도도 단순비교보다 빠르다.

하지만 list를 힙의 형태로 재편성했다가 그것을 정렬하므로 안정적이지 않다. (같은 값의 두 원소간 선후관계가 그대로라는 보장이 없다.) 메모리와 속도 모두 위의 다른 정렬들보다 우수하니, 안정성이 필요없는 경우라면 좋은 선택지일 것 같다.

 

 

 

Counting sort

 

원소의 range를 크기로 하는 도수분포표를 만든다.

리스트의 각 원소마다 도수분포표의 자기 위치의 count에 +1을 한다.

도수분포표를 참고하여 리스트를 정렬한다.

 

위의 selection ~ heap sort가 두 원소간의 비교를 통해 정렬하는 비교 정렬이었다면, 

counting sort는 원소간에 비교를 하지 않는다.

길이 n의 list를 쭉 훑으면서 길이 range의 도수분포표에 넣고 그것을 보면서 리스트를 다시 작성하니,

n+range번의 연산을 하고 range+n만큼의 메모리를 필요로 한다.

쉽고 빠르고 가볍고 기발한 방법이지만, range가 무한하다면 쓸 수가 없다.

상황에 맞게 range를 고려하고, n^2이나 nlogn과 비교해봤을 때 더 낫다면 애용할 것 같다.

 

 

counting sort 말고도 원소간의 직접적인 비교 외의 개성적인 방법으로 효율을 높인 비 비교 정렬이 더 있다고 한다.

자리수별로 따로 정렬해서 결과적으로 사전식으로 정렬되는 radix sort도 그중 하나.