pancake_sort.cpp File Reference

pancake sort sorts a disordered stack of pancakes by flipping any number of pancakes using a spatula using minimum number of flips. More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for pancake_sort.cpp:

Namespaces
namespace	sorting
	for working with vectors
namespace	pancake_sort
	Functions for Pancake sort algorithm.

Functions
template<typename T >
void	sorting::pancake_sort::reverse (std::vector< T > &arr, int start, int end)
	This implementation is for reversing elements in a a C-style array .
template<typename T >
int	sorting::pancake_sort::pancakeSort (std::vector< T > &arr, int size)
	This implementation is for a C-style array input that gets modified in place.
static void	test ()
	Test implementations.
int	main ()
	Main function.

Detailed Description

pancake sort sorts a disordered stack of pancakes by flipping any number of pancakes using a spatula using minimum number of flips.

Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible. Overall time complexity of pancake sort is O(n^2) For example: example 1:- Disordered pancake sizes: {2,5,3,7,8} Sorted: {2,3,5,7,8} For example: example 2:- Disordered pancake sizes: {22,51,37,73,81} Sorted: {22,37,51,73,81}

Author

Divyansh Gupta

See also

more on Pancake sort

related problem at Leetcode

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();
    return 0;
}

Here is the call graph for this function:

pancakeSort()

template<typename T >

int sorting::pancake_sort::pancakeSort	(	std::vector< T > &	arr,
		int	size )

This implementation is for a C-style array input that gets modified in place.

Parameters

[start,end]	arr our vector of elements.
size	size of given array

Returns

0 on exit

                                             {
    for (int i = size; i > 1; --i) {
        int max_index = 0, j = 0;  // intialize some variables.
        T max_value = 0;
        for (j = 0; j < i; j++) {
            if (arr[j] >= max_value) {
                max_value = arr[j];
                max_index = j;
            }
        }
        if (max_index != i - 1)  // check for reversing
        {
            reverse(arr, 0, max_index);
            reverse(arr, 0, i - 1);
        }
    }
    return 0;
}

Here is the call graph for this function:

reverse()

template<typename T >

void sorting::pancake_sort::reverse	(	std::vector< T > &	arr,
		int	start,
		int	end )

This implementation is for reversing elements in a a C-style array .

Parameters

[start,end]	arr our vector of elements.
start	starting index of array
end	ending index of array

Returns

void

                                                    {
    T temp;  // Temporary variable
    while (start <= end) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

test()

static void test ( )

static

Test implementations.

Returns

void

                   {
    // example 1: vector of int
    const int size1 = 7;
    std::cout << "\nTest 1- as std::vector<int>...";
    std::vector<int> arr1 = {23, 10, 20, 11, 12, 6, 7};
    sorting::pancake_sort::pancakeSort(arr1, size1);
    assert(std::is_sorted(arr1.begin(), arr1.end()));
    std::cout << "Passed\n";
    for (int i = 0; i < size1; i++) {
        std::cout << arr1[i] << " ,";
    }
    std::cout << std::endl;
 
    // example 2: vector of double
    const int size2 = 8;
    std::cout << "\nTest 2- as std::vector<double>...";
    std::vector<double> arr2 = {23.56, 10.62, 200.78, 111.484,
                                3.9,   1.2,   61.77,  79.6};
    sorting::pancake_sort::pancakeSort(arr2, size2);
    assert(std::is_sorted(arr2.begin(), arr2.end()));
    std::cout << "Passed\n";
    for (int i = 0; i < size2; i++) {
        std::cout << arr2[i] << ", ";
    }
    std::cout << std::endl;
 
    // example 3:vector of float
    const int size3 = 7;
    std::cout << "\nTest 3- as std::vector<float>...";
    std::vector<float> arr3 = {6.56, 12.62, 200.78, 768.484, 19.27, 68.87, 9.6};
    sorting::pancake_sort::pancakeSort(arr3, size3);
    assert(std::is_sorted(arr3.begin(), arr3.end()));
    std::cout << "Passed\n";
    for (int i = 0; i < size3; i++) {
        std::cout << arr3[i] << ", ";
    }
    std::cout << std::endl;
}

Here is the call graph for this function: