기본정렬

선택, 버블, 삽입, 쉘, 퀵, 합병, 힙, 계수, 기수 정렬

 

모두 오름차순을 기준으로 정렬

 

1. 선택 정렬

첫번째 원소부터 마지막 원소까지 정렬을 한다고 했을때 전체 배열 중 가장 작은 원소를 찾아 첫번째 원소부터 순서대로 교환해가며 최솟값을 차례대로 넣는 정렬이라고 할 수 있다. 그래서 총 n번, 나머지 원소들 n-1, n-2, n-3, ... 개의 원소와 비교하게 되므로 시간복잡도는 O(n^2)이다.

 

2. 버블 정렬

거품이 수중위로 올라가는 것처럼 인덱스를 첫번째에서 마지막으로 이동하는 도중 해당 위치에서의 값이 다음 인덱스의 값보다 크면 교환하여 값이 큰 원소를 마지막으로 계속해서 밀어내는 정렬 방법이라고 할 수 있다. 즉 마지막위치에 최댓값을 쌓아가는 방식으로 정렬한다. 시간복잡도는 O(n^2)이다.

 

3. 삽입 정렬

삽입 정렬은 카드뽑기와 비슷한 원리라고 할 수 있다.  첫번째 원소부터 마지막 원소까지 n번 탐색과정 중 현재 인덱스의 원소값을 임시로 저장한 후 이전인덱스들과 순차적으로 비교해 가며 저장 값보다 큰 원소가 나오는 동안은 계속 이동 한다. 자신보다 작은 원소가 나오면 해당 인덱스의 다음 인덱스에 값을 삽입하는 정렬 방법이라고 할 수 있다. 시간복잡도는 O(n^2).

 

4. 쉘 정렬

부분화일을 선정해서 해당 부분화일들끼리 삽입정렬를 수행하는 방법이라고 할 수 있다.  삽입정렬의 경우 자신보다 작은 원소가 나오게 되면 해당 인덱스에 대한 탐색을 마치기 때문에 쉘 정렬을 통해 거의 정렬이 된 배열을 미리 만들어주는 방식이라고 할 수 있다. 그래서 화일 값을 어떻게 선정하는 지가 가장 중요한 요소 중 하나라고 할 수 있다. 화일 값 선정은 대체로 h = h*3 + 1 의 값들로 선정하되 그 크기가 배열의 전체 크기인 n보다 작은 값을 선정한다. 예를들어 h=4 이고 n=10이면 [1,5,9], [2,6,10], [3,7], [4,8] 번째 원소가 부분 화일(배열)이 되어 각각 삽입정렬을 수행하는 방식이라고 할 수 있다.  시간복잡도는 최악의 경우 O(n^2)이지만 보통 O(n^(2/3)) 을 따른다.

 

5. 퀵 정렬

이분탐색의 개념이 들어간 정렬. 피봇값을 기준으로 왼쪽에 남아있는 원소들 중 첫번째를 i 인덱스로 지정, 마지막 원소를 j 로 지정해서 i는 피봇보다  큰 값이 나올때까지 오른쪽으로 이동 시키고 j는 피봇보다 작은 값이 나올때까지 왼쪽으로 이동시킨다. 그리고 i와 j의 값을 교환한다. 이와 같은 과정을 i>=j가 되면 멈추고 i번째 원소와 피봇값을 교환한다.  

그리고 i-1 값을 다음 분할의 분기점인 피봇값으로 지정한다. 즉 1부터 n까지 배열이 있다고 하면 맨 처음 피봇값은 n번째 원소의 값이 되고 교환과정을 거쳐 n/2 번째 값을 다음 피봇으로 지정하게 되면 그다음 탐색은 1~n/2,  n/2+1 ~ n 범위에서 위와 같은 방식으로 부분정렬을 진행하게 된다. 대체로 이분탐색의 개념이라고 할 수 있기떄문에 시간복잡도는 O(nlogn)이다.

 

6. 합병 정렬

이분탐색을 통해 분할정복을 적용한 정렬 방법이다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할 된 리스트를 합하여 전체 리스트를 정렬시키는 방법이다. 시간복잡도는 O(nlogn)

 

7. 힙 정렬

 트리를 최대힙 구성으로 만든 후에 첫번째 원소를 마지막 원소와 교환하여 다시 최대힙 구성으로 만들어주며 리스트의 마지막 원소를 최댓값으로 계속해서 쌓는 방식으로 정렬하는 방법이다. 최대힙 구성은 부모노드와 자식노드와의 값을 비교하며 교환하는 방식이다. 노드의 높이가 logn이기 때문에 최대힙으로 트리를 구성하는 시간복잡도는 logn이다. 거기에 n개의 원소를 정렬하는 방식이기 때문에 총 시간 복잡도는 nlogn이라고 할 수 있다.

 

8. 계수 정렬

리스트의 값의 범위가 작을 때 쓰기 좋은 정렬이다. Counting 이라고 하는 값의 갯수를 저장하는 배열을 추가로 사용한다. 그래서 해당 원소의 갯수만큼 차례대로 리스트를 재정렬 하는 방법이기 때문에 시간복잡도는 O(N) 밖에 되지 않는다. 하지만 원소 값의 범위가 클때 Counting 배열 공간이 매우 커지기 때문에 메모리의 낭비가 있다는 단점이 있다.

 

9. 기수 정렬 

기수 정렬은 리스트의 원소값의 자릿수를 기준으로 0~9까지 표현되기 때문에 10개의 큐를 생성하여 1의 자리에서부터 10, 100, 1000, ... , 원소값의 최대 자릿수 까지 원소의 숫자에 해당하는 큐에 넣어 리스트를 재정렬 하는 방식이다. 그래서 원소값의 최대 자릿수까지 이 과정을 반복하면 리스트의 정렬이 끝나게 된다. 이 방법은 O(자릿수 * n )의 시간 복잡도를 가지고 있지만  자릿수가 커지게 되면 큐를 자릿수 만큼 생성해야하는 메모리 낭비와 그만큼 시간복잡도가 커지는 단점을 가지고 있다. 따라서 자릿수의 범위가 작을 때 유용하게 사용된다.

 

반응형

 

소스코드