Sponsored
Sponsored
This approach involves sorting the array by repeatedly moving the largest unsorted element to its correct position at the end. This is achieved by two flips: first flipping the array to get the largest element to the front, and then flipping up to the end of the unsorted part to push the largest element to the end.
Time Complexity: O(n^2) due to nested loops finding the maximum index and reversing. Space Complexity: O(1) due to in-place operations.
1#include <stdio.h>
2#include <stdlib.h>
3
4void reverse(int* arr, int k) {
5 for (int i = 0, j = k; i < j; i++, j--) {
6 int temp = arr[i];
7 arr[i] = arr[j];
8 arr[j] = temp;
9 }
10}
11
12int findMaxIndex(int* arr, int n) {
13 int maxIdx = 0;
14 for (int i = 1; i <= n; i++) {
15 if (arr[i] > arr[maxIdx]) {
16 maxIdx = i;
17 }
18 }
19 return maxIdx;
20}
21
22void pancakeSort(int* arr, int n) {
23 if (n <= 1) return;
24 for (int i = n - 1; i > 0; i--) {
25 int maxIndex = findMaxIndex(arr, i);
26 if (maxIndex != i) {
27 reverse(arr, maxIndex);
28 reverse(arr, i);
29 }
30 }
31}
32
33int main() {
34 int arr[] = {3, 2, 4, 1};
35 int n = sizeof(arr) / sizeof(arr[0]);
36 pancakeSort(arr, n);
37 for (int i = 0; i < n; i++) {
38 printf("%d ", arr[i]);
39 }
40 return 0;
41}The C solution identifies the maximum element in the unsorted portion of the array and brings it to the 0th index if it isn't already there. Then, it reverses the entire array up to the current unsorted subarray length to place the maximum at its sorted position. This process is repeated for the rest of the elements.