[알고리즘 이론] 정렬 Sort - 2-4. 비교 기반 알고리즘 (셸 정렬)

정렬 Sort
1. 기본 개념
2. 비교 기반 알고리즘

   1) 선택 정렬
   2) 버블 정렬
   3) 삽입 정렬
   4) 셸 정렬

---

💡예시에 대한 가정
- 입력 크기 n
- 입력 배열 A[0…. n-1]
- 입력 데이터 : 양의 정수
- 정렬 방식 : 오름차순 (1, 2, 3, 4,…)

 

2-3) 셸 정렬 (Shell sort)

• 삽입 정렬의 단점인 “올바른 삽입 위치에서 멀어도 한자리씩 비교하며 이동” 해야하는 과정을 보완
• 멀리 떨어진 데이터와 비교, 교환하여 한번에 이동할 수 있는 거리를 늘림 → 처리 속도 향상
  1. 삽입 정렬
     처리해야할 데이터에서 가까운 값과 비교 → 점점 멀리
  2. 셸 정렬
     처리해야할 데이터에서 멀리 떨어진 값과 비교 → 점점 가까이
• 입력 배열을 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 줄여가면서 반복적으로 수행
• 부분배열 개수 정하는 방법
  • 순열 (양수 ℎ₁, ⋯ , ℎₖ₋₁ , ℎₖ)
    • ℎₖ의 의미
      • 부분 배열 개수
      • 각 부분배열 내에서 이웃한 데이터 간의 거리

 

 

 

 

 

3. 특징

• 순열에 따라 최선 O(nlogn) ~ 최악 O(n²)
• 사용하는 순열에 따라 성능이 달라짐
  • 가장 좋은 간격을 정하는 것은 미해결 과제이다.
• 순열 값은 역순으로 적용 (ℎₖ₋₁ , ℎₖ, ℎₖ₋₁, … ℎ₁)
• 제자리 정렬 알고리즘 : 입력 배열 A 이외 상수개(i, j, val) 의 저장 공간만 필요
• 안정적이지 않은 알고리즘

 

 

[JS code]

function shellSort(A) {
    const n = A.length; // 배열 A의 길이를 n에 저장합니다.

    for (let D = Math.floor(n / 2); D >= 1; D = Math.floor(D / 2)) { // D: ℎₖ에 해당, 부분배열의 개수 & 간격의 크기
       //=============⬇️ 삽입 정렬 과정=============
        for (let i = D; i < n; i++) { // i를 D부터 n-1까지 증가. 삽입정렬에서는 i=1이었음.
            let val = A[i];
            
            for (let j = i; j >= D && A[j - D] > val; j -= D) { // 간격 D만큼 떨어진 위치에서 삽입 정렬을 수행
                A[j] = A[j - D]; // A[j-D]가 val보다 크면 간격 D만큼 뒤로 이동
            }

            A[j] = val; // 찾아진 위치에 val을 삽입
        }
		//==============⬆️ 삽입 정렬 과정=============
    }

    return A; // 정렬된 배열을 반환합니다.
}