Shell sort, Performance comparison between sorting algorithms (3/3)

---

Contents

1️⃣ 셀 정렬(Shell sort)
2️⃣ 정렬 알고리즘의 성질 (Sorting Algorithms)
3️⃣ 정렬 알고리즘간 성능 비교

---

1️⃣ 셀 정렬(Shell sort)

셀 정렬(Shell sort)이 나오게 된 배경

• 삽입 정렬의 장점 활용:

  • 삽입 정렬은 평균적으로 Θ(n²)의 시간 복잡도를 가지지만, 이미 거의 정렬된 배열에 대해서는 Θ(n)의 시간으로 정렬을 수행할 수 있다.

  • 이 장점을 활용하려면, 새로운 원소를 정렬된 부분 배열에 삽입할 때 위치가 가까워야 효율적이다.

  • 셀 정렬은 이를 위해 원소들을 미리 정렬된 부분 상태로 만들기 위한 사전 작업을 수행한다.

• 셀 정렬의 핵심 아이디어:

  • 각 원소가 최종적으로 있어야 할 자리에서 멀리 떨어지지 않도록 하는 것이 셀 정렬의 핵심 아이디어이다.

  • 즉, 정렬되지 않은 배열을 일정 간격(gap)으로 분할하여 부분적으로 정렬하고, 이 간격을 점점 줄여가면서 정렬하는 방식이다.

  • 이를 통해 최종적으로 정렬할 때 삽입 정렬의 최적 성능을 유도할 수 있게 된다.

---

셀 정렬의 개념

• 셀 정렬은 일정한 간격으로 배열의 원소들을 추출하여 삽입 정렬을 수행하고, 이 간격을 점차 줄여나가며 최종적으로 간격이 1일 때 배열을 완전히 정렬하는 알고리즘이다.

셀 정렬의 특징

• 초기에는 큰 간격으로 원소를 정렬하여 전체적인 정렬 상태를 어느 정도 갖추게 한 다음, 간격을 줄여가면서 정밀하게 정렬한다.

• 간격이 1이 되었을 때, 배열은 이미 부분적으로 정렬된 상태이므로, 삽입 정렬이 O(n) 시간 복잡도로 매우 빠르게 수행될 수 있게된다.

셀 정렬의 갭 수열(Gap Sequence)

• 갭 수열은 각 단계에서 삽입 정렬을 수행할 때 원소들을 비교할 간격(h)을 정의하는 수열이다.

• h₀, h₁, h₂, ..., 1과 같은 형태를 가지며, 일반적으로 아래와 같은 특성을 가진다.

  • 점차 줄어드는 간격: hₙ < hₙ₋₁ (간격이 점차 줄어드는 형태)

  • 중복되지 않는 간격: 수열 값들이 서로 배수 관계가 아니며, 약수 관계도 아니도록 하여 중복되는 값을 피함.

  • 수열의 마지막 값은 1: 마지막 단계에서는 간격이 1이 되어 모든 원소가 서로 인접한 위치에 있게 되므로, 전체 배열을 완전히 정렬하게 된다.

예시

• 갭 수열의 예시: {31, 15, 7, 3, 1}

  • 이 수열에서는 초기 간격이 31이며, 이후 15, 7, 3, 1 순서로 간격을 줄여가면서 정렬을 수행한다.

  • 각 단계에서는 주어진 간격을 유지하며 삽입 정렬을 통해 부분 정렬을 수행하게 된다.

요약:

• 셀 정렬은 간격을 점차 줄여가며 삽입 정렬을 수행하는 정렬 알고리즘이다.

• 갭 수열(Gap Sequence)은 각 단계의 간격을 정의하며, 큰 간격에서 시작해 점차 줄여가면서 정렬을 진행하게 된다.

• 이 과정은 삽입 정렬의 효율을 높이고, 최종적으로 전체 배열을 빠르게 정렬할 수 있게 한다.

---

셀 정렬의 동작 예시

갭 수열은 {7, 3, 1}

