선택 정렬에서 약간 개선된 정렬 알고리즘?

여기에서 선택 정렬에 대한 몇 가지 개선 사항을 볼 수 있습니다. 선택 정렬은 배열에서 최소 또는 최대 요소를 가져와 올바른 위치에 배치하여 작동한다는 것을 알고 있습니다. 이 접근 방식에서는 배열을 두 가지 방식으로 정렬하려고 합니다. 여기서 우리는 최대값과 최소값을 동시에 취한 다음 두 끝에서 배열을 정렬합니다. 더 나은 아이디어를 얻기 위해 알고리즘을 살펴보겠습니다.

알고리즘

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