[C#] 정렬(Sorting)

정렬은 크게 선형 정렬, 분할 정복 정렬로 나뉜다.

​

선형 정렬은 하나의 데이터를 정렬하기 위해 모든 데이터를 다 순회해야 하는 정렬이다. n개의 요소를 재위치시키기 위해 n개를 확인하는 정렬이다. 그래서 시간복잡도가 모두 O(n^2)이다. (잘 안 쓰임)

선형정렬은 선택 정렬, 삽입 정렬, 버블 정렬이 있다.

​

분할 정복 정렬은 재배치 할 리스트를 잘게 쪼개서 해결하는 방법이다. 리스트를 작은 부분들로 분할하게 되면서 선형정렬 때 했던 모든 데이터를 순회했던 과정을 거치지 않아도 되기 때문에 속도가 빠르다. 그래서 분할 정복 정렬의 평균적인 시간복잡도는 O(NlongN)이다.

분할정복정렬은 힙 정렬, 합병 정렬, 퀵 정렬이 있다.

​

​

​

선택 정렬

(별로 중요하진 않음)

데이터 중 가장 작은 값부터 하나씩 선택하여 정렬하는 방식이다. 무작위로 놓여진 데이터를 모두 돌면서 가장 작은 데이터 하나를 선택하여 가장 앞으로 보낸다. 원래 가장 앞에 있었던 데이터는 선택된 데이터와 자리를 교체하게 된다.

리스트를 다 거치면서 하나의 최솟값을 탐색하는 것을 하나의 회전이라고 한다.

​

​

​

삽입 정렬

(별로 중요하진 않음)

삽입 정렬은 데이터를 앞부분부터 돌면서 데이터보다 작은 데이터를 앞으로 삽입하는 방식이다. 따라서 리스트가 대부분 정렬이 되어 있는 상태에서 삽입 정렬을 하면 매우 빠르게 동작한다. 하나의 데이터를 삽입하거나 제자리에 두는 한 번의 과정을 하나의 단계라고 한다(?)

​

​

​

버블 정렬

가끔 손코딩하는 정도로 나올 수 있다.

버블정렬은 가장 앞에 있는 데이터부터 그 다음 데이터와 비교하여 더 큰 데이터를 만날 때까지 교체하는 방식이다. 더 큰 데이터를 만나게 되면 멈추고 큰 데이터가 다음 데이터와 비교하는 것을 반복한다. 이렇게 리스트를 한 번 다 거치는 것을 하나의 회전이라고 한다.

​

​

​

힙 정렬

힙 자료구조의 원리를 이용하여 우선순위가 가장 높은 요소부터 정렬시키는 방법이다. 재배치할 배열들을 힙의 이진트리 형식으로 구성하고 우선순위가 알맞게 되게끔 힙을 구성한다. 그 후 가장 앞의 부모노드가 가장 우선순위가 되었을 때 그 노드를 빼내 배열에 정렬시킨다. 내림차순 정렬을 하려면 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 힙 정렬은 전체 자료를 정렬하는 것보다 가장 큰 값 몇 개만 필요할 때 매우 유용하게 쓰인다.

 

힙 정렬의 단점은 불안정 정렬이다. 데이터의 순서를 보장하지 못한다. 동일한 값(중복된 값)을 정렬하는데 입력된 순서에 상관없이 정렬로 인해 순서가 뒤바뀔 수 있는 것을 불안정 정렬이라고 한다.

또한 힙 정렬은 참조 지역성 원리로 인해 속도가 느려질 수 있다. 참조 지역성 원리란, 캐시 메모리가 메모리를 연속적으로 읽을 경우 빠른 속도로 읽을 수 있는데 무작위로 읽는 작업은 메모리에서 읽어오는 데 속도차이가 있다는 것이다. 힙 정렬은 트리 구조이기 때문에 비선형구조라 원소를 임의 접근 해야한다. 따라서 속도가 느려질 수 있다.

힙 정렬의 장점은 추가적인 메모리 할당을 필요로 하지 않기 때문에 항상 O(NlogN)을 보장한다.

​

​

​

병합 정렬(합병정렬)

합병 정렬은 데이터를 2분할하여 정렬하고 다시 합병하는 방식이다.

큰 덩어리를 절반으로 나누고, 그 절반에서 또 반절을 나누는 것을 하나의 데이터가 남을 때까지 반복한다. 그렇게 하나만 남겨진 데이터끼리 비교하여 정렬하여 합치고, 이렇게 합쳐진 데이터들끼리 다시 정렬하는 것을 반복한다.

​

병합 정렬의 가장 큰 단점은 메모리 할당에서 나타난다. 데이터가 담긴 배열을 복사하여 그 배열을 저장할 새로운 배열을 만들어야 해서 메모리가 상대적으로 많이 쓰인다. 그래서 공간복잡도가 O(N)가 된다. 이런 경우 오버헤드가 발생하는데, 오버헤드란 코드 자체에서 발생하는 문제가 아닌 프로그램의 실행흐름에서 나타나는 현상으로 간접적으로 추가적인 시간, 메모리, 자원 등이 소요되는 현상이다.

병합 정렬의 장점은 안정 정렬이다. 안정 정렬이란 중복된(동일한) 데이터를 입력 순서와 동일하게 정렬하는 것이다. 순서가 중요한 경우 중복된 값이 뒤바뀌지 않는 안정 정렬을 사용해야 한다.

​

​

​

퀵 정렬

퀵 정렬은 무작위로 선정된 하나의 기준으로 작은 값과 큰 값을 2분할 하여 정렬한다.

기준이 되는 데이터(보통 피벗이라고 함)보다 더 작은 값은 앞으로, 더 큰 값은 뒤로 보내지면서 작은 값들의 배열과 큰 값들의 배열로 분할된다. 그렇게 나눠지는 배열들을 반복적으로 분할해 나가면 결국 배열은 정렬된 상태에 도달한다. 퀵 정렬의 가장 큰 중점은 피벗의 선정 기준이다. 피벗에 따라 정렬 효율이 크게 달라지기 때문이다.

​

퀵 정렬의 단점은 불안정 정렬이라는 것이다. 시간복잡도 상 최악의 경우가 O(N^2)가 될 수 있다는 것이다. 하나의 분할 과정에서 사용되는 기준 값이 중간 값 혹은 중간값과 가까운 값이 되리라는 보장이 없기 때문이다. 즉, 임의로 뽑는 기준 값이 뭐가 되냐에 따라 성능이 달라진다. 만약 제일 앞에 있는 데이터를 기준값으로 삼으려고 하는 경우 987654321이라는 배열을 오름차순으로 정렬할 때 최악의 경우가 된다.