1. 초기 배열 (a):

   • 정렬할 배열 A는 [15, 31, 65, 73, 8, 66, 11, 3, 20, 48, 29, 1, 33, 25, 4]로 주어져 있다.

   • 이 배열의 원소들을 정렬하기 위해 갭 수열 {7, 3, 1}이 사용되었다.

2. 7 간격 떨어진 원소들끼리 정렬 (b):

   • 7 간격으로 떨어진 원소들끼리 부분 배열을 이루고, 이 부분 배열들을 각각 삽입 정렬을 수행한다.

   • 예를 들어, 첫 번째 7 간격 부분 배열은 [15, 3]이며, 이를 정렬하면 [3, 15]가 된다.

   • 다른 7 간격 부분 배열들도 각각 [31, 20], [65, 48], [73, 29], [8, 1], [66, 33], [11, 25]이며, 이를 각각 정렬하여 아래와 같은 정렬된 부분 배열을 얻는다..

   • 정렬 후 배열 상태: [3, 20, 48, 29, 1, 33, 25, 15, 65, 73, 8, 66, 11, 4, 73]

3. 3 간격 떨어진 원소들끼리 정렬 (c):

   • 다음 단계에서는 3 간격으로 떨어진 원소들끼리 부분 배열을 이루어 삽입 정렬을 수행한다.

   • 예를 들어, 첫 번째 3 간격 부분 배열은 [3, 1, 11, 4, 25]이며, 이를 정렬하면 [1, 3, 4, 11, 25]가 된다.

   • 다른 3 간격 부분 배열들도 각각 정렬되어 부분적으로 배열이 정렬된 상태가 된다.

   • 정렬 후 배열 상태: [3, 1, 48, 11, 4, 29, 25, 20, 8, 31, 33, 65, 66, 73, 73]

4. 1 간격(전체 정렬) 수행 (d):

   • 마지막으로 1 간격을 사용하여 전체 배열을 정렬한다.

   • 이는 기존의 삽입 정렬을 수행하여 전체 배열을 완전히 정렬하는 단계이다.

   • 배열은 이미 부분적으로 정렬된 상태이므로, 삽입 정렬의 시간 복잡도는 O(n)에 가깝게 최적화된다.

   • 최종 정렬된 배열: [1, 3, 4, 8, 11, 15, 20, 25, 29, 31, 33, 48, 65, 66, 73]

---

셀 정렬의 의사코드1

요약:

• 셀 정렬의 의사코드는 shellSort 함수와 stepInsertionSort 함수를 이용하여 간격(h)을 기준으로 부분적으로 정렬을 수행한 후, 최종적으로 전체 배열을 정렬된 상태로 만든다.

• 각 간격(h)은 갭 수열에 따라 점차 줄어들며, 마지막 간격이 1이 되면 전체 배열이 정렬된다

---

의사코드 단계별 설명:

1. shellSort(A[]) 함수:

   • 주어진 배열 A와 갭 수열(h₀, h₁, ..., 1)을 이용하여 정렬을 수행한다.

   • 갭 수열의 각 값 h에 대해, h 간격으로 나누어진 부분 배열을 stepInsertionSort 함수를 이용하여 정렬한다.

2. stepInsertionSort(A[], k, h) 함수:

   • k부터 시작하여 h 간격으로 나누어진 원소들 [A[k], A[k+h], A[k+2h], ...]을 삽입 정렬한다.

   • 예를 들어, k=0이고 h=3일 경우, 배열은 [A[0], A[3], A[6], A[9], ...]과 같은 형태로 나누어지게 된다.

3. 정렬 과정:

   • 외부 루프: i = k+h부터 시작하여 i를 h씩 증가시키며 배열의 끝까지 이동한다.

   • 내부 루프: newItem을 A[i]로 설정하고, newItem이 이전 원소(A[j])보다 작을 경우, A[j]의 값을 한 칸 오른쪽(A[j+h])으로 이동시킨다.

   • 내부 루프가 끝나면, A[j+h]에 newItem을 배치하여 h 간격으로 나누어진 부분 배열의 정렬을 완료한다.

---

셀 정렬의 성능

