이진 정렬

1. 이진 정렬 알고리즘
2. 이진 정렬 예
3. 이진 정렬 알고리즘 구현
4. 이진 정렬 알고리즘 복잡성

이진 정렬은 비교 유형 정렬 알고리즘입니다. 삽입 정렬 알고리즘의 수정입니다. 이 알고리즘에서 우리는 또한 하나의 정렬 된 하위 배열과 하나의 정렬되지 않은 하위 배열을 유지합니다. 유일한 차이점은 선형 검색 대신 이진 검색을 사용하여 요소의 올바른 위치를 찾는 것입니다. 필요한 비교 횟수를 줄여 정렬 알고리즘을 고정하는 데 도움이됩니다.

이진 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다. 첫 번째 요소A[0]은 이미 정렬되어 있고 정렬 된 하위 배열에 있습니다.

이진 정렬 예

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

• 첫 번째 반복

키 :A[1]= 3

바이너리 검색 : ‘3’의 위치를 ​​인덱스 0으로 반환합니다. 정렬 된 배열의 나머지 요소를 오른쪽으로 이동합니다.

• 두 번째 반복

키 :A[2]= 4

바이너리 검색 : ‘4’의 위치를 ​​색인 1로 반환합니다. 정렬 된 배열의 나머지 요소를 오른쪽으로 이동합니다.

• 세 번째 반복

키 :A[3]= 2

바이너리 검색 : 2의 위치를 색인 0으로 반환합니다. 정렬 된 배열의 나머지 요소를 오른쪽으로 이동합니다.

• 네 번째 반복

키 :A[4]= 1

바이너리 검색 : 1의 위치를 인덱스 0으로 반환합니다. 정렬 된 배열의 나머지 요소를 오른쪽으로 이동합니다.

• 다섯 번째 반복

키 :A[5]= 6

바이너리 검색 : 6의 위치를 색인 5로 반환합니다. 오른쪽에는 요소가 없습니다.

네 번째 반복 후에 정렬 된 배열을 얻습니다-(1 2 3 4 5 6)

이진 정렬 알고리즘 구현

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int a[], int x, int low, int high) {
  if (high <= low) return (x > a[low]) ? (low + 1) : low;

  int mid = (low + high) / 2;

  if (x == a[mid]) return mid + 1;

  if (x > a[mid]) return binarySearch(a, x, mid + 1, high);
  return binarySearch(a, x, low, mid - 1);
}

void binarySort(int a[], int n) {
  for (int i = 1; i < n; ++i) {
    int j = i - 1;
    int key = a[i];
    int pos = binarySearch(a, key, 0, j);
    while (j >= pos) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  binarySort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

이진 정렬 알고리즘 복잡성

시간 복잡성

• 평균 사례

이진 검색은 삽입 정렬에 사용되는 선형 검색의 선형 복잡도 n에 비해 로그 복잡도 ‘로그’가 있습니다. 우리는n 요소에 대해 이진 정렬을 사용하여 시간 복잡성nlogn을 제공합니다. 따라서 시간 복잡도는 [Big Theta]:O(nlogn)의 순서입니다.

• 최악의 경우

최악의 경우는 배열이 역으로 정렬되고 최대 이동 횟수가 필요한 경우에 발생합니다. 최악의 시간 복잡도는 [Big O]:O(nlogn)입니다.

• 베스트 케이스

최상의 경우는 배열이 이미 정렬되어 있고 요소 이동이 필요하지 않을 때 발생합니다. 최적의 시간 복잡도는 [Big Omega]:O(n)입니다.

공간 복잡성

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