โปรแกรม C++ จัดเรียงอาร์เรย์ในรูปแบบสูงสุด-ต่ำสุด (Maximum Minimum Form)

เราได้รับอาร์เรย์จำนวนเต็มซึ่งอาจเรียงลำดับหรือไม่ได้ ถ้าไม่ได้เรียง ให้เรียงลำดับก่อน จากนั้นจัดเรียงอาร์เรย์ใหม่ในรูปแบบ: ตัวแรกเป็นค่าสูงสุด ตัวที่สองเป็นค่าต่ำสุด ตัวที่สามเป็นค่าสูงสุดอันดับสอง ตัวที่สี่เป็นค่าต่ำสุดอันดับสอง และทำซ้ำไปเรื่อยๆ

ตัวอย่างการทำงาน (Input/Output)

ตัวอย่างที่ 1

Input: int arr[] = {7, 5, 2, 3, 4, 9, 10, 5}

Output: Array before Arrangement: 2 3 4 5 5 7 9 10 Rearrangement of an array in maximum minimum form is: 10 2 9 3 7 4 5 5

คำอธิบาย: เรียงอาร์เรย์ได้ {2, 3, 4, 5, 5, 7, 9, 10} จากนั้นจัด: สูงสุด(10), ต่ำสุด(2), สูงสุดอันดับ2(9), ต่ำสุดอันดับ2(3), สูงสุดอันดับ3(7), ต่ำสุดอันดับ3(4), สูงสุดอันดับ4(5), ต่ำสุดอันดับ4(5) → 10 2 9 3 7 4 5 5

ตัวอย่างที่ 2

Input: int arr[] = {2, 4, 1, 6, 7}

Output: Array before Arrangement: 1 2 4 6 7 Rearrangement of an array in maximum minimum form is: 7 1 6 2 4

คำอธิบาย: เรียงได้ {1, 2, 4, 6, 7} จัด: 7, 1, 6, 2, 4

อัลกอริทึมที่ใช้ (Technique: Encode Two Values in One)

• รับอาร์เรย์ คำนวณขนาด เรียก sort() จาก C++ STL
• พิมพ์อาร์เรย์หลังเรียง (ก่อนจัดรูปแบบ max-min) เรียก Rearr_Max_Min(arr, size)
• ภายในฟังก์ชัน Rearr_Max_Min(arr, size):
  • max = size - 1 (index สูงสุด), min = 0 (index ต่ำสุด), max_val = arr[size-1] + 1 (ค่ามากกว่าสูงสุดในอาร์เรย์)
  • วนลูป for i = 0 ถึง size-1:
    • ถ้า i คู่ (index 0,2,4...): arr[i] += (arr[max] % max_val) * max_val; max--
    • ถ้า i คี่ (index 1,3,5...): arr[i] += (arr[min] % max_val) * max_val; min++
  • วนลูป for i = 0 ถึง size-1: arr[i] = arr[i] / max_val (ถอดรหัส)

ตัวอย่างโค้ด C++

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

void Rearr_Max_Min(int arr[], int size) {
    int max = size - 1;
    int min = 0;
    int max_val = arr[size - 1] + 1;
    for (int i = 0; i < size; i++) {
        if (i % 2 == 0) {
            arr[i] += (arr[max] % max_val) * max_val;
            max--;
        } else {
            arr[i] += (arr[min] % max_val) * max_val;
            min++;
        }
    }
    for (int i = 0; i < size; i++) {
        arr[i] = arr[i] / max_val;
    }
}

int main() {
    int arr[] = {7, 5, 2, 3, 4, 9, 10, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    // เรียงอาร์เรย์
    sort(arr, arr + size);
    // แสดงอาร์เรย์หลังเรียง
    cout << "Array before Arrangement: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    // เรียกฟังก์ชันจัดเรียง max-min
    Rearr_Max_Min(arr, size);
    // แสดงผลลัพธ์
    cout << "\nRearrangement of an array in maximum minimum form is: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

ผลลัพธ์

การรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Array before Arrangement: 2 3 4 5 5 7 9 10
Rearrangement of an array in maximum minimum form is: 10 2 9 3 7 4 5 5