• 셀 정렬은 삽입 정렬보다 훨씬 효율적인 정렬 알고리즘으로, 특히 큰 데이터셋에 대해 매우 좋은 성능을 보인다. 이 이미지는 이러한 성능 차이를 설명하며, 셀 정렬이 실용적인 이유를 보여주고 있다.

• 셀 정렬은 갭 수열과 구현 방식에 따라 수행 시간이 달라지므로 분석이 어렵지만, 일반적으로 O(n^1.25)의 성능을 가진다.

• 실제 구현 시, 입력 크기가 커질수록 삽입 정렬에 비해 훨씬 빠른 속도를 보이며, 효율적인 성능을 자랑한다.

• 표를 통해 입력 크기 증가에 따른 셀 정렬과 삽입 정렬의 성능 차이를 시각적으로 확인할 수 있다.

---

2️⃣ 정렬 알고리즘의 성질

정렬 알고리즘의 안정성

(Stability of Sorting Algorithms)

정렬 알고리즘의 안정성 정의:

• 안정성: 중복된 동일한 key를 원래의 순서대로 정렬하는 성질을 의미한다.

  • 예를 들어, 두 개의 동일한 key를 가진 요소가 있을 때, 정렬 후에도 이 두 요소의 순서가 바뀌지 않으면 해당 정렬 알고리즘은 안정적이라고 할 수 있다.

정렬 후 설명

• 나이(key) 기준으로 오름차순 정렬을 수행했을 때, 동일한 나이를 가진 사람들(21살, 25살)이 원래의 순서를 유지하고 있다.

• 예를 들어, 21살의 김동수와 한남길의 순서가 정렬 후에도 유지되었고, 25살의 나한석, 문석철, 박진호도 원래 순서를 그대로 유지했다.

• 이를 통해 해당 정렬 알고리즘이 안정적임을 알 수 있다.

정렬 알고리즘 안정성의 중요성

(Importance of Stability in Sorting Algorithms)

• 기수 정렬(Radix Sort)에서 안정성의 활용:

  • 기수 정렬은 자릿수를 하나씩 증가시키면서 정렬을 수행하는 알고리즘.

  • 이때 기존 정렬을 보존하는 안정성이 중요한 성질로 활용된다.

  • 예를 들어, 일의 자리, 십의 자리, 백의 자리 등 여러 자릿수를 반복적으로 정렬할 때, 이전 자릿수의 정렬 결과가 유지되어야 올바른 최종 정렬 결과를 얻을 수 있다.

• 복수개의 key로 반복 정렬 시 안정성 필요:

  • 데이터가 **복수개의 key**를 가지고 있고, 이를 여러 번 반복해서 정렬할 때, 안정적인 정렬이 필요하다.

  • 예를 들어, 먼저 이름을 기준으로 정렬한 후, 다시 나이를 기준으로 정렬할 때, 이름의 순서가 유지되길 원한다면 안정 정렬이 필요하다.

• 정렬할 개체들이 key 외에 여러 항목이 있을 때:

  • 정렬할 데이터가 key 외에도 여러 개의 속성(예: 이름, 나이, 주소 등)을 가질 경우, **특정 key**를 기준으로 정렬하되, 기존 순서를 유지해야 하는 경우가 있다.

  • 이럴 때 안정적인 정렬 알고리즘을 사용해야 여러 속성의 원래 순서가 보장될 수 있다.

안정 절렬과 불안정 정렬

(Stable Sorting and Unstable Sorting)

안정 정렬은 동일한 값을 가진 원소들이 정렬 후에도 원래의 순서를 유지하는 정렬 알고리즘이다.

불안정 정렬은 동일한 값을 가진 원소들의 순서가 바뀔 수 있는 정렬 알고리즘이다.

안정성과 불안정성은 데이터의 순서 유지 여부에 따라 정렬 알고리즘의 선택에 중요한 요소가 될 수 있다. 예를 들어, 안정성이 필요한 경우에는 버블 정렬, 삽입 정렬, 병합 정렬 등을 사용하며, 그렇지 않은 경우에는 선택 정렬이나 퀵 정렬을 사용할 수 있다.

