Chương trình C++ thực hiện Stooge Sort

Stooge Sort được dùng để sắp xếp dữ liệu đã cho. Đây là một thuật toán sắp xếp đệ quy. Stooge Sort chia mảng thành hai phần chồng chéo nhau, mỗi phần 2/3 và sắp xếp mảng trong ba bước bằng cách sắp xếp phần I rồi phần II và lại phần I. Độ phức tạp thời gian xấu nhất của thuật toán này là O(n^2.7095).

Thuật toán

Bắt đầu
  Nhập dữ liệu.
  Gọi hàm StoogeSort() với 'a' mảng dữ liệu và 'n' số lượng giá trị.
  Triển khai sắp xếp bằng phương pháp đệ quy.
  Chia mảng thành 2/3 phần tử đầu là phần I và 2/3 phần tử cuối là phần II.
  Sau đó gửi phần đầu, phần thứ hai và lại phần đầu vào StoogeSort().
  Nếu độ dài không thể chia nhỏ hơn thì hoán đổi phần tử tại đầu và cuối nếu a[end] < a[start].
  Trả về main và hiển thị kết quả.
Kết thúc.

Mã ví dụ

#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 << "\nNhập số lượng phần tử dữ liệu cần sắp xếp: ";
    cin >> m;
    int arr[m];
    for (i = 0; i < m; i++) {
        cout << "Nhập phần tử " << i+1 << ": ";
        cin >> arr[i];
    }
    StoogeSort(arr, 0, m-1);
    cout << "\nDữ liệu đã sắp xếp ";
    for (i = 0; i < m; i++)
        cout << "->" << arr[i];
    return 0;
}

Kết quả

Nhập số lượng phần tử dữ liệu cần sắp xếp: 4
Nhập phần tử 1: 6
Nhập phần tử 2: 7
Nhập phần tử 3: 3
Nhập phần tử 4: 2
Dữ liệu đã sắp xếp ->2->3->6->7