Pancake sorting

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;
}
Try It


Next > < Prev
Scroll to Top