[알고리즘] 정렬(선택, 삽입, 퀵, 계수)

선택 정렬

(필자는 '최소값 정렬'이란 이름도 직관적이라 생각한다.)

 

정렬 과정

1. 주어진 리스트 중 가장 작은 값을 탐색한다.

2. 첫 번째 원소와 해당 값을 교체한다(exchange)

3. 첫 번째 원소를 제외하고 1~2를 반복한다. 하나의 원소가 남으면 종료한다.

 

위키피디아의 선택 정렬 애니메이션

 

시간 복잡도

n개의 리스트 중 최소값을 찾는 연산은 n-1번의 비교 연산이 필요.

선택 정렬을 진행하면서 비교해야할 원소가 1개씩 줄어들기 때문에 연산 횟수는

(n-1) + (n-2) + ... + 2 + 1= ((n-1)*n/2) = O(n^2)

 

특징

1. 자료 이동 횟수가 미리 결정된다.

2. 안정성을 만족하지 않는다. (같은 값에 대해 순서가 바뀔 수 있음.)

삽입 정렬

(필자는 '카드 정렬'이란 이름도 직관적이라 생각한다.)

 

정렬 과정

0. 좌측에서 부터 우측으로 index를 증가시키며 정렬을 진행한다.

1. index 증가 후 만나는 숫자를 왼쪽의 리스트의 알맞은 위치에 '삽입'시킨다. 

1-1. 1번을 진행하므로서, index보다 작은 숫자의 리스트(index의 좌측)은 늘 정렬된 상태이다.

2.  index가 해당 리스트의 끝까지 도착한다면 정렬이 완료된다.

위키피디아의 삽입 정렬 애니메이션

시간 복잡도

최선의 경우(모든 레코드가 정렬되어 있는 경우)

교환이 없고 비교만 n번 진행한다.(index와 index-1)

O(n)

 

최악의 경우(입력 자료가 역순일 경우)

비교횟수: n-1 + n-2 + ... + 2 + 1 = n(n-1)/2 O(n^2)

교환 횟수: n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O(n^2) (제대로 이해 x)

특징

1. 이미 정렬된 리스트에서 매우 빠르다 (O(n))(퀵 소트와 반대)

2. 리스트가 길어질 수록 불리해진다.

3. 레코드들의 이동이 비교적 많다.

 

퀵  정렬

(필자는 '중앙 정렬', '피벗 정렬' 이란 이름이 붙었으면 좀 더 직관적이었을 것 같다.)

 

정렬 과정

1. 양 끝 중 하나의 숫자를 정하고 이를 pivot으로 정한다.)

2. 리스트의 양 끝단에서 high, low가 중앙으로 이동하면서 pivot과 값을 비교하고, 크면 오른쪽, 작으면 왼쪽으로 정렬한다(방향은 바뀔 수 있다)

3. high와 low가 서로 교차하면 이동을 중단하고, pivot과 가까운 쪽의 high/low가 pivot과 교체 된다. 서로 한 숫자에서 만났다면, 해당 숫자와 pivot을 교체하면 된다.

4. pivot을 기준으로 나누어진 좌, 우측 숫자 리스트에 대해서 각각 1~4를 적용한다. 리스트의 길이가0 또는 1이 되면 중단한다.

위키피디아의 퀵 소트 설명. i가 low, j 가 high에 대응된다.

시간 복잡도

순환 호출의 깊이: n개를 2개씩 분할 하므로, log2n (최악: n)

각 호출 별 비교 연산: n

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

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

 

특징

1. 한 번 정렬된 pivot의 위치는 정확하다

2. 이미 정렬된 리스트에 대해서 성능이 좋지 않다.

3. 빠르다

 

계수 정렬

정렬 과정

1. 각 숫자가 몇 번 나오는지를 카운트한다.

2. 각 숫자를 순서대로, 카운트만큼 정렬한다.

 

 

시간 복잡도

O(n)

비교도, 교환도 없다. n번을 돌면서 미리 저장한 공간에 저장한다.

 

특징

1. 메모리 공간을 미리 구현해야하므로 리스트의 최대 숫자값만큼의 길이의 리스트가 필요하다.

2. 최대 숫자가 너무 크면 미리 구현해놓을 리스트가 매우 크게 된다(메모리 공간을 많이 잡아야한다.)

3. 공간 복잡도를 손해를 보고 시간 복잡도를 이득을 본다.

 

 

선택 정렬

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

삽입 정렬
https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

 

퀵 정렬

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

계수 정렬

https://velog.io/@chappi/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-6%EC%9D%BC%EC%B0%A8-On-%EC%A0%95%EB%A0%AC-%EA%B3%84%EC%88%98-%EC%A0%95%EB%A0%AC

https://en.wikipedia.org/wiki/Counting_sort