Given an unsorted array, this function uses only flip operation to sort the array. flip is the operation which reverses the array.
Example
INPUT:
arr[] = {4, 1, 10, 5}
OUTPUT:
{1, 4, 5, 10}
Time Complexity: O()
The main idea is to find maximum element in the array and place it in the end of the array and decrease the size of the array.
Algorithm
Till the size of the array is greater than 1, decrement size
1. Find the maximum element in the current size array
2. flip the array till maximum number ie, now maximum number is at starting of the array
3. Now, flip the array of current size ie, now maximum number is at the end of the array
Print the sorted array
C++ Program
#include <bits/stdc++.h>
using namespace std;
//finding the maximum number in the array till the size mentioned
int maximumNumber(int arr[], int curr_size)
{
int m =0, k =0;
for (int i = 0; i < curr_size; ++i)
{
if (arr[i]>m)
{
m = arr[i];
k = i;
}
}
return k;
}
int flip(int arr[], int m) // Flipping the array till the index m
{
int t;
for(int i = 0; i< m; ++i)
{
t = arr[i];
arr[i] = arr[m];
arr[m] = t;
m--;
}
}
int pancakeSort(int arr[], int n)
{
for (int curr_size = n; curr_size > 1 ; --curr_size)
{
int m = maximumNumber(arr, curr_size);
if (m != curr_size -1)
{
flip(arr, m);//flipping till the max element ie, includinig max
flip(arr, curr_size-1);// To place the max element at the end of the array
}
}
//Printing the sorted array
cout<<"The sorted array is [ ";
for (int i = 0; i < n; ++i)
{
cout<<arr[i]<<" ";
}
cout<<"]"<<endl;
}
int main()
{
int arr[]= {4, 1, 10, 23, 5}; //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
pancakeSort(arr,n);
return 0;
}
