Sắp xếp thay thế (Alternative Sorting) trong C++

Sắp xếp mảng sao cho: phần tử 1 là max, phần tử 2 là min, phần tử 3 là max thứ 2, phần tử 4 là min thứ 2,...

Ví dụ: Input: 4 1 8 2 9 3 7 -> Sorted: 1 2 3 4 7 8 9 -> Output: 9 1 8 2 7 3 4.

Thuật toán: Sắp xếp mảng tăng dần. Dùng 2 con trỏ: left=0, right=n-1. In arr[right--], arr[left++] luân phiên. Nếu n lẻ, in phần tử giữa cuối cùng.

Ví dụ code

#include <iostream>
#include <algorithm>
using namespace std;

void alternateSort(int arr[], int n) {
    sort(arr, arr + n);
    int i = 0, j = n - 1;
    while (i < j) {
        cout << arr[j--] << " ";
        cout << arr[i++] << " ";
    }
    if (n % 2 != 0) cout << arr[i];
}

int main() {
    int arr[] = {4, 1, 8, 2, 9, 3, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    alternateSort(arr, n);
    return 0;
}

Kết quả

9 1 8 2 7 3 4