อัลกอริทึมจัดเรียงที่ปรับปรุงจาก Selection Sort

ที่นี่เราจะดูการปรับปรุง Selection Sort ตัว Selection Sort ทำงานโดยหาตัวน้อยที่สุดหรือมากที่สุด วางไว้ตำแหน่งที่ถูกต้อง ในแนวทางนี้ เราจะจัดเรียงจาก 2 ด้านพร้อมกัน หา max และ min พร้อมกัน แล้ววางไว้ปลายทั้งสองข้าง มาดูอัลกอริทึม

อัลกอริทึม

twoWaySelectionSort(arr, n)

begin
    for i := 0, and j := n-1, increase i by 1, and decrease j by 1, until i >= j, do
        min := minimum element from index i to j
        max := maximum element from index i to j
        i_min := index of min
        i_max := index of max
        exchange arr[i] and arr[i_min]
        if arr[i_min] is same as max, then
            swap arr[j] and arr[i_min]
        else
            swap arr[j] and arr[i_max]
        end if
    done
end

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

void twoWaySelectionSort(int arr[], int n) {
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        int min = arr[i], max = arr[i];
        int i_min = i, i_max = i;
        for (int k = i; k <= j; k++) {
            if (arr[k] > max) {
                max = arr[k];
                i_max = k;
            } else if (arr[k] < min) {
                min = arr[k];
                i_min = k;
            }
        }
        swap(arr[i], arr[i_min]);
        if (arr[i_min] == max)
            swap(arr[j], arr[i_min]);
        else
            swap(arr[j], arr[i_max]);
    }
}

int main() {
    int arr[] = {25, 45, 14, 10, 23, 29, 65, 21, 78, 96, 30};
    int n = sizeof(arr) / sizeof(arr[0]);
    twoWaySelectionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

ผลลัพธ์

Sorted array: 10 14 21 23 25 29 30 45 65 78 96