Skip to main content

Pancake Sort

Pancake sort is a sorting algorithm that sorts an array by repeatedly flipping subarrays of the array. It was developed by William Gates in 1970.

The algorithm works by selecting the largest element in the array and flipping the subarray from the beginning of the array up to that element. This moves the largest element to the beginning of the array. Then, the entire array is flipped, moving the largest element to the end of the array. This process is repeated for the remaining elements, with the size of the subarray being reduced by one for each iteration.

Here are the basic steps of the algorithm:

  1. Start with the original array.
  2. For each iteration: a. Find the index of the largest element in the unsorted portion of the array. b. Flip the subarray from the beginning of the array up to that index. c. Flip the entire array, moving the largest element to the end of the unsorted portion.
  3. After all iterations, the array is sorted.

The time complexity of pancake sort is O(n^2), where n is the number of elements in the array. This makes it less efficient than many other sorting algorithms, such as quicksort and merge sort, which have a time complexity of O(n log n). However, pancake sort has the advantage of being easy to understand and implement, and it can be useful in certain specialized situations where the number of possible values is small.

Here given code implementation process.

//C program for
//Sort array by using pancake sort 
#include <stdio.h>

// Reverse array elements
void reverse_element(int arr[], int size)
{
	int temp = 0;
	int front = 0;
	int tail = size;
	while (front < tail)
	{
		//Swap elements
		temp = arr[front];
		arr[front] = arr[tail];
		arr[tail] = temp;
		//Modified element location
		front++;
		tail--;
	}
}
// This are finding max element and returning its location
int max_element_location(int arr[], int size)
{
	int i = 0;
	int result = 0;
	for (i = 0; i < size; ++i)
	{
		if (arr[i] > arr[result])
		{
			result = i;
		}
	}
	return result;
}
// Perform the pancake sort of given array
void pancake_sort(int arr[], int n)
{
	for (int size = n; size > 1; size--)
	{
		int location = max_element_location(arr, size);
		if (location != size - 1)
		{
			reverse_element(arr, location);
			reverse_element(arr, size - 1);
		}
	}
}
//print the array elements
void display(int arr[], int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		printf("  %d", arr[i]);
	}
}
int main()
{
	//Define the collection of integer elements
	int arr[] = {
		7,
		2,
		90,
		4,
		1,
		46,
		12,
		6,
		3,
		2
	};
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("After Sort : ");
	display(arr, size);
	pancake_sort(arr, size);
	printf("\nBefore Sort  : ");
	display(arr, size);
	return 0;
}

Output

After Sort :   7  2  90  4  1  46  12  6  3  2
Before Sort  :   1  2  2  3  4  6  7  12  46  90
// Java program 
// Sort array by using pancake sort 
class MySort
{
	// Reverse array elements
	public void reverse_element(int[] arr, int size)
	{
		int temp = 0;
		int front = 0;
		int tail = size;
		while (front < tail)
		{
			//Swap elements
			temp = arr[front];
			arr[front] = arr[tail];
			arr[tail] = temp;
			//Modified element location
			front++;
			tail--;
		}
	}
	// This are finding max element and returning its location
	public int max_element_location(int[] arr, int size)
	{
		int i = 0;
		int result = 0;
		for (i = 0; i < size; ++i)
		{
			if (arr[i] > arr[result])
			{
				result = i;
			}
		}
		return result;
	}
	// Perform the pancake sort of given array
	public void pancake_sort(int[] arr, int n)
	{
		for (int size = n; size > 1; size--)
		{
			int location = max_element_location(arr, size);
			if (location != size - 1)
			{
				reverse_element(arr, location);
				reverse_element(arr, size - 1);
			}
		}
	}
	//print the array elements
	public void display(int[] arr, int size)
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			System.out.print("  " + arr[i]);
		}
	}
	public static void main(String[] args)
	{
		MySort obj = new MySort();
		//Define the collection of integer elements
		int[] arr = {
			7,
			2,
			90,
			4,
			1,
			46,
			12,
			6,
			3,
			2
		};
		int size = arr.length;
		System.out.print("After Sort : ");
		obj.display(arr, size);
		obj.pancake_sort(arr, size);
		System.out.print("\nBefore Sort  : ");
		obj.display(arr, size);
	}
}

Output

After Sort :   7  2  90  4  1  46  12  6  3  2
Before Sort  :   1  2  2  3  4  6  7  12  46  90
//Include header file
#include <iostream>

