데이터구조 - (8) 정렬 -2

퀵 정렬

선행 작업을 한 다음 재귀적으로 작은 문제를 해결하는 방식의 정렬이다.

기준 원소를 하나 잡아 작은 원소와 큰 원소 그룹을 나누어 기준 원소의 좌우로 분할하는 방법이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

​

1~4구역까지 나누어 분할하여 정렬을 수행한다.

1구역은 기준 원소보다 작은 원소들 즉 왼쪽,

2구역은 기준 원소보다 크거나 같은 원소들 즉 오른쪽,

3구역은 아직 정해지지 않은 원소들 즉 아래에서 흰 색 부분,

4구역은 기준 원소 부분이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

 

위에서 보면 기준 원소를 정하고 정렬되지 않은 3구역 원소들을 기준 원소와 비교해

1구역과 2구역으로 나누는 과정을 반복한다. 최종적으로 기준 원소를 1구역과 2구역 사이에 배치한다.

이후 1구역과 2구역을 각각 정렬해주면 최종적으로 퀵 정렬이 완성된다.

​

퀵 정렬의 성능은 평균적으로 빅세타 nlogn이며 굉장히 빠른 편이다.

하지만 같은 원소가 많으면 큰 수준으로 성능이 떨어진다.

그렇기에 최악은 빅세타 n^2이다.

​

 

출처 : 쉽게 배우는 자료구조 with 파이썬

partition 함수는 기준 원소를 기준으로 3구역 값들과 비교해

작은 경우 즉 1구역에 추가되야 하는 경우는 1구역을 늘려주고

늘어난 구간에 값을 교환해준다.

​

최종적으로 기준 원소를 1구역과 2구역 사이에 배치해준다.

 

힙 정렬

출처 : 쉽게 배우는 자료구조 with 파이썬

출처 : 쉽게 배우는 자료구조 with 파이썬

처음 힙 구조로 되어있는 것을 최종적으로 루트에 가장 작은 값으로 정렬하는 것을 힙 정렬이라 한다.

(위 기준은 max heap, min heap은 반대로 정렬)

​

출처 : 쉽게 배우는 자료구조 with 파이썬

힙 정렬은 과거에 다루었던 buildHeap, 스며내리기 내용이 포함된다.

우선 주어진 리스트를 힙으로 만들어주고, 스며내리기를 통해 정렬해준다.

코드 자체는 심플하지만, 각각의 동작을 이해하기가 어렵기에 천천히

하나씩 해석하며 이해하는 것이 중요하다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

이외에도 다양한 정렬이 있다.

위 사진은 각 정렬마다 최악, 평균, 최선의 시행일 때의 수행 시간이 어떻게 되는지 나타낸 사진이다.