# 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` 순서로 간격을 줄여가면서 정렬을 수행한다.
        
    * 각 단계에서는 주어진 간격을 유지하며 삽입 정렬을 통해 부분 정렬을 수행하게 된다.
        

### <mark>요약:</mark>

* 셀 정렬은 **간격을 점차 줄여가며 삽입 정렬**을 수행하는 정렬 알고리즘이다.
    
* **갭 수열(Gap Sequence)**은 각 단계의 간격을 정의하며, **큰 간격**에서 시작해 **점차 줄여가면서** 정렬을 진행하게 된다.
    
* 이 과정은 삽입 정렬의 효율을 높이고, 최종적으로 전체 배열을 빠르게 정렬할 수 있게 한다.
    

---

### 셀 정렬의 동작 예시

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727952094225/244786c9-4f61-4f2f-92da-0aac9e59d832.png align="center")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727952104109/14f1d7d5-ba30-4055-94d8-b7e79fc3ba38.png align="center")

갭 수열은 {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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727952434553/91a032c4-04eb-4c2f-8677-93ac1be603a9.png align="center")

### 요약:

* 셀 정렬의 의사코드는 `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` 간격으로 나누어진 부분 배열의 정렬을 완료한다.
        

---

### 셀 정렬의 성능

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727954219176/79df3fd9-e22a-4173-bf35-f6afb9537bf8.png align="center")

* 셀 정렬은 **삽입 정렬보다 훨씬 효율적**인 정렬 알고리즘으로, 특히 **큰 데이터셋**에 대해 매우 좋은 성능을 보인다. 이 이미지는 이러한 성능 차이를 설명하며, 셀 정렬이 실용적인 이유를 보여주고 있다.
    
* 셀 정렬은 **갭 수열**과 구현 방식에 따라 수행 시간이 달라지므로 분석이 어렵지만, 일반적으로 `O(n^1.25)`의 성능을 가진다.
    
* 실제 구현 시, **입력 크기**가 커질수록 삽입 정렬에 비해 훨씬 빠른 속도를 보이며, 효율적인 성능을 자랑한다.
    
* 표를 통해 입력 크기 증가에 따른 **셀 정렬과 삽입 정렬**의 성능 차이를 시각적으로 확인할 수 있다.
    

---

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

### 정렬 알고리즘의 안정성  
(Stability of Sorting Algorithms)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727955163372/50f75e79-bc11-4432-bfa5-014516ba82be.png align="center")

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

* **안정성**: 중복된 동일한 `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**)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727955465303/277d1354-66eb-4bb5-913e-308fc168e186.png align="center")

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

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

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

---

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

* 제자리 정렬은 **원소들의 개수에 비해 무시할만한 저장 공간만 추가적으로 사용하는 정렬 알고리즘**을 의미한다.
    
* 즉, 정렬을 수행하면서 **입력 배열 외에 추가적인 메모리 공간**을 거의 사용하지 않으며, **공간 효율성이 높은** 알고리즘이다.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727955536193/aea9d089-9ce9-4493-8eac-1ab1b171f8e3.png align="center")

제자리(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)

**<mark>요약</mark>:**

* 비교 정렬 알고리즘의 **최악의 경우 시간 복잡도**는 최소 `Θ(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)

**<mark>요약:</mark>**

* **비교 정렬의 최적 성능**: `Θ(n log n)`
    
    * 예시: 병합 정렬, 힙 정렬, 퀵 정렬
        
* **비교 연산을 사용하지 않는 경우**: `Θ(n)`
    
    * 예시: 기수 정렬, 계수 정렬, 버킷 정렬
        
* 데이터의 특성과 조건에 따라 **비교 연산을 사용하지 않는 알고리즘**이 더 나은 성능을 발휘할 수 있다.
    

---

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

### 정렬 알고리즘의 실제 성능

**<mark>요약:</mark>**

* **점근적 수행 시간(Asymptotic Execution Time)**은 **큰 입력값**을 기준으로 성능을 표현하므로, **실제 성능과 차이가 있을 수 있다.**
    
* **랜덤으로 동일한 입력값**을 생성하여 **실제 성능을 비교**함으로써, 정렬 알고리즘의 **실제 성능**을 평가하고 선택할 수 있다.
    

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

* **점근적 수행 시간**은 입력의 크기가 **충분히 큰 경우**에 대해 **상수 인자**를 무시하고, 성능을 표현하는 수학적 분석 방법이다.
    
    * 예: `O(n log n)`, `O(n²)` 등.
        
* 하지만, **현실적인 크기의 입력**에서는 점근적 시간 복잡도가 실제 성능을 **정확히 반영하지 않을 수 있다.**
    
    * 실제 수행 시간은 점근적 수행 시간과 **일치하지 않는 경우**가 많다..
        
    * 이는 상수 인자, 캐싱, 메모리 접근 방식 등의 요인 때문이다.
        

**실제 성능 측정 방법**:

* **랜덤으로 동일한 입력값**을 생성하여 여러 정렬 알고리즘을 적용하고, 이를 통해 **실제 성능을 비교**할 수 있다.
    
    * 점근적 수행 시간 대신 **실제 측정된 성능**으로 정렬 알고리즘을 평가할 수 있다.
        
* 이러한 방식은 **실무에서 정렬 알고리즘의 성능을 유지하고 활용**하는 데 유용하다.
    
    * 예를 들어, `O(n log n)` 복잡도의 알고리즘이 `O(n²)` 복잡도의 알고리즘보다 이론적으로는 빠르지만, 작은 입력 크기에서는 `O(n²)` 알고리즘이 더 나을 수 있다.
        

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727956877156/04b5d31d-3480-4a00-8fd7-243e296c3575.png align="center")

**<mark>요약:</mark>**

* 퀵 정렬과 셸 정렬은 큰 입력 크기에서도 좋은 성능을 보여주고 있으며, 셸 정렬은 퀵 정렬보다 시간이 조금 더 많이 소요된다.
    
* 병합 정렬은 메모리 사용량이 많아질 수 있으나, 안정적인 성능을 보여준다.
    
* 힙 정렬도 큰 입력 크기에서 비교적 빠른 성능을 보인다.
    

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

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

* 단위: `μs` (마이크로초) , `ms` (밀리초), `초` (초)
    
* 예: 크기 10⁷일 때, 퀵 정렬은 **0.93초**가 소요되었으며, 셸 정렬은 **1.65초**가 소요됨. 크기 10⁸일 때, 퀵 정렬은 **10.3초**, 셸 정렬은 **23.7초** 소요됨.
    

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

---

**학습정리**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727957640869/647f9b94-7867-4fa2-802c-2ea57964e38f.png align="center")