Một thuật toán sắp xếp cải thiện một chút về sắp xếp lựa chọn?

Ở đây chúng ta sẽ thấy một số cải tiến về phân loại lựa chọn. Như chúng ta biết rằng sắp xếp lựa chọn hoạt động bằng cách lấy phần tử tối thiểu hoặc tối đa từ mảng và đặt phần tử đó vào đúng vị trí. Trong cách tiếp cận này, chúng tôi muốn sắp xếp mảng theo cả hai cách. Ở đây chúng ta sẽ lấy max và min đồng thời, sau đó sắp xếp mảng từ hai đầu. Hãy cho chúng tôi xem thuật toán để có ý tưởng tốt 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] << " ";
}

Đầu ra

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