using namespace std;
// C++ program 
// Sort array by using pancake sort 
class MySort
{
	public:
		// Reverse array elements
		void reverse_element(int arr[], int size)
		{
			int temp = 0;
			int front = 0;
			int tail = size;
			while (front < tail)
			{
				//Swap elements
				temp = arr[front];
				arr[front] = arr[tail];
				arr[tail] = temp;
				//Modified element location
				front++;
				tail--;
			}
		}
	// This are finding max element and returning its location
	int max_element_location(int arr[], int size)
	{
		int i = 0;
		int result = 0;
		for (i = 0; i < size; ++i)
		{
			if (arr[i] > arr[result])
			{
				result = i;
			}
		}
		return result;
	}
	// Perform the pancake sort of given array
	void pancake_sort(int arr[], int n)
	{
		for (int size = n; size > 1; size--)
		{
			int location = this->max_element_location(arr, size);
			if (location != size - 1)
			{
				this->reverse_element(arr, location);
				this->reverse_element(arr, size - 1);
			}
		}
	}
	//print the array elements
	void display(int arr[], int size)
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			cout << "  " << arr[i];
		}
	}
};
int main()
{
	MySort obj = MySort();
	int arr[] = {
		7 , 2 , 90 , 4 , 1 , 46 , 12 , 6 , 3 , 2
	};
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "After Sort : ";
	obj.display(arr, size);
	obj.pancake_sort(arr, size);
	cout << "\nBefore Sort  : ";
	obj.display(arr, size);
	return 0;
}

Output

After Sort :   7  2  90  4  1  46  12  6  3  2
Before Sort  :   1  2  2  3  4  6  7  12  46  90
//Include namespace system
using System;
// C# program 
// Sort array by using pancake sort 
class MySort
{
	// Reverse array elements
	public void reverse_element(int[] arr, int size)
	{
		int temp = 0;
		int front = 0;
		int tail = size;
		while (front < tail)
		{
			//Swap elements
			temp = arr[front];
			arr[front] = arr[tail];
			arr[tail] = temp;
			//Modified element location
			front++;
			tail--;
		}
	}
	// This are finding max element and returning its location
	public int max_element_location(int[] arr, int size)
	{
		int i = 0;
		int result = 0;
		for (i = 0; i < size; ++i)
		{
			if (arr[i] > arr[result])
			{
				result = i;
			}
		}
		return result;
	}
	// Perform the pancake sort of given array
	public void pancake_sort(int[] arr, int n)
	{
		for (int size = n; size > 1; size--)
		{
			int location = max_element_location(arr, size);
			if (location != size - 1)
			{
				reverse_element(arr, location);
				reverse_element(arr, size - 1);
			}
		}
	}
	//print the array elements
	public void display(int[] arr, int size)
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			Console.Write("  " + arr[i]);
		}
	}
	public static void Main(String[] args)
	{
		MySort obj = new MySort();
		int[] arr = {
			7 , 2 , 90 , 4 , 1 , 46 , 12 , 6 , 3 , 2
		};
		int size = arr.Length;
		Console.Write("After Sort : ");
		obj.display(arr, size);
		obj.pancake_sort(arr, size);
		Console.Write("\nBefore Sort  : ");
		obj.display(arr, size);
	}
}

Output

After Sort :   7  2  90  4  1  46  12  6  3  2
Before Sort  :   1  2  2  3  4  6  7  12  46  90
<?php
// Php program 
// Sort array by using pancake sort 
class MySort
{
	// Reverse array elements
	public	function reverse_element( & $arr, $size)
	{
		$temp = 0;
		$front = 0;
		$tail = $size;
		while ($front < $tail)
		{
			//Swap elements
			$temp = $arr[$front];
			$arr[$front] = $arr[$tail];
			$arr[$tail] = $temp;
			//Modified element location
			$front++;
			$tail--;
		}
	}
	// This are finding max element and returning its location
	public	function max_element_location( & $arr, $size)
	{
		$i = 0;
		$result = 0;
		for ($i = 0; $i < $size; ++$i)
		{
			if ($arr[$i] > $arr[$result])
			{
				$result = $i;
			}
		}
		return $result;
	}
	// Perform the pancake sort of given array
	public	function pancake_sort( & $arr, $n)
	{
		for ($size = $n; $size > 1; $size--)
		{
			$location = $this->max_element_location($arr, $size);
			if ($location != $size - 1)
			{
				$this->reverse_element($arr, $location);
				$this->reverse_element($arr, $size - 1);
			}
		}
	}
	//print the array elements
	public	function display( & $arr, $size)
	{
		$i = 0;
		for ($i = 0; $i < $size; $i++)
		{
			echo "  ". $arr[$i];
		}
	}
}

