การจัดเรียงอาร์เรย์ในรูปแบบสูงสุด-ต่ำสุดโดยใช้ C++

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

Input : arr[] = { 10, 20, 30, 40, 50, 60 }
Output : { 60, 10, 50, 20, 40, 30 }
คำอธิบาย : อาร์เรย์ถูกจัดเรียงใหม่ในรูปแบบ { สูงสุดอันดับ1, ต่ำสุดอันดับ1, สูงสุดอันดับ2, ต่ำสุดอันดับ2, สูงสุดอันดับ3, ต่ำสุดอันดับ3 }

Input : arr[] = { 15, 17, 19, 23, 36, 67, 69 }
Output : { 69, 15, 67, 17, 36, 19, 23 }

วิธีการแก้ปัญหา

มีวิธีการเดียวในการจัดเรียงอาร์เรย์ในรูปแบบสูงสุด-ต่ำสุด:

วิธี Two-pointer (ตัวชี้สองตัว)

ใช้ตัวแปรสองตัวคือ min และ max ซึ่งจะชี้ไปยังองค์ประกอบต่ำสุดและสูงสุด และสร้างอาร์เรย์ใหม่ว่างเปล่าขนาดเท่าเดิมเพื่อเก็บอาร์เรย์ที่จัดเรียงใหม่ ต่อมาทำการวนลูปผ่านอาร์เรย์ และหากดัชนีการวนซ้ำเป็นเลขคู่ ให้เพิ่ม arr[max] ลงในอาร์เรย์ว่างและลดค่า max ลง 1 หากดัชนีเป็นเลขคี่ ให้เพิ่ม arr[min] ลงในอาร์เรย์ว่างและเพิ่มค่า min ขึ้น 1 ทำซ้ำจนกว่า max จะน้อยกว่า min

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

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

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // สร้างอาร์เรย์ใหม่เพื่อเก็บอาร์เรย์ที่จัดเรียงใหม่
    int final[n];
    
    // ตัวแปรชี้ไปยังดัชนีเริ่มต้นและสุดท้าย
    int min = 0, max = n - 1;
    int count = 0;
    
    // วนลูปผ่านอาร์เรย์จนกว่า max จะน้อยกว่าหรือเท่ากับ min
    for (int i = 0; min <= max; i++) {
        // ถ้า count เป็นเลขคู่ ให้เก็บองค์ประกอบดัชนี max
        if (count % 2 == 0) {
            final[i] = arr[max];
            max--;
        }
        // เก็บองค์ประกอบดัชนี min
        else {
            final[i] = arr[min];
            min++;
        }
        count++;
    }
    
    // แสดงอาร์เรย์ที่จัดเรียงใหม่
    for (int i = 0; i < n; i++)
        cout << final[i] << " ";
    return 0;
}

ผลลัพธ์

6 1 5 2 4 3

คำอธิบายโค้ด

• เริ่มต้นตัวแปร min=0 และ max = ความยาวอาร์เรย์(n) - 1
• for (int i = 0; min <= max; i++) เพื่อวนลูปผ่านอาร์เรย์จนกว่า max จะมากกว่า min
• ถ้า count เป็นเลขคี่ ให้เพิ่มองค์ประกอบ (max) ลงในอาร์เรย์สุดท้าย และลดค่า max ลง 1
• ถ้า count เป็นเลขคู่ ให้เพิ่มองค์ประกอบ (min) ลงในอาร์เรย์สุดท้าย และเพิ่มค่า min ขึ้น 1
• สุดท้าย อาร์เรย์ผลลัพธ์จะถูกเก็บใน final[]

สรุป

ในบทความนี้ เราได้อภิปรายวิธีแก้ปัญหาการจัดเรียงอาร์เรย์ที่กำหนดให้เป็นรูปแบบ max-min เราได้อภิปรายวิธีการแก้ปัญหาและแก้ไขด้วยวิธีที่เหมาะสมที่สุดซึ่งมีความซับซ้อนด้านเวลา O(n) เรายังเขียนโปรแกรม C++ สำหรับปัญหานี้เช่นกัน ทำนองเดียวกัน เราสามารถเขียนโปรแกรมนี้ในภาษาอื่นๆ เช่น C, Java, Python ฯลฯ ได้ หวังว่าบทความนี้จะเป็นประโยชน์