Cho một mảng arr [] với n số phần tử, nhiệm vụ của chúng ta là kiểm tra xem mảng đã cho có theo thứ tự đã sắp xếp hay không, Nếu nó theo thứ tự đã sắp xếp thì in “Mảng theo thứ tự đã sắp xếp”, nếu không thì in “Mảng không theo thứ tự được sắp xếp ”.
Để giải quyết vấn đề đã nêu ở trên, chúng ta có thể sử dụng phương pháp Lặp lại hoặc Đệ quy, chúng ta sẽ thảo luận cả hai.
Phương pháp tiếp cận đệ quy
Vậy, cách tiếp cận Đệ quy là gì? Trong cách tiếp cận đệ quy, chúng ta gọi đệ quy một hàm lặp đi lặp lại cho đến khi chúng ta nhận được kết quả mong muốn. Trong cách tiếp cận đệ quy, các giá trị do hàm trả về được lưu trữ trong bộ nhớ ngăn xếp.
Đầu vào
arr[] = {12, 13, 14, 16, 18} Đầu ra
The array is in sorted order
Giải thích - 12 <13 <14 <16 <18, do đó, mảng được sắp xếp
Đầu vào
arr[] = {2, 1, 3, 5, 6} Đầu ra
The array is not in sorted order
Giải thích - 2 không nhỏ hơn 1, do đó, nó không theo thứ tự đã sắp xếp.
Phương pháp tiếp cận được sử dụng bên dưới như sau để giải quyết vấn đề -
-
Lấy một mảng arr [] làm đầu vào và khởi tạo n với kích thước của một mảng.
-
Kiểm tra xem chúng ta đã đến đầu một mảng chưa, hãy trả về true.
-
Kiểm tra xem phần tử trước của mảng không nhỏ hơn phần tử tiếp theo hay không, trả về false.
-
Giảm dần n và chuyển sang bước 2.
Thuật toán
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 Ví dụ
//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;
} Đầu ra
Nếu chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
The array is in sorted order
Phương pháp tiếp cận lặp lại
Trong cách tiếp cận lặp, chúng tôi sử dụng các vòng lặp như vòng lặp for, vòng lặp while hoặc vòng lặp do-while thực thi các câu lệnh cho đến khi điều kiện giữ đúng nghĩa là 1.
Đầu vào
arr[] = {12, 13, 14, 16, 18} Đầu ra
The array is in sorted order
Giải thích - 12 <13 <14 <16 <18, do đó, mảng được sắp xếp theo thứ tự
Đầu vào
arr[] = {2, 1, 3, 5, 6} Đầu ra
The array is not in sorted order
Giải thích 2 không nhỏ hơn 1, do đó, nó không theo thứ tự đã sắp xếp.
Phương pháp tiếp cận được sử dụng dưới đây như sau để giải quyết vấn đề
-
Lấy arr đầu vào [].
-
Lặp lại cho đến khi chúng ta đến cuối mảng đó.
-
Kiểm tra nếu phần tử hiện tại không nhỏ hơn phần tử tiếp theo, trả về false và thoát.
-
Còn nữa thì tiếp tục.
-
-
Chuyển sang bước 2.
Thuật toán
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 Ví dụ
//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;
} Đầu ra
Nếu chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
The array is in sorted order