ให้อาร์เรย์ arr[] มีองค์ประกอบจำนวน n รายการ หน้าที่ของเราคือตรวจสอบว่าอาร์เรย์ที่ระบุอยู่ในลำดับการจัดเรียงหรือไม่ ถ้าอยู่ในลำดับการจัดเรียง ให้พิมพ์ "อาร์เรย์อยู่ในลำดับการจัดเรียง" หรือพิมพ์ "อาร์เรย์" ไม่เรียงลำดับ”
ในการแก้ปัญหาดังกล่าว เราสามารถใช้วิธี Iterative หรือ Recursive ได้ เราจะพูดคุยกันทั้งสองเรื่อง
แนวทางแบบเรียกซ้ำ
ดังนั้นวิธีการแบบเรียกซ้ำคืออะไร? ในวิธีแบบเรียกซ้ำ เราเรียกฟังก์ชันซ้ำแล้วซ้ำอีกจนกว่าเราจะได้ผลลัพธ์ที่ต้องการ ในแนวทางแบบเรียกซ้ำ ค่าที่ส่งคืนโดยฟังก์ชันจะถูกเก็บไว้ในหน่วยความจำสแต็ก
ป้อนข้อมูล
arr[] = {12, 13, 14, 16, 18} ผลผลิต
The array is in sorted order
คำอธิบาย − 12 <13 <14 <16 <18 ดังนั้น ใช่ อาร์เรย์ถูกจัดเรียงแล้ว
ป้อนข้อมูล
arr[] = {2, 1, 3, 5, 6} ผลผลิต
The array is not in sorted order
คำอธิบาย − 2 ไม่เล็กกว่า 1 จึงไม่เรียงลำดับ
แนวทางที่ใช้ด้านล่างมีดังต่อไปนี้ในการแก้ปัญหา -
-
รับอาร์เรย์ arr[] เป็นอินพุตและเริ่มต้น n ด้วยขนาดของอาร์เรย์
-
ตรวจสอบว่าเรามาถึงจุดเริ่มต้นของอาร์เรย์หรือไม่ คืนค่า true
-
ตรวจสอบว่าองค์ประกอบก่อนหน้าของอาร์เรย์ไม่เล็กกว่าองค์ประกอบถัดไป ให้คืนค่าเท็จ
-
ลดระดับ n และไปที่ขั้นตอนที่ 2
อัลกอริทึม
Start
In function int arraySortedCheck(int arr[], int n)
Step 1→ If n == 1 || n == 0 then,
Return 1
Step 2→ If arr[n-1] < arr[n-2] then,
Return 0
Step 3→ Return arraySortedCheck(arr, n-1)
In Function int main(int argc, char const *argv[])
Step 1→ Declare and initialize arr[] as {1,8,3,4,7}
Step 2→ Declare and initialize int n as sizeof(arr)/sizeof(arr[0])
Step 3→ If arraySortedCheck(arr, n) then,
Print "Array is in sorted order”
Step 4→ Else
Print "Array is not in sorted order”
Stop ตัวอย่าง
//Recursive approach
#include <stdio.h>
//Recursive function to check if it
//is in sorted order or not
int arraySortedCheck(int arr[], int n){
//all elements are checked and
//all are in sorted order
if (n == 1 || n == 0)
return 1;
//when an array is not in sorted order
if(arr[n-1] < arr[n-2])
return 0;
return arraySortedCheck(arr, n-1);
}
int main(int argc, char const *argv[]){
int arr[] = {1,8,3,4,7};
int n = sizeof(arr)/sizeof(arr[0]);
if(arraySortedCheck(arr, n)){
printf("Array is in sorted order\n");
}
else
printf("Array is not in sorted order\n");
return 0;
} ผลลัพธ์
หากรันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้ -
The array is in sorted order
แนวทางการทำซ้ำ
ในการวนซ้ำ เราใช้ลูปเช่น for-loop, while-loop หรือ do-while loop ซึ่งดำเนินการคำสั่งจนกว่าเงื่อนไขจะเป็นจริงซึ่งหมายถึง 1
ป้อนข้อมูล
arr[] = {12, 13, 14, 16, 18} ผลผลิต
The array is in sorted order
คำอธิบาย − 12 <13 <14 <16 <18 ใช่ อาร์เรย์อยู่ในลำดับการจัดเรียง
ป้อนข้อมูล
arr[] = {2, 1, 3, 5, 6} ผลผลิต
The array is not in sorted order
คำอธิบาย 2 ไม่เล็กกว่า 1 จึงไม่เรียงลำดับ
แนวทางที่ใช้ด้านล่างมีดังต่อไปนี้ในการแก้ปัญหา
-
รับอินพุต arr[].
-
วนซ้ำจนกว่าจะถึงจุดสิ้นสุดของอาร์เรย์นั้น
-
ตรวจสอบว่าองค์ประกอบปัจจุบันไม่เล็กกว่าองค์ประกอบถัดไป ให้คืนค่าเท็จและออก
-
อย่างอื่นต่อ
-
-
ไปที่ขั้นตอนที่ 2
อัลกอริทึม
Start
In function int arraySortedCheck(int arr[], int n)
Step 1 → Loop For i = 0 and i < n and ++i
If arr[n-1] < arr[n-2] then,
Return 0
Step 2→ Return 1
In Function int main(int argc, char const *argv[])
Step 1→ Declare and initialize arr[] as {1,8,3,4,7}
Step 2→ Declare and initialize int n as sizeof(arr)/sizeof(arr[0])
Step 3→ If arraySortedCheck(arr, n) then,
Print "Array is in sorted order”
Step 4→ Else
Print "Array is not in sorted order”
Stop ตัวอย่าง
//Iterative approach
#include <stdio.h>
int arraySortedCheck(int arr[], int n){
for (int i = 0; i < n; ++i){
//when an array is not in sorted order
if(arr[n-1] < arr[n-2])
return 0;
}
//all elements are checked and
//all are in sorted order
return 1;
}
int main(int argc, char const *argv[]){
int arr[] = {1,8,3,4,7};
int n = sizeof(arr)/sizeof(arr[0]);
if(arraySortedCheck(arr, n)){
printf("Array is in sorted order\n");
}
else
printf("Array is not in sorted order\n");
return 0;
} ผลลัพธ์
หากรันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้ -
The array is in sorted order
