選択ソートをわずかに改善するソートアルゴリズム？

ここでは、選択ソートのいくつかの改善が見られます。選択ソートは、配列から最小要素または最大要素のいずれかを取得し、その要素を正しい位置に配置することで機能することがわかっています。このアプローチでは、両方の方法で配列を並べ替えます。ここでは、最大値と最小値を同時に取得してから、配列を両端から並べ替えます。より良いアイデアを得るためのアルゴリズムを見てみましょう。

アルゴリズム

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

例

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

出力

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