[Algorithm] 셸, 병합, 퀵 정렬

■ 셸 정렬 (Shell Sort)

삽입 정렬을 보완한 알고리즘. Donald L. Shell이란 사람이 제안한 방법이라 셸 정렬임.

 

[삽입 정렬의 문제점]

1. 데이터들이 삽입될 때 이웃한 위치로만 이동하는 것
2. 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있음

[특징]

1. 삽입 정렬의 확장된 개념. 전체 데이터를 한꺼번에 정렬하는 것이 아니라 매개변수를 설정한 후 이 매개변수만큼 떨어져 있는 데이터들을 모아 부분 리스트를 만든 다음 그 매개변수를 줄여가면서 정렬하는 방식

2. 일정한 간격(gap)만큼 떨어져있는 데이터들끼리 부분 리스트를 구성하고 각 부분 리스트에 있는 데이터들을 삽입 정렬하는 작업을 반복

3. 큰 간격에서부터 시작하여 각 단계마다 간격을 줄여감

4. 간격이 줄어들면 하나의 부분 리스트에 속하는 데이터의 개수는 증가

5. 셸 정렬의 마지막 단계에서는 간격을 1로 설정해야 함

6. 간격이 1이 되면 입력 리스트는 한 개의 부분 리스트로 간주되는데 이것을 삽입 정렬하게 되면 셸 정렬이 완료
[간격이 1이되면 '삽입 정렬 == 셸 정렬'이 되어버림]

 

[구현]

 

 

[시간 복잡도]

경우	특징
최선의 경우	O(n^2). but,  삽입 정렬의 시간 복잡도 O(n^2)보다는 개선된 방법
최악의 경우	O(n^1.5)
* 쉘 정렬의 시간 복잡도를 정확히 계산하기 어려운 이유는 가장 좋은 간격을 알아내야 하고 이 간격에 따라 시간 복잡도가 달라질 수 있기 때문

 

■ 병합 정렬 (Merge Sort)

 

기존 데이터를 원소의 개수가 동일한 부분 리스트로 분할하고 분할된 각 부분리스트를 병합하면서 정렬하는 방식
하나의 리스트를 균등한 크기로 반복해서 분할한 뒤 분할된 부분 리스트를 정렬한 다음 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법

 

* 따라서 병합 정렬은 분할 정복(Divide and Conquer) 알고리즘에 해당

[병합 정렬의 분할 정복 과정]

1. 재귀 과정을 반복
2. 하나의 집합으로 합쳐질 때까지 반복
3. 분할 정복 기법 적용

 

[구현]

 

[효율성]

1. 기존 데이터를 원소의 개수가 동일한 부분리스트로 분할하고 분할된 각 부분 리스트를 병합하면서 정렬을 수행하므로 
  이동 및 비교 연산이 평균적으로 O(nlogn)의 효율성을 가진다.

2. 데이터들을 배열로 구성하므로 임시 배열을 위한 추가 메모리 공간이 필요

3. 데이터의 이동 횟수가 많다는 단점이 있으나, 입력 데이터의 상태와 상관없이 병합 정렬의 효율성은 최선, 평균, 최악의 경우 모두 O(nlogn)이기 때문에 효율이 아주 우수한 정렬 방식

 

■ 퀵 정렬 (Quick Sort)

기준을 하나 뽑은 후 기준보다 작은 그룹과 큰 그룹을 나누어 다시 각 그룹으로 정렬하는 방법

[기준 값에 해당하는 피벗(Pivot)을 기준으로 두 데이터의 키값을 비교하여 위치를 교환하는 정렬 방법임]

원래의 문제를 더 작은 크기의 하위 문제로 쪼개어 해결하는 분할 정복 알고리즘에 해당함.

피벗을 기준으로 작거나 같은 데이터는 앞으로 가도록 하고, 피벗보다 큰 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법

오름차순 정렬이라면 왼쪽은 피벗보다 작은 값이, 오른쪽이 피벗보다 큰 값이 오도록 데이터의 위치를 교환

 

[퀵 정렬의 피벗 선택 방법]

1. 전체 데이터 중 가운데 위치한 데이터
2. 첫 번째 데이터
3. 마지막 데이터
4. 별도의 수식을 사용하여 정함

[구현]

 

[시간복잡도]

1. 퀵 정렬은 피벗을 기준으로 두 개의 부분리스트로 나누어 데이터의 위치를 교환하기 때문에 n개의 데이터에 대해 평균 O(nlogn)번 만에 정렬하는 효율성을 가짐

2. n개의 데이터가 균일하게 분포되었다면 정렬 횟수가 1/2, 1/4, 1/8, ... , 1/2^k와 같이 줄어들기 때문에 평균 logn의 연산 횟수가 필요함

3. 다만 매번 정렬할 때마다 모두 n번의 비교가 필요하기 때문에 평균 비교 횟수는 nlogn임

[퀵 정렬의 평균적인 효율성]

 O(nlogn)

=> 평균적으로 매우 빠른 수행속도를 갖는 정렬 방법
=> 데이터의 이동 연산은 비교 연산보다 상대적으로 적게 발생

 * 다른 정렬에 비해서 상당히 빠른 속도이며 특히 정렬할 데이터 양이 많을수록 다른 정렬보다 매우 우수한 성능을 냄

[최악인 경우]

 O(n^2)

=> 피벗에 의해 데이터들을 분할하였을 때 1개와 n-1개와 같이 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우

=> 피벗을 기준으로 나누어지는 두 개의 부분 집합에 계속 불균형이 발생하면 최악의 경우

=> 하지만 이렇게 지속적으로 불균형적으로 부분집합이 발생할 가능성은 매우 희박하기 때문에

 일반적으로 이 정렬은 O(nlogn)이다.