function main()
{
	$obj = new MySort();
	//Define the collection of integer elements
	$arr = array(7, 2, 90, 4, 1, 46, 12, 6, 3, 2);
	$size = count($arr);
	echo "After Sort : ";
	$obj->display($arr, $size);
	$obj->pancake_sort($arr, $size);
	echo "\nBefore Sort  : ";
	$obj->display($arr, $size);
}
main();

Output

After Sort :   7  2  90  4  1  46  12  6  3  2
Before Sort  :   1  2  2  3  4  6  7  12  46  90
// Node Js program 
// Sort array by using pancake sort 
class MySort
{
	// Reverse array elements
	reverse_element(arr, size)
	{
		var temp = 0;
		var front = 0;
		var tail = size;
		while (front < tail)
		{
			//Swap elements
			temp = arr[front];
			arr[front] = arr[tail];
			arr[tail] = temp;
			//Modified element location
			front++;
			tail--;
		}
	}
	// This are finding max element and returning its location
	max_element_location(arr, size)
	{
		var i = 0;
		var result = 0;
		for (i = 0; i < size; ++i)
		{
			if (arr[i] > arr[result])
			{
				result = i;
			}
		}
		return result;
	}
	// Perform the pancake sort of given array
	pancake_sort(arr, n)
	{
		for (var size = n; size > 1; size--)
		{
			var location = this.max_element_location(arr, size);
			if (location != size - 1)
			{
				this.reverse_element(arr, location);
				this.reverse_element(arr, size - 1);
			}
		}
	}
	//print the array elements
	display(arr, size)
	{
		var i = 0;
		for (i = 0; i < size; i++)
		{
			process.stdout.write("  " + arr[i]);
		}
	}
}

function main()
{
	var obj = new MySort();
	//Define the collection of integer elements
	var arr = [7, 2, 90, 4, 1, 46, 12, 6, 3, 2];
	var size = arr.length;
	process.stdout.write("After Sort : ");
	obj.display(arr, size);
	obj.pancake_sort(arr, size);
	process.stdout.write("\nBefore Sort  : ");
	obj.display(arr, size);
}
main();

Output

After Sort :   7  2  90  4  1  46  12  6  3  2
Before Sort  :   1  2  2  3  4  6  7  12  46  90
#  Python 3 program 
#  Sort array by using pancake sort 
class MySort :
	#  Reverse array elements
	def reverse_element(self, arr, size) :
		temp = 0
		front = 0
		tail = size
		while (front < tail) :
			# Swap elements
			temp = arr[front]
			arr[front] = arr[tail]
			arr[tail] = temp
			# Modified element location
			front += 1
			tail -= 1
		
	
	#  This are finding max element and returning its location
	def max_element_location(self, arr, size) :
		i = 0
		result = 0
		i = 0
		while (i < size) :
			if (arr[i] > arr[result]) :
				result = i
			
			i += 1
		
		return result
	
	#  Perform the pancake sort of given array
	def pancake_sort(self, arr, n) :
		size = n
		while (size > 1) :
			location = self.max_element_location(arr, size)
			if (location != size - 1) :
				self.reverse_element(arr, location)
				self.reverse_element(arr, size - 1)
			
			size -= 1
		
	
	# print the array elements
	def display(self, arr, size) :
		i = 0
		i = 0
		while (i < size) :
			print("  ", arr[i], end = "")
			i += 1
		
	

def main() :
	obj = MySort()
	# Define the collection of integer elements
	arr = [7, 2, 90, 4, 1, 46, 12, 6, 3, 2]
	size = len(arr)
	print("After Sort : ", end = "")
	obj.display(arr, size)
	obj.pancake_sort(arr, size)
	print("\nBefore Sort  : ", end = "")
	obj.display(arr, size)

if __name__ == "__main__": main()

Output

After Sort :    7   2   90   4   1   46   12   6   3   2
Before Sort  :    1   2   2   3   4   6   7   12   46   90
#  Ruby program 
#  Sort array by using pancake sort 
class MySort

	#  Reverse array elements
	def reverse_element(arr, size)
	
		temp = 0
		front = 0
		tail = size
		while (front < tail)
		
			# Swap elements
			temp = arr[front]
			arr[front] = arr[tail]
			arr[tail] = temp
			# Modified element location
			front += 1
			tail -= 1
		end
	end
	#  This are finding max element and returning its location
	def max_element_location(arr, size)
	
		i = 0
		result = 0
		i = 0
		while (i < size)
		
			if (arr[i] > arr[result])
			
				result = i
			end
			i += 1
		end
		return result
	end
	#  Perform the pancake sort of given array
	def pancake_sort(arr, n)
	
		size = n
		while (size > 1)
		
			location = self.max_element_location(arr, size)
			if (location != size - 1)
			
				self.reverse_element(arr, location)
				self.reverse_element(arr, size - 1)
			end
			size -= 1
		end
	end
	# print the array elements
	def display(arr, size)
	
		i = 0
		i = 0
		while (i < size)
		
			print("  ", arr[i])
			i += 1
		end
	end
