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:
- Start with the original array.
- 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.
- 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
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