Odd-Even Sort หรือ Brick Sort เป็นการเรียงคล้าย Bubble Sort แบ่งเป็น 2 Phase: Odd Phase และ Even Phase ทำงานสลับกันทุก Iteration จนเรียงครบ
Odd Phase: ทำงานแบบ Bubble Sort แต่เฉพาะ Index คี่
Even Phase: ทำงานแบบ Bubble Sort แต่เฉพาะ Index คู่
ตัวอย่าง:
Input: a[] = {3, 5, 7, 6, 1, 4, 2} Output: 1 2 3 4 5 6 7คำอธิบาย
Even-Odd Sort (Brick Sort) ใช้ Comparison Sort เหมาะสำหรับ Parallel Processing เปรียบเทียบคู่ Odd/Even กับเพื่อนบ้าน หากผิดลำดับ สลับกัน ทำซ้ำจนเรียบร้อย
ตัวอย่าง
#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 = *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;
}
}
}
}ผลลัพธ์
1 2 3 4 5 6 7
