একটি বাছাই অ্যালগরিদম যা নির্বাচন সাজানোর উপর সামান্য উন্নতি করে?

এখানে আমরা নির্বাচন সাজানোর কিছু উন্নতি দেখতে পাব। আমরা জানি যে নির্বাচন সাজানোর কাজ হয় অ্যারে থেকে সর্বনিম্ন বা সর্বোচ্চ উপাদান নিয়ে এবং সেই উপাদানটিকে সঠিক অবস্থানে রেখে। এই পদ্ধতিতে, আমরা উভয় উপায়ে অ্যারে সাজাতে চাই। এখানে আমরা সর্বোচ্চ এবং মিন একই সাথে নেব, তারপর অ্যারেটিকে দুই প্রান্ত থেকে বাছাই করব। আসুন আরও ভাল ধারণা পেতে অ্যালগরিদম দেখি।

অ্যালগরিদম

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