Tim Sort Algorithm ใน C ++

Timsort เป็นอัลกอริธึมการเรียงลำดับที่เสถียรซึ่งใช้แนวคิดของการเรียงลำดับการผสานและการเรียงลำดับการแทรก นอกจากนี้ยังสามารถเรียกได้ว่าเป็นอัลกอริธึมไฮบริดของการเรียงลำดับการแทรกและการผสาน มีการใช้กันอย่างแพร่หลายในอัลกอริธึมการจัดเรียงแบบฝังใน Java, Python, C และ C++ แนวคิดเบื้องหลังอัลกอริธึมนี้คือการจัดเรียงชิ้นเล็ก ๆ โดยใช้การเรียงลำดับการแทรก แล้วรวมชิ้นใหญ่ทั้งหมดโดยใช้ฟังก์ชันผสานของอัลกอริธึมการจัดเรียงการผสาน

การทำงาน

ในอัลกอริทึมนี้ อาร์เรย์จะแบ่งออกเป็นส่วนเล็กๆ ชิ้นนี้เรียกว่า RUN แต่ละ RUN จะถูกถ่ายและจัดเรียงโดยใช้เทคนิคการเรียงลำดับแบบแทรก หลังจากที่ RUN ถูกจัดเรียงแล้ว สิ่งเหล่านี้จะถูกผสานโดยใช้ฟังก์ชันผสาน

อาจมีกรณีที่ขนาดของอาร์เรย์อาจน้อยกว่า RUN ในกรณีเช่นนี้ อาร์เรย์จะถูกจัดเรียงตามเทคนิคการเรียงลำดับการแทรก โดยปกติกลุ่ม RUN จะแตกต่างกันไปตั้งแต่ 32 ถึง 64 ขึ้นอยู่กับขนาดของอาร์เรย์ ฟังก์ชันผสานจะผสานก็ต่อเมื่อส่วนย่อยของอาร์เรย์ย่อยมีขนาดกำลัง 2

ข้อดีของการใช้การเรียงลำดับการแทรกคือการเรียงลำดับการแทรกทำงานได้ดีสำหรับอาร์เรย์ที่มีขนาดเล็ก

ความซับซ้อนของเวลา −

• เคสที่ดีที่สุด - Omega(n)

• กรณีเฉลี่ย - O(nlogn)

• กรณีที่เลวร้ายที่สุด - O(nlogn)

อัลกอริทึมของ Tim Sort

• เริ่มต้น RUN ด้วยขนาด 32

• ใช้การเรียงลำดับการแทรกสำหรับชิ้นส่วนขนาด RUN

• การรวมฟังก์ชัน (int arr[], int l, int m, int r) รับอาร์เรย์ องค์ประกอบด้านซ้าย ตรงกลางของอาร์เรย์ และองค์ประกอบด้านขวาของอาร์เรย์เป็นอินพุต ฟังก์ชันส่งคืนชิ้นส่วนที่จัดเรียงแบบรวมขนาด 32

• เริ่มต้นความยาวของอาร์เรย์ที่มีองค์ประกอบด้านซ้ายทั้งหมดและความยาวของอาร์เรย์ที่มีองค์ประกอบที่ถูกต้องทั้งหมด

• หลังจากกรอกอาร์เรย์ด้านซ้ายและอาร์เรย์ด้านขวา ให้วนซ้ำในอาร์เรย์ด้านซ้ายและอาร์เรย์ด้านขวา

• หากองค์ประกอบในอาร์เรย์ด้านซ้ายน้อยกว่าองค์ประกอบในอาร์เรย์ด้านขวา ให้เพิ่มองค์ประกอบลงในอาร์เรย์ที่ใหญ่ขึ้น

• มิฉะนั้นจะดันองค์ประกอบเข้าไปในอาร์เรย์ที่เล็กกว่าตามลำดับ

• คัดลอกองค์ประกอบที่เหลือในอาร์เรย์ด้านซ้ายและอาร์เรย์ด้านขวาลงในอาร์เรย์ที่ใหญ่กว่า

• ฟังก์ชัน timSortAlgo(int arr[], int n) รับอาร์เรย์และขนาดของอาร์เรย์เป็นอินพุต ซึ่งเรียกใช้การแทรก Sort ในขั้นต้นและผสานองค์ประกอบอาร์เรย์

• ส่งคืนผลลัพธ์เป็นองค์ประกอบสุดท้ายของอาร์เรย์โดยใช้ Tim Sort

ตัวอย่าง (C++)

#include<bits/stdc++.h>
using namespace std;
const int RUN = 32; // Initialising the RUN to get chunks
void insertionSort(int arr[], int left, int right) // Implementing insertion
sort for RUN size chunks{
   for (int i = left + 1; i <= right; i++){
      int t = arr[i];
      int j = i - 1;
      while (j >= left && t < arr[j]){
         arr[j+1] = arr[j--];
      }
      arr[j+1] = t;
   }
}
void merge(int arr[], int l, int m, int r) // using the merge function the
sorted chunks of size 32 are merged into one{
   int len1 = m - l + 1, len2 = r - m;
   int left[len1], right[len2];
   for (int i = 0; i < len1; i++)
      left[i] = arr[l + i]; // Filling left array
   for (int i = 0; i < len2; i++)
      right[i] = arr[m + 1 + i]; // Filling right array
   int i = 0;
   int j = 0;
   int k = l;
   while (i < len1 && j < len2) // Iterate into both arrays left and right{
      if (left[i] <= right[j]) // IF element in left is less then increment i by pushing into larger array{
         arr[k] = left[i];
         i++;
      } else {
         arr[k] = right[j]; // Element in right array is greater
         increment j
         j++;
      }
      k++;
   }
   while (i < len1) // This loop copies remaining element in left array{
      arr[k] = left[i];
      k++;
      i++;
   }
   while (j < len2) // This loop copies remaining element in right array{
      arr[k] = right[j];
      k++;
      j++;
   }
}
void timSortAlgo(int arr[], int n){
   for (int i = 0; i < n; i+=RUN) insertionSort(arr, i, min((i+31), (n-1))); //Call insertionSort()
   for (int s = RUN; s < n; s = 2*s) // Start merging from size RUN (or 32). It will continue upto 2*RUN{
      // pick starting point of left sub array. We are going to merge
      arr[left..left+size-1]
      // and arr[left+size, left+2*size-1]
      // After every merge, we
      // increase left by 2*size
      for (int left = 0; left < n;left += 2*s){
         int mid = left + s - 1; // find ending point of left sub
         array mid+1 is starting point of right sub array
         int right = min((left + 2*s - 1), (n-1));
         merge(arr, left, mid, right); // merge sub array
         arr[left.....mid] & arr[mid+1....right]
      }
   }
}
void printArray(int arr[], int n){
   for (int i = 0; i < n; i++)
      cout << arr[i] << " ";
   cout << endl;
}
// Main function to implement timsort algorithm
int main(){
   int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "The Original array- ";
   printArray(arr, n);
   // calling the timsortAlgo function to sort array
   timSortAlgo(arr, n);
   cout<<"After Sorting Array Using TimSort Algorithm- ";
   printArray(arr, n); // Calling print function
   return 0;
}