end
def main()

	obj = MySort.new()
	# Define the collection of integer elements
	arr = [7, 2, 90, 4, 1, 46, 12, 6, 3, 2]
	size = arr.length
	print("After Sort : ")
	obj.display(arr, size)
	obj.pancake_sort(arr, size)
	print("\nBefore Sort  : ")
	obj.display(arr, size)
end
main()

Output

After Sort :   7  2  90  4  1  46  12  6  3  2
Before Sort  :   1  2  2  3  4  6  7  12  46  90
// Scala program 
// Sort array by using pancake sort 
class MySort
{
	// Reverse array elements
	def reverse_element(arr: Array[Int], size: Int): Unit = {
		var temp: Int = 0;
		var front: Int = 0;
		var tail: Int = size;
		while (front < tail)
		{
			//Swap elements
			temp = arr(front);
			arr(front) = arr(tail);
			arr(tail) = temp;
			//Modified element location
			front += 1;
			tail -= 1;
		}
	}
	// This are finding max element and returning its location
	def max_element_location(arr: Array[Int], size: Int): Int = {
		var i: Int = 0;
		var result: Int = 0;
		i = 0;
		while (i < size)
		{
			if (arr(i) > arr(result))
			{
				result = i;
			}
			i += 1;
		}
		return result;
	}
	// Perform the pancake sort of given array
	def pancake_sort(arr: Array[Int], n: Int): Unit = {
		var size: Int = n;
		while (size > 1)
		{
			var location: Int = max_element_location(arr, size);
			if (location != size - 1)
			{
				reverse_element(arr, location);
				reverse_element(arr, size - 1);
			}
			size -= 1;
		}
	}
	//print the array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		i = 0;
		while (i < size)
		{
			print("  " + arr(i));
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MySort = new MySort();
		//Define the collection of integer elements
		var arr: Array[Int] = Array(7, 2, 90, 4, 1, 46, 12, 6, 3, 2);
		var size: Int = arr.length;
		print("After Sort : ");
		obj.display(arr, size);
		obj.pancake_sort(arr, size);
		print("\nBefore Sort  : ");
		obj.display(arr, size);
	}
}

Output

After Sort :   7  2  90  4  1  46  12  6  3  2
Before Sort  :   1  2  2  3  4  6  7  12  46  90
// Swift program 
// Sort array by using pancake sort 
class MySort
{
	// Reverse array elements
	func reverse_element(_ arr: inout[Int], _ size: Int)
	{
		var temp: Int = 0;
		var front: Int = 0;
		var tail: Int = size;
		while (front < tail)
		{
			//Swap elements
			temp = arr[front];
			arr[front] = arr[tail];
			arr[tail] = temp;
			//Modified element location
			front += 1;
			tail -= 1;
		}
	}
	// This are finding max element and returning its location
	func max_element_location(_ arr: [Int], _ size: Int) -> Int
	{
		var i: Int = 0;
		var result: Int = 0;
		i = 0;
		while (i < size)
		{
			if (arr[i] > arr[result])
			{
				result = i;
			}
			i += 1;
		}
		return result;
	}
	// Perform the pancake sort of given array
	func pancake_sort(_ arr: inout[Int], _ n: Int)
	{
		var size: Int = n;
		while (size > 1)
		{
			let location: Int = self.max_element_location(arr, size);
			if (location != size - 1)
			{
				self.reverse_element(&arr, location);
				self.reverse_element(&arr, size - 1);
			}
			size -= 1;
		}
	}
	//print the array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		i = 0;
		while (i < size)
		{
			print("  ", arr[i], terminator: "");
			i += 1;
		}
	}
}
func main()
{
	let obj: MySort = MySort();
	//Define the collection of integer elements
	var arr: [Int] = [7, 2, 90, 4, 1, 46, 12, 6, 3, 2];
	let size: Int = arr.count;
	print("After Sort : ", terminator: "");
	obj.display(arr, size);
	obj.pancake_sort(&arr, size);
	print("\nBefore Sort  : ", terminator: "");
	obj.display(arr, size);
}
main();

Output

After Sort :    7   2   90   4   1   46   12   6   3   2
Before Sort  :    1   2   2   3   4   6   7   12   46   90
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment