[100] 알고리즘 05차시 효율적인 정렬 알고리즘

1. 쉘 정렬(Shell Sort)

가. 개념

주어진 입력 데이터를 적당한 매개 변수의 값만큼 서로 떨어진 데이터들과 비교하여 교환하는 과정을 매개 변수의 값을 바꾸어가며 되풀이하는 것

영역을 나눈 후 삽입하는 보완된 삽입 정렬 개념

입력 파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 삽입 정렬 방식으로 배열하는 과정을 반복하는 정렬 방식

이때 서로 떨어져 있는 데이터들은 하나의 부분 리스트를 구성하며 삽입 정렬에 의해 개별적으로 정렬됨.

먼저 적절한 매개 변수의 값을 선택한 후 점차 감소시켜 가면서 쉘 정렬을 수행하고 매개 변수의 값이 1이 될 때 종료함.

나. 쉘 정렬 복잡도

쉘 정렬은 최악 경우(Worst Case)의 시간복잡도가 \(O(n^{2})\)

쉘 정렬의 수행 속도는 간격 선정에 따라 좌우됨.

다. 쉘 정렬의 특징

쉘 정렬은 입력 크기가 매우 크지 않은 경우에 매우 좋은 성능을 보임.

쉘 정렬은 임베디드 시스템에서 주로 사용되는데 쉘 정렬의 특징인 간격에 따른 그룹별 정렬 방식이 하드웨어로 정렬 알고리즘을 구현하는데 매우 적합하기 때문

https://ko.wikipedia.org/wiki/셸_정렬

셸 정렬 - 위키백과, 우리 모두의 백과사전

2. 병합 정렬(Merge Sort)

가. 개념

정렬할 데이터들을 2개로 나누고 2개로 나뉜 데이터들을 각각 정렬한 다음에 다시 합병하여 하나의 정렬된 데이터들로 완성하는 방법

이미 정렬되어 있는 두 개의 파일을 1개의 파일로 합병하는 정렬 방식으로 1개의 파일에서는 각각의 데이터를 하나의 파일로 취급하여 정렬함.

나. 수행시간

\(O(n\log{n})\)

https://ko.wikipedia.org/wiki/합병_정렬

합병 정렬 - 위키백과, 우리 모두의 백과사전

3. 퀵 정렬(Quick Sort)

가. 개념

기준 키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법

평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘

나.  퀵 정렬 복잡도

1) 평균 수행 시간(Average Case)

\(O(n\log{n})\)

2) 최악 수행 시간(Worst Case)

\(O(n^{2})\)

https://ko.wikipedia.org/wiki/퀵_정렬

퀵 정렬 - 위키백과, 우리 모두의 백과사전