Sắp xếp mảng theo dạng Max-Min bằng C++

Cho một mảng đã được sắp xếp. Chúng ta cần sắp xếp lại mảng này theo dạng tối đa - tối thiểu, tức là phần tử đầu tiên là phần tử lớn nhất, phần tử thứ hai là phần tử nhỏ nhất, phần tử thứ ba là phần tử lớn thứ hai, phần tử thứ tư là phần tử nhỏ thứ hai, và cứ tiếp tục như vậy. Ví dụ:

Input : arr[ ] = { 10, 20, 30, 40, 50, 60 } Output : { 60, 10, 50, 20, 40, 30 } Giải thích : mảng được sắp xếp lại theo dạng { max thứ 1, min thứ 1, max thứ 2, min thứ 2, max thứ 3, min thứ 3 } Input : arr[ ] = { 15, 17, 19, 23, 36, 67, 69 } Output : { 69, 15, 67, 17, 36, 19, 23 }

Có một cách tiếp cận đơn giản để sắp xếp mảng theo dạng max-min:

Cách tiếp cận giải quyết bài toán

Cách tiếp cận hai con trỏ (Two-pointer Approach)

Sử dụng hai biến min và max để trỏ đến chỉ số của phần tử nhỏ nhất và lớn nhất, đồng thời tạo một mảng mới rỗng cùng kích thước để lưu mảng đã sắp xếp lại. Duyệt qua mảng: nếu chỉ số hiện tại là chẵn, thêm phần tử arr[max] vào mảng mới và giảm max đi 1; nếu chỉ số là lẻ, thêm phần tử arr[min] và tăng min lên 1. Lặp lại cho đến khi max nhỏ hơn min.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    // Tạo mảng mới để lưu mảng đã sắp xếp lại
    int final[n];
    // Các biến trỏ đến chỉ số đầu và cuối
    int min = 0, max = n - 1;
    int count = 0;
    // Duyệt mảng cho đến khi min > max
    for (int i = 0; min <= max; i++) {
        // Nếu count chẵn thì lưu phần tử max
        if (count % 2 == 0) {
            final[i] = arr[max];
            max--;
        }
        // Ngược lại lưu phần tử min
        else {
            final[i] = arr[min];
            min++;
        }
        count++;
    }
    // In mảng kết quả
    for (int i = 0; i < n; i++)
        cout << final[i] << " ";
    return 0;
}

Kết quả đầu ra

6 1 5 2 4 3

Giải thích mã nguồn

• Khởi tạo min = 0 và max = n - 1.
• Vòng lặp for (int i = 0; min <= max; i++) duyệt cho đến khi min vượt quá max.
• Nếu count chẵn: lấy phần tử tại max, giảm max.
• Nếu count lẻ: lấy phần tử tại min, tăng min.
• Kết quả lưu trong mảng final[].

Kết luận

Bài viết đã trình bày giải pháp sắp xếp mảng theo dạng max-min. Cách tiếp cận hai con trỏ cho độ phức tạp thời gian O(n). Chương trình C++ mẫu cũng được cung cấp; bạn có thể triển khai tương tự bằng C, Java, Python, v.v. Hy vọng bài viết hữu ích.