Home » Interview Questions » Array Interview Questions » Pancake sorting

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

READ  First Bad Version

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions