โปรแกรม C++ เพื่อทำการจัดเรียง Stooge

Stooge Sort ใช้เพื่อจัดเรียงข้อมูลที่กำหนด เป็นอัลกอริธึมการเรียงลำดับแบบเรียกซ้ำ Stooge Sort แบ่งอาร์เรย์ออกเป็นสองส่วนที่ทับซ้อนกัน 2/3 แต่ละส่วนและจัดเรียงอาร์เรย์ในสามขั้นตอนโดยเรียงลำดับ I จากนั้น II และอีกครั้งฉันแยกส่วน ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดของอัลกอริทึมนี้คือ O(n ^ 2.7095)

อัลกอริทึม

Begin
   Take input of data.
   Call StoogeSort() function with ‘a’ the array of data and ‘n’ the number of values, in the argument list.
   Implement Sorting using recursive approach.
   Divide the array into first 2/3 element as part I and last 2/3 as part II.
   Then send the first, second and again first part into StoogeSort().
   If the length is not further breakable then swap element at the start and end if a[end] < a[start].
   Return to main and display the result.
End.

โค้ดตัวอย่าง

#include<iostream>
using namespace std;
void StoogeSort(int a[],int start, int end) {
   int temp;
   if(end-start+1 > 2) {
      temp = (end-start+1)/3;
      StoogeSort(a, start, end-temp);
      StoogeSort(a, start+temp, end);
      StoogeSort(a, start, end-temp);
   }
   if(a[end] < a[start]) {
      temp = a[start];
      a[start] = a[end];
      a[end] = temp;
    }
}
int main() {
   int m, i;
   cout<<"\nEnter the number of data element to be sorted: ";
   cin>>m;
   int arr[m];
   for(i = 0; i < m; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>arr[i];
   }
   StoogeSort(arr, 0, m-1);
   cout<<"\nSorted Data ";
   for (i = 0; i < m; i++)
      cout<<"->"<<arr[i];
   return 0;
}

ผลลัพธ์

Enter the number of data element to be sorted: 4
Enter element 1: 6
Enter element 2: 7
Enter element 3: 3
Enter element 4: 2
Sorted Data ->2->3->6->7