एक सॉर्टिंग एल्गोरिदम जो चयन प्रकार पर थोड़ा सुधार करता है?

यहां हम चयन क्रम में कुछ सुधार देखेंगे। जैसा कि हम जानते हैं कि चयन क्रम सरणी से न्यूनतम या अधिकतम तत्व लेकर काम करता है और उस तत्व को सही स्थिति में रखता है। इस दृष्टिकोण में, हम सरणी को दोनों तरीकों से क्रमबद्ध करना चाहते हैं। यहां हम अधिकतम और न्यूनतम एक साथ लेंगे, फिर सरणी को दो छोर से क्रमबद्ध करें। आइए बेहतर विचार प्राप्त करने के लिए एल्गोरिथम देखें।

एल्गोरिदम

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