Tim Sortieren

1. Tim-Sortieralgorithmus
2. Tim Sort Beispiel
3. Implementierung des Tim-Sortieralgorithmus
4. Tim-Sort-Algorithmus Komplexität

Tim sort ist ein hybrider stabiler Sortieralgorithmus. Es ist ein hybrider Algorithmus, der von Insertion Sort und Merge Sort abgeleitet ist. Er sortiert zunächst Subarrays mit Insertion Sort; diese kleinen sortierten Subarrays werden natürliche Läufe genannt. Diese Läufe werden dann mit Hilfe von Merge-Sort in Unterarrays zusammengeführt, um endgültige sortierte Arrays zu erzeugen. Der Algorithmus wurde mit Blick auf die optimale Leistung des Algorithmus bei realen Daten entwickelt. Er nutzt die Tatsache, dass Einfügesortierung bei kleinen Subarrays sehr gut funktioniert. Es ist der Standard-Sortieralgorithmus, der von Javas Array.sort() und Pythons sorted() und sort() verwendet wird.

Tim-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben. Wir betrachten die Größe des Durchlaufs als 32. Sie kann eine beliebige Potenz von 2 sein, da das Zusammenführen effektiver ist, wenn die Zahlen aus Potenzen von 2 bestehen.

TimSort()

Zusammenführen()

Tim Sort Beispiel

Angenommen, wir haben das Array: (3, 5, 2, 8, 1, 7, 6, 4). Wir werden es mit dem Tim-Sortieralgorithmus sortieren. Um die Illustration einfach zu halten, betrachten wir die Größe des Durchlaufs als 4.

Unterteilen Sie das Array in zwei Unterarrays: (3, 5, 2, 8) und (1, 7, 6, 4).

Das erste Subarray: (3, 5, 2, 8)

• Erste Iteration

Schlüssel : A[1] = 5

• Zweite Iteration

Schlüssel : A[2] = 4

• Dritte Iteration

Schlüssel: A[3] = 2

Das zweite Subarray:(1,7,6,4)

• Erste Iteration

Schlüssel : A[1] = 7

• Zweite Iteration

Schlüssel : A[2] = 6

• Dritte Iteration

Schlüssel : A[3] = 4

Mischen Sie die beiden sortierten Subarrays, um das endgültige Subarray als zu erhalten: (1, 2, 3, 4, 5, 6, 7, 8)

Implementierung des Tim-Sortieralgorithmus

#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-Sort-Algorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Der Algorithmus benötigt O(nlogn) Vergleiche, um ein Array mit n Elementen zu sortieren. Daher ist die Zeitkomplexität in der Größenordnung von [Big Theta]: O(nlogn).

• Schlimmster Fall

Im ungünstigsten Fall sind nlogn Vergleiche erforderlich. Die Zeitkomplexität im schlimmsten Fall ist [Big O]: O(nlogn). Sie ist identisch mit der Zeitkomplexität im durchschnittlichen Fall.

• Bester Fall

Der beste Fall tritt ein, wenn das Array bereits sortiert ist und keine Vertauschungen erforderlich sind. Die Zeitkomplexität im besten Fall ist [Big Omega]: O(n).

Raumkomplexität

Die Raumkomplexität für diesen Algorithmus ist O(n), weil der Merge-Sortieralgorithmus zusätzlichen Hilfsraum von O(n) benötigt.