Thuật toán sắp xếp cải tiến Selection Sort

Ở đây chúng ta sẽ xem một số cải tiến trên selection sort. Chúng ta biết selection sort hoạt động bằng cách lấy phần tử nhỏ nhất hoặc lớn nhất từ mảng và đặt phần tử đó tại vị trí đúng. Trong cách tiếp cận này, chúng ta muốn sắp xếp mảng theo cả hai chiều. Ở đây chúng ta sẽ lấy max và min cùng lúc, sau đó sắp xếp mảng từ hai đầu. Hãy xem thuật toán để hiểu rõ hơn.

Thuật toán

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 the 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

Ví dụ

#include<iostream>
using namespace std;

void twoWaySelectionSort(int arr[], int n) {
  //i will move from left, and j will move from right
  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; //i_min and i_max will hold min and max index respectively
    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]); //put the min into the index i
    if (arr[i_min] == max)
      swap(arr[j], arr[i_min]);
    else
      swap(arr[j], arr[i_max]);
  }
}

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] << " ";
}

Kết quả

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