Chương trình C/C++ sắp xếp chẵn-lẻ (Odd-Even Sort / Brick Sort)

Odd-Even Sort (Brick Sort) tương tự Bubble Sort nhưng chia thành 2 pha: pha lẻ (so sánh hoán đổi cặp chỉ số lẻ) và pha chẵn (cặp chỉ số chẵn). Cả hai chạy song song cho đến khi mảng sắp xếp xong.

Input: a[]={3,5,7,6,1,4,2} Output: 1 2 3 4 5 6 7

Giải thích

Thuật toán so sánh hoán đổi cặp (i, i+1) với i lẻ (pha lẻ) rồi i chẵn (pha chẵn). Lặp lại cho đến khi không còn hoán đổi nào. Thiết kế cho xử lý song song.

Ví dụ

#include <stdio.h>
#include <math.h>
#define MAX 7

void swap(int *,int *);
void oddeven_sort(int *);

int main() {
    int a[]={3,5,7,6,1,4,2}, i;
    oddeven_sort(a);
    for (i = 0;i < MAX;i++) {
        printf(" %d", a[i]);
    }
}

void swap(int * x, int * y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void oddeven_sort(int * x) {
    int sort = 0, i;
    while (!sort) {
        sort = 1;
        for (i = 1;i < MAX;i += 2) {
            if (x[i] > x[i+1]) {
                swap(&x[i], &x[i+1]);
                sort = 0;
            }
        }
        for (i = 0;i < MAX - 1;i += 2) {
            if (x[i] > x[i + 1]) {
                swap(&x[i], &x[i + 1]);
                sort = 0;
            }
        }
    }
}

Kết quả

1234567