C++での代替ソート

最初の要素が配列の最大値であり、ソートされた配列の2番目の要素が最小であり、3番目の要素が2番目の最小値であり、4番目の要素が2番目の最大値であるように、整数配列の要素を並べ替えます。配列して続行します。

概念をよりよく理解するために例を見てみましょう。

Input : 4 1 8 2 9 3 7
Output : 9 1 8 2 7 3 4
Explanation : The elements in a sorted way is 1 2 3 4 7 8 9. Now, 
let’s create it in the manner we wanted it i.e. alternate sorted form. 
So, the largest element of the array first i.e. 9 followed by 1 which 
is the smallest element of the array i.e. 1 next comes 8 , 2 , 7 , 3, 4.

概念を理解したので、この問題に対処するためのソリューションを開発できます。したがって、考えられる解決策の1つは、配列を並べ替えて、この並べ替えられた配列の最後と最初の要素を出力することです。このソリューションに基づいてアルゴリズムを作成しましょう。

アルゴリズム

Step 1 : Sort the array.
Step 2 : Create two pointers one for traversing from start and other pointer for traversing from end.
Step 3 : Print values of the pointer in alternate form and increase the value of the iterator.

例

#include <iostream>
using namespace std;
void alternateSort(int arr[], int n) ;
void swap(int *xp, int *yp) ;
void selectionSort(int arr[], int n) ;
int main(){
   int arr[] = { 4,1,8,2,9,3,7};
   int n = sizeof(arr)/sizeof(arr[0]);
   alternateSort(arr, n);
   return 0;
}
void alternateSort(int arr[], int n){
   selectionSort(arr, n);
   int i = 0, j = n-1;
   while (i < j) {
      cout << arr[j--] << " ";
      cout << arr[i++] << " ";
   }
   if (n % 2 != 0)
      cout << arr[i];
}
void swap(int *xp, int *yp){
   int temp = *xp;
   *xp = *yp;
   *yp = temp;
}
void selectionSort(int arr[], int n){
   int i, j, min_idx;
   for (i = 0; i < n-1; i++){
      min_idx = i;
   for (j = i+1; j < n; j++)
      if (arr[j] < arr[min_idx])
         min_idx = j;
      swap(&arr[min_idx], &arr[i]);
   }
}

出力

9 1 8 2 7 3 4