---

제자리 알고리즘(In-place Algorithm) 정의

• 제자리 정렬은 원소들의 개수에 비해 무시할만한 저장 공간만 추가적으로 사용하는 정렬 알고리즘을 의미한다.

• 즉, 정렬을 수행하면서 입력 배열 외에 추가적인 메모리 공간을 거의 사용하지 않으며, 공간 효율성이 높은 알고리즘이다.

제자리(In-peach) 정렬을 수행하면서 입력 배열의 요소들을 교환하는 방식으로 진행하며, 추가적인 배열이나 리스트를 생성하지 않는다.

---

비제자리 정렬(Non In-place Algorithm)의 예:

• 병합 정렬 (Merge Sort):

  • 정렬을 수행하기 위해 추가적인 배열이 필요하다.

  • 각 단계에서 병합을 수행할 때, 새로운 배열 공간을 사용하여 원소들을 합친다.

• 기수 정렬 (Radix Sort):

  • 자릿수를 기준으로 여러 번 정렬을 수행하며, 각 자릿수를 저장할 큐나 리스트 등의 추가 공간을 사용한다.

• 계수 정렬 (Counting Sort):

  • 원소의 개수를 저장하기 위해 추가적인 배열 공간을 사용한다.

• 버킷 정렬 (Bucket Sort):

  • 원소들을 담을 버킷(리스트 또는 배열)을 사용하여 정렬한다.

제자리 정렬과 비제자리 정렬의 차이:

• 제자리 정렬 (In-place):

  • 추가적인 메모리 공간을 거의 사용하지 않음.

  • 공간 복잡도가 매우 낮음.

  • 배열 내에서 교환과 삽입 등을 통해 정렬을 수행.

• 비제자리 정렬 (Non In-place):

  • 정렬을 위해 추가적인 메모리 공간이 필요.

  • 원소를 정렬할 때 추가 배열이나 리스트 등을 사용하여 정렬.

  • 공간 복잡도가 상대적으로 높음.

요약:

• 제자리 정렬은 정렬을 수행하면서 추가적인 메모리 공간을 거의 사용하지 않는 공간 효율적인 알고리즘.

• 비제자리 정렬은 추가적인 배열이나 리스트 등의 메모리 공간을 사용하여 정렬을 수행

• 제자리 정렬과 비제자리 정렬의 선택은 공간 복잡도와 성능 요구 사항에 따라 달라짐

---

비교 정렬 시간의 하한

(Lower Bound of Comparison-based Sorting Time)

요약:

• 비교 정렬 알고리즘의 최악의 경우 시간 복잡도는 최소 Θ(n log n)이다.

• 이보다 더 빠른 시간 복잡도를 가지는 비교 기반 정렬 알고리즘은 존재하지 않는다.

• Θ(n log n)은 결정 트리의 탐색 시간에 의해 결정되며, 모든 비교 정렬이 이 하한을 따른다.

비교 정렬(Comparison-Based Sorting) 정의:

• 비교 정렬은 두 원소를 비교하는 연산을 기반으로 정렬을 수행하는 알고리즘이다.

• 예를 들어, A와 B 두 원소를 비교하여 A > B인지 A < B인지 판단하는 연산을 통해 순서를 정한다.

비교 정렬 하한의 정리:

1. 결정 트리(Decision Tree) 탐색으로 설명:

   • 정렬을 이진 결정 트리에서의 탐색으로 볼 때, 결정 트리의 말단 노드는 주어진 배열의 가능한 모든 순열로 표현된다.

   • 배열의 모든 가능한 순열은 n! (n 팩토리얼)의 가지수를 가진다.

2. 결정 트리의 깊이 탐색:

   • 루트 노드에서 말단 노드까지 탐색하는데 log(n!)의 시간이 걸린다.

   • 이를 통해 정렬 알고리즘이 최악의 경우 Θ(n log n)의 시간 복잡도를 가짐을 알 수 있다.

