빗 정렬

1. 빗 정렬 알고리즘
2. 콤 정렬 예
3. Comb Sort 알고리즘 구현
4. 조합 정렬 알고리즘 복잡성

콤 정렬은 간단한 비교 기반 정렬 알고리즘입니다. 버블 정렬의 개선 된 형태입니다. 버블 정렬에서 인접한 요소는 각 통과 / 단계에서 비교되고 반전을 하나씩 제거합니다. 반면에 콤 정렬은 큰 간격을 사용하여 시작하여 ‘1.3’의 축소 계수로 매번 줄입니다. Comb Sort는 단 한 번의 스왑으로 여러 반전을 제거 할 수 있습니다. 그것은 거북이를 죽이는 아이디어에 기초합니다. 거북이는 목록 끝 부분에있는 작은 요소로, 버블 정렬의 효율성을 낮추고 제거하면 정렬 성능이 크게 향상됩니다.

빗 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다. 축소 계수는 경험적으로 최상의 결과를 제공하는 것으로 확인되었으므로 ‘1.3’으로 간주합니다.

콤 정렬 예

배열이(3, 5, 2, 8, 1, 7, 6, 4)라고 가정합니다. Comb 정렬 알고리즘을 사용하여 정렬합니다.

gap = 8,swapped =true 및SHRINK_FACTOR =1.3을 초기화합니다.

• 첫 번째 패스

갭= 8 / 1.3 = 6,스왑 됨=false

• 두 번째 패스

갭= 6 / 1.3 = 4,스왑 됨=false

• 세 번째 패스

갭= 4 / 1.3 = 3,스왑 됨=false

• 네 번째 패스

갭= 3 / 1.3 = 2,스왑 됨=false

• 다섯 번째 패스

갭= 2 / 1.3 = 1,스왑 됨=false

최종 정렬 된 배열을(1, 2, 3, 4, 5, 6, 7, 8)로 얻습니다.

Comb Sort 알고리즘 구현

#include <iostream>
using namespace std;

int updateGap(int gap) {
  gap = (gap * 10) / 13;
  if (gap < 1)
    return 1;
  else
    return gap;
}

void combSort(int arr[], int n) {
  int gap = n;
  bool swapped = true;
  while (gap > 1 || swapped == true) {
    gap = updateGap(gap);
    swapped = false;
    for (int i = 0; i < (n - gap); i++) {
      int temp;
      if (arr[i] > arr[i + gap]) {
        temp = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = temp;
        swapped = true;
      }
    }
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  combSort(arr, n);
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

조합 정렬 알고리즘 복잡성

시간 복잡성

• 평균 사례

시간 복잡도는 [Big Theta] : O(n²/ 2 ^p)의 순서입니다. 여기서p는 증분 수입니다.

• 최악의 경우

최악의 경우 시간 복잡도는 [Big O] : O(n²)입니다.

• 베스트 케이스

가장 좋은 경우는 배열이 이미 정렬되었거나 거의 정렬되었을 때 발생합니다. 최적의 시간 복잡도는 [Big Omega] :O(nlogn)입니다. 버블 정렬의 최상의 경우 시간 복잡성에 비해 크게 개선되었습니다.

공간 복잡성

이 알고리즘의 공간 복잡성은 O(n)입니다. 콤 정렬 알고리즘은 임시 변수 외에 추가 공간이 필요하지 않기 때문입니다.