Tim 정렬

Harshit Jindal 2023년10월12일
  1. Tim 정렬 알고리즘
  2. Tim 정렬 예
  3. Tim 정렬 알고리즘 구현
  4. Tim 정렬 알고리즘 복잡성
Tim 정렬

Tim 정렬은 안정적인 하이브리드 정렬 알고리즘입니다. 삽입 정렬 및 병합 정렬에서 파생 된 하이브리드 알고리즘입니다. 먼저 삽입 정렬을 사용하여 하위 배열합니다. 이러한 작은 정렬 하위 배열을 자연 실행이라고합니다. 그런 다음 이러한 실행은 병합 정렬을 사용하여 병합 된 하위 배열로 최종 정렬 된 배열을 생성합니다. 실제 데이터에서 알고리즘의 최적 성능을 염두에두고 설계되었습니다. 삽입 정렬이 작은 하위 배열에서 정말 잘 수행된다는 사실을 사용합니다. Java의Array.sort()와 Python의sorted()sort()에서 사용하는 표준 정렬 알고리즘입니다.

Tim 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다. 런의 크기는 32로 간주합니다. 숫자가 2의 거듭 제곱 일 때 병합이 더 효과적이기 때문에 2의 모든 거듭 제곱이 될 수 있습니다.

TimSort()

  • 배열을n / 32 실행으로 나눕니다.
  • 삽입 정렬을 사용하여 개별 실행을 정렬합니다.
  • 병합 정렬의merge 기능을 사용하여 정렬 된 런을 하나씩 병합합니다.

Merge()

  • 정렬 된 출력을 저장하기 위해 보조 배열 output을 초기화합니다.
  • 3 개의 포인터i,j &k를 초기화합니다.

    i는 첫 번째 하위 배열 beg의 시작을 가리 킵니다.

    j는 두 번째 하위 배열mid + 1의 시작을 가리 킵니다.

    beg로 초기화 된 k는 정렬 된 배열 output의 현재 인덱스를 유지합니다.

  • arr[beg, ...., mid]또는arr[mid + 1, ...., end]하위 배열의 끝에 도달 할 때까지 요소 중에서 더 작은 값을 선택합니다. 인덱스i &j에서output에 삽입합니다.
  • 나머지 요소를 선택하고 배열 중 하나가 소진되면출력에 삽입합니다.
  • outputarr[beg, ..., end]에 복사합니다.

Tim 정렬 예

배열이(3, 5, 2, 8, 1, 7, 6, 4)라고 가정합니다. Tim 정렬 알고리즘을 사용하여 정렬합니다. 그림을 간단하게 유지하기 위해 런의 크기를 4로 간주하겠습니다.

배열을 (3, 5, 2, 8)(1, 7, 6, 4)의 두 하위 배열로 나눕니다.

첫 번째 하위 배열 :(3, 5, 2, 8)

정렬 된 하위 배열 정렬되지 않은 하위 배열 정렬
(삼) (5, 2, 8) (3,5,2,8)
  • 첫 번째 반복

키 :A[1]= 5

정렬 된 하위 배열 정렬되지 않은 하위 배열 정렬
(3, 5) (2, 8) (3, 5, 2, 8)
  • 두 번째 반복

키 :A[2]= 4

정렬 된 하위 배열 정렬되지 않은 하위 배열 정렬
(2, 3, 5) (8) (2, 3, 5, 8)
  • 세 번째 반복

키 :A[3]= 2

정렬 된 하위 배열 정렬되지 않은 하위 배열 정렬
(2, 3, 5, 8) () (2, 3, 5, 8)

두 번째 부분 배열 :(1,7,6,4)

정렬 된 하위 배열 정렬되지 않은 하위 배열 정렬
(1) (7, 6, 4) (1, 7, 6, 4)
  • 첫 번째 반복

키 :A[1]= 7

정렬 된 하위 배열 정렬되지 않은 하위 배열 정렬
(1, 7) (6, 4) (1, 7, 6, 4)
  • 두 번째 반복

키 :A[2]= 6

정렬 된 하위 배열 정렬되지 않은 하위 배열 정렬
(1, 6, 7) (4) (1, 6, 7, 4)
  • 세 번째 반복

키 :A[3]= 4

정렬 된 하위 배열 정렬되지 않은 하위 배열 정렬
(1, 4, 6, 7) () (1, 4, 6, 7)

두 개의 정렬 된 부분 배열을 병합하여 최종 부분 배열을(1, 2, 3, 4, 5, 6, 7, 8)로 얻습니다.

Tim 정렬 알고리즘 구현

#include <bits/stdc++.h>
using namespace std;
const int RUN = 32;

void insertionSort(int arr[], int left, int right) {
  for (int i = left + 1; i <= right; i++) {
    int temp = arr[i];
    int j = i - 1;
    while (j >= left && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
}

void merge(int arr[], int beg, int mid, int end) {
  int output[end - beg + 1];
  int i = beg, j = mid + 1, k = 0;
  // add smaller of both elements to the output
  while (i <= mid && j <= end) {
    if (arr[i] <= arr[j]) {
      output[k] = arr[i];
      k += 1;
      i += 1;
    } else {
      output[k] = arr[j];
      k += 1;
      j += 1;
    }
  }
  // remaining elements from first array
  while (i <= mid) {
    output[k] = arr[i];
    k += 1;
    i += 1;
  }
  // remaining elements from the second array
  while (j <= end) {
    output[k] = arr[j];
    k += 1;
    j += 1;
  }
  // copy output to the original array
  for (i = beg; i <= end; i += 1) {
    arr[i] = output[i - beg];
  }
}
void timSort(int arr[], int n) {
  for (int i = 0; i < n; i += RUN)
    insertionSort(arr, i, min((i + 31), (n - 1)));

  for (int size = RUN; size < n; size = 2 * size) {
    for (int left = 0; left < n; left += 2 * size) {
      int mid = left + size - 1;
      int right = min((left + 2 * size - 1), (n - 1));

      merge(arr, left, mid, right);
    }
  }
}

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";
  timSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Tim 정렬 알고리즘 복잡성

시간 복잡성

  • 평균 사례

알고리즘은n 요소의 배열을 정렬하기 위해O(nlogn)비교를 필요로합니다. 따라서 시간 복잡도는 [Big Theta] :O(nlogn)의 순서입니다.

  • 최악의 경우

최악의 경우nlogn 비교가 필요합니다. 최악의 시간 복잡성은 [Big O] : O(nlogn)입니다. 평균 케이스 시간 복잡성과 동일합니다.

  • 베스트 케이스

최상의 경우는 어레이가 이미 정렬되어 있고 교체가 필요하지 않은 경우에 발생합니다. 최적의 시간 복잡도는 [Big Omega] :O(n)입니다.

공간 복잡성

이 알고리즘의 공간 복잡도는 O(n)입니다. 병합 정렬 알고리즘에 O(n)의 추가 보조 공간이 필요하기 때문입니다.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

관련 문장 - Sort Algorithm