โปรแกรมตรวจสอบว่าอาร์เรย์เรียงลำดับหรือไม่ (แบบวนซ้ำและแบบเรียกซ้ำ) ในภาษา C

ได้รับอาร์เรย์ arr[] ด้วย n จำนวนองค์ประกอบ งานคือตรวจสอบว่าอาร์เรย์ที่กำหนดอยู่ในลำดับที่เรียงแล้วหรือไม่ ถ้าอยู่ในลำดับที่เรียงแล้วให้พิมพ์ "อาร์เรย์อยู่ในลำดับที่เรียงแล้ว" ไม่งั้นพิมพ์ "อาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว"

เพื่อแก้ปัญหานี้ เราสามารถใช้วิธีแบบวนซ้ำ (Iterative) หรือแบบเรียกซ้ำ (Recursive) เราจะอธิบายทั้งสองวิธี

วิธีแบบเรียกซ้ำ (Recursive)

วิธีแบบเรียกซ้ำคืออะไร? ในวิธีนี้ เราเรียกฟังก์ชันซ้ำๆ จนกว่าจะได้ผลลัพธ์ที่ต้องการ ในวิธีนี้ ค่าที่ฟังก์ชันคืนจะถูกเก็บในหน่วยความจำแบบสแต็ก (stack memory)

ตัวอย่าง

อินพุต

arr[] = {12, 13, 14, 16, 18}

เอาต์พุต

อาร์เรย์อยู่ในลำดับที่เรียงแล้ว

คำอธิบาย — 12 < 13 < 14 < 16 < 18 ดังนั้นใช่ อาร์เรย์อยู่ในลำดับที่เรียงแล้ว

อินพุต

arr[] = {2, 1, 3, 5, 6}

เอาต์พุต

อาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว

วิธีการแก้ปัญหาแบบเรียกซ้ำ

• รับอาร์เรย์ arr[] เป็นอินพุตและกำหนด n ด้วยขนาดของอาร์เรย์
• ตรวจสอบถ้าถึงจุดเริ่มต้นของอาร์เรย์ ให้คืนค่า true
• ตรวจสอบถ้าองค์ประกอบก่อนหน้าของอาร์เรย์ไม่น้อยกว่าองค์ประกอบถัดไป ให้คืนค่า false
• ลด n ลง 1 และไปขั้นตอนที่ 2

อัลกอริทึมแบบเรียกซ้ำ

Start
In function int arraySortedCheck(int arr[], int n)
    Step 1: ถ้า n == 1 || n == 0 แล้ว Return 1
    Step 2: ถ้า arr[n-1] < arr[n-2] แล้ว Return 0
    Step 3: Return arraySortedCheck(arr, n-1)
In Function int main()
    Step 1: ประกาศและกำหนด arr[] เป็น {1, 8, 3, 4, 7}
    Step 2: ประกาศและกำหนด int n เป็น sizeof(arr)/sizeof(arr[0])
    Step 3: ถ้า arraySortedCheck(arr, n) แล้ว Print "อาร์เรย์อยู่ในลำดับที่เรียงแล้ว"
    Step 4: ถ้าไม่ใช่ Print "อาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว"
Stop

ตัวอย่างโค้ดแบบเรียกซ้ำ

#include <stdio.h>

// ฟังก์ชันเรียกซ้ำตรวจสอบว่าอยู่ในลำดับที่เรียงแล้วหรือไม่
int arraySortedCheck(int arr[], int n) {
    // ตรวจสอบองค์ประกอบทั้งหมดแล้วและทั้งหมดเรียงลำดับ
    if (n == 1 || n == 0)
        return 1;
    // เมื่ออาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว
    if (arr[n-1] < arr[n-2])
        return 0;
    return arraySortedCheck(arr, n-1);
}

int main() {
    int arr[] = {1, 8, 3, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    if (arraySortedCheck(arr, n)) {
        printf("อาร์เรย์อยู่ในลำดับที่เรียงแล้ว\n");
    } else {
        printf("อาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว\n");
    }
    return 0;
}

ผลลัพธ์

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

อาร์เรย์อยู่ในลำดับที่เรียงแล้ว

วิธีแบบวนซ้ำ (Iterative)

ในวิธีแบบวนซ้ำ เราใช้ลูปเช่น for-loop, while-loop หรือ do-while loop ที่ทำงานจนกว่าเงื่อนไขจะเป็นจริง (คือ 1)

ตัวอย่าง

อินพุต

arr[] = {12, 13, 14, 16, 18}

เอาต์พุต

อาร์เรย์อยู่ในลำดับที่เรียงแล้ว

อินพุต

arr[] = {2, 1, 3, 5, 6}

เอาต์พุต

อาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว

วิธีการแก้ปัญหาแบบวนซ้ำ

• รับอินพุต arr[]
• ลูปจนถึงสิ้นสุดของอาร์เรย์
  • ตรวจสอบถ้าองค์ประกอบปัจจุบันไม่น้อยกว่าองค์ประกอบถัดไป ให้คืนค่า false และออก
  • ไม่งั้นทำต่อ
• ไปขั้นตอนที่ 2

อัลกอริทึมแบบวนซ้ำ

Start
In function int arraySortedCheck(int arr[], int n)
    Step 1: Loop For i = 0 และ i < n-1 และ ++i
        ถ้า arr[i] > arr[i+1] แล้ว Return 0
    Step 2: Return 1
In Function int main()
    Step 1: ประกาศและกำหนด arr[] เป็น {1, 8, 3, 4, 7}
    Step 2: ประกาศและกำหนด int n เป็น sizeof(arr)/sizeof(arr[0])
    Step 3: ถ้า arraySortedCheck(arr, n) แล้ว Print "อาร์เรย์อยู่ในลำดับที่เรียงแล้ว"
    Step 4: ถ้าไม่ใช่ Print "อาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว"
Stop

ตัวอย่างโค้ดแบบวนซ้ำ

#include <stdio.h>

int arraySortedCheck(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        // เมื่ออาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว
        if (arr[i] > arr[i+1])
            return 0;
    }
    // ตรวจสอบองค์ประกอบทั้งหมดแล้วและทั้งหมดเรียงลำดับ
    return 1;
}

int main() {
    int arr[] = {1, 8, 3, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    if (arraySortedCheck(arr, n)) {
        printf("อาร์เรย์อยู่ในลำดับที่เรียงแล้ว\n");
    } else {
        printf("อาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว\n");
    }
    return 0;
}

ผลลัพธ์

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

อาร์เรย์ไม่อยู่ในลำดับที่เรียงแล้ว