3. 스털링(Stirling) 근사식 활용:

   • 스털링 근사식에 따르면 log(n!) = Θ(n log n)이 된다.

   • 이를 통해 비교 정렬 알고리즘의 최소 수행 시간이 Θ(n log n)임을 수학적으로 증명할 수 있게된다.

---

최적의 정렬 알고리즘

(Optimal Sorting Algorithm)

요약:

• 비교 정렬의 최적 성능: Θ(n log n)

  • 예시: 병합 정렬, 힙 정렬, 퀵 정렬

• 비교 연산을 사용하지 않는 경우: Θ(n)

  • 예시: 기수 정렬, 계수 정렬, 버킷 정렬

• 데이터의 특성과 조건에 따라 비교 연산을 사용하지 않는 알고리즘이 더 나은 성능을 발휘할 수 있다.

---

3️⃣ 정렬 알고리즘간 성능 비교

정렬 알고리즘의 실제 성능

요약:

• 점근적 수행 시간(Asymptotic Execution Time)은 큰 입력값을 기준으로 성능을 표현하므로, 실제 성능과 차이가 있을 수 있다.

• 랜덤으로 동일한 입력값을 생성하여 실제 성능을 비교함으로써, 정렬 알고리즘의 실제 성능을 평가하고 선택할 수 있다.

점근적 수행 시간 분석(Asymptotic Execution Time Analysis)

• 점근적 수행 시간은 입력의 크기가 충분히 큰 경우에 대해 상수 인자를 무시하고, 성능을 표현하는 수학적 분석 방법이다.

  • 예: O(n log n), O(n²) 등.

• 하지만, 현실적인 크기의 입력에서는 점근적 시간 복잡도가 실제 성능을 정확히 반영하지 않을 수 있다.

  • 실제 수행 시간은 점근적 수행 시간과 일치하지 않는 경우가 많다..

  • 이는 상수 인자, 캐싱, 메모리 접근 방식 등의 요인 때문이다.

실제 성능 측정 방법:

• 랜덤으로 동일한 입력값을 생성하여 여러 정렬 알고리즘을 적용하고, 이를 통해 실제 성능을 비교할 수 있다.

  • 점근적 수행 시간 대신 실제 측정된 성능으로 정렬 알고리즘을 평가할 수 있다.

• 이러한 방식은 실무에서 정렬 알고리즘의 성능을 유지하고 활용하는 데 유용하다.

  • 예를 들어, O(n log n) 복잡도의 알고리즘이 O(n²) 복잡도의 알고리즘보다 이론적으로는 빠르지만, 작은 입력 크기에서는 O(n²) 알고리즘이 더 나을 수 있다.

정렬 알고리즘 간 실제 성능 비교

요약:

• 퀵 정렬과 셸 정렬은 큰 입력 크기에서도 좋은 성능을 보여주고 있으며, 셸 정렬은 퀵 정렬보다 시간이 조금 더 많이 소요된다.

• 병합 정렬은 메모리 사용량이 많아질 수 있으나, 안정적인 성능을 보여준다.

• 힙 정렬도 큰 입력 크기에서 비교적 빠른 성능을 보인다.

점근적 평균 복잡도: 각 알고리즘의 이론적인 시간 복잡도를 의미한다.

입력 크기 별 실제 수행 시간: 다양한 입력 크기 (크기 10³, 10⁴, 10⁵, 10⁷, 10⁸)에 대한 각 알고리즘의 실제 수행 시간이 표시되어 있다.

• 단위: μs (마이크로초) , ms (밀리초), 초 (초)

• 예: 크기 10⁷일 때, 퀵 정렬은 0.93초가 소요되었으며, 셸 정렬은 1.65초가 소요됨. 크기 10⁸일 때, 퀵 정렬은 10.3초, 셸 정렬은 23.7초 소요됨.

특이 사항: 일부 정렬 알고리즘은 큰 입력 크기(10⁷, 10⁸)에 대해 N/A 또는 Overflow가 표시되어 있다. 이는 해당 알고리즘이 너무 오래 걸리거나, 메모리 부족으로 인해 수행이 불가능했음을 의미한다.

---

학습정리