/
pancake_sort.cpp
79 lines (72 loc) · 2.22 KB
/
pancake_sort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <vector>
using namespace std;
// Reverses the array from index 0 to i
void flip(vector<int> &arr, int i)
{
int start = 0;
while (start < i)
{
int temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i--;
}
}
// Finds the index of the maximum element in the array
int findMaxIndex(vector<int> &arr, int n)
{
int maxIndex = 0;
for (int i = 1; i < n; i++)
{
// If the current element is greater than the maximum element so far,
if (arr[i] > arr[maxIndex])
{
maxIndex = i;
}
}
return maxIndex;
}
void pancakeSort(vector<int> &arr)
{
int n = arr.size();
for (int currSize = n; currSize > 1; currSize--)
{
// Below line of code will find the index of the maximum element in the current subvector
int maxIndex = findMaxIndex(arr, currSize);
// If the maximum element is not alreay at the end of thee subvector,
// perform the flipping operations to move that to correct position
if (maxIndex != currSize - 1)
{
flip(arr, maxIndex);
flip(arr, currSize - 1);
}
}
}
int main()
{
vector<int> arr = {6, 3, 9, 2, 5};
cout << "Original array: ";
for (int num : arr)
{
cout << num << " ";
}
cout << endl;
pancakeSort(arr);
cout << "Sorted array: ";
for (int num : arr)
{
cout << num << " ";
}
cout << endl;
return 0;
}
// //General steps we followed
// -->Start with the given unsorted array.
// -->Set the current size of the array as the total number of elements (n).
// -->Repeat the following steps until the current size becomes 1:
// --> Find the index of the maximum element in the subarray from index 0 to the current size minus 1. Let's call this index 'mi' (maxIndex).
// --> Flip the subarray from index 0 to 'mi', which will move the maximum element to the beginning of the array.
// --> Flip the entire subarray from index 0 to the current size minus 1, which will move the maximum element to its correct position at the end of the array.
// -->Once all the iterations are completed, the array will be sorted in ascending order.