อัลกอริทึมการเรียงลำดับที่ปรับปรุงการเรียงลำดับการเลือกเล็กน้อย?

ที่นี่เราจะเห็นการปรับปรุงบางอย่างในการเรียงลำดับการเลือก ดังที่เราทราบแล้วว่าการเรียงลำดับการเลือกทำงานโดยนำองค์ประกอบต่ำสุดหรือสูงสุดจากอาร์เรย์และวางองค์ประกอบนั้นในตำแหน่งที่ถูกต้อง ในแนวทางนี้ เราต้องการจัดเรียงอาร์เรย์ทั้งสองวิธี ที่นี่เราจะใช้ค่าสูงสุดและต่ำสุดพร้อมกัน จากนั้นจัดเรียงอาร์เรย์จากปลายทั้งสอง ให้เราดูอัลกอริธึมเพื่อรับแนวคิดที่ดีขึ้น

อัลกอริทึม

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