Chương trình C/C++ cho Sắp xếp Lẻ-Chẵn (Brick Sort)

Ở đây chúng ta sẽ xem cách sắp xếp gạch (brick sort) hoạt động. Sắp xếp gạch là một biến thể của sắp xếp nổi bọt (bubble sort). Thuật toán này được chia thành hai phần. Các phần này là phần lẻ và phần chẵn. Trong phần lẻ chúng ta sẽ dùng sắp xếp nổi bọt trên các phần tử chỉ số lẻ, và trong phần chẵn chúng ta sẽ dùng sắp xếp nổi bọt trên các phần tử chỉ số chẵn. Hãy xem thuật toán để hiểu ý tưởng.

Thuật toán

brickSort(arr, n)

begin
  flag := false
  while the flag is not true, do
    flag := true
    for i := 1 to n-2, increase i by 2, do
      if arr[i] > arr[i+1], then
        exchange arr[i] and arr[i+1]
        flag := false
      end if
    done
    for i := 0 to n-2, increase i by 2, do
      if arr[i] > arr[i+1], then
        exchange arr[i] and arr[i+1]
        flag := false
      end if
    done
  done
end

Ví dụ

#include<iostream>
using namespace std;

void brickSort(int arr[], int n){
  bool flag = false;
  while(!flag){
    flag = true;
    for(int i = 1; i<n-1; i= i+2){
      if(arr[i] > arr[i+1]){
        swap(arr[i], arr[i+1]);
        flag = false;
      }
    }
    for(int i = 0; i<n-1; i= i+2){
      if(arr[i] > arr[i+1]){
        swap(arr[i], arr[i+1]);
        flag = false;
      }
    }
  }
}

main() {
  int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
  int n = sizeof(data)/sizeof(data[0]);
  cout << "Sorted Sequence ";
  brickSort(data, n);
  for(int i = 0; i <n;i++){
    cout << data[i] << " ";
  }
}

Kết quả

Sorted Sequence 13 20 32 35 40 54 74 98 98 154