What's wrong with my pancake sort?

[stonedviper]

Hello!

I have been working on the pancake sort algorithm and I challenged myself to implement this algorithm without using any resource from the internet.

but my program crashes can somebody explain?

Thank you for your answers!

#include "stdafx.h"
#include <iostream>
#include <stack>

void print(int *arr,const unsigned &k)
{
	for (unsigned i = 0; i < k; i++)
		std::cout << arr[i] << " ";

	std::cout << "\n";
}

bool sorted(int arr[],const unsigned &k)
{
	bool* check = new bool[k - 1];
	unsigned l = 0;
	for (unsigned i = 1; i < k; i++)
	{
		if (arr[i - 1] > arr[i])
			check[i - 1] = true;
	}
	for (unsigned i = 0; i < k - 1; i++)
	{
		if (check[i])
			l++;
	}

	delete[] check;

	if (l == k - 1)
		return true;
	else return false;
}

void pancake(int arr[],const unsigned &k)
{
	unsigned temp1 ,temp2;
	temp1 = arr[0];
	temp2 = 0;
	std::stack<int> spatula,spatula1;
	spatula.push(temp1);

	for (unsigned i = 1; i < k; i++)
	{
		spatula.push(i);
		if (arr[i] > temp1)
		{
			for (unsigned j = 0; j <= i; j++)
			{
				arr[j] = spatula.top();
				spatula.pop();
			}
			for (unsigned j = 0; j < k; j++)
				spatula1.push(arr[j]);
			for (unsigned j = 0; j < k; j++)
			{
				arr[j] = spatula1.top();
				spatula1.pop();
			}
			temp1 = arr[0];
			spatula.push(temp1);
		}
	}
	if (!sorted(arr,k))pancake(arr, k);
}


int main()
{
	const unsigned k = 10;
	int arr[10] = { 15,1,6,10,20,25,30,53,11,7 };
	print(arr, k);
	pancake(arr, k);
	print(arr, k);
}

[tpb]

You must have used some kind of resource otherwise you wouldn't know what a pancake sort was. Do you have pseudocode?

[stonedviper]

No the only thing I used for a resource is this https://www.youtube.com/watch?v=kk-_DDgoXfk

and as I said I tried using my skill to make this without looking for any sort of code

[tpb]

It was hard to help when I've never heard of a pancake sort. The video suggests that you try to sort a list of numbers where the only allowed operation on the list is flipping a section of the array over from a[0] to a[wherever] (could be the whole thing), like you were flipping the top x pancakes on a pile of pancakes with a spatula. That's pretty weird.

Do you mean to push i or arr[i] here?

		spatula.push(i);

It's needlessly expensive to pass an integer to a function as a const&. Just pass the (unsigned) integer.

Your "sorted" routine is more complicated than it needs to be.

bool sorted(int arr[], size_t sz)
{
	for (size_t i = 1; i < sz; i++)
		if (arr[i - 1] > arr[i])
			return false;
    return true;
}

I haven't looked at the pancake function sort yet.

[stonedviper]

the first one I swear I didn't see it I'm supposed to push arr[i] :D and thank you for the remark but it's still crashes

and the sorted function it's basically to see if the array is sorted to I can stop the recursion.
because this is a recursive function

and the pancake sort i was just curious about new algorithms and saw this and thought "Why not implement it" :D.

[tpb]

Why not implement it

Absolutely.

Can you describe your algorithm in words?

The recursion is not necessary and it's best to avoid recursion if it does nothing more than what a simple loop does. Just use a loop around the whole thing:

do {
    ...
} while (!sorted(arr, k));

BTW, I made an error in the sorted function above but it's fixed now.

[stonedviper]

But it's supposed to be a recursive algorithm.

If visualize it it's like flipping a pancake.You always start from the first and find a bigger one than it ten flip it on top and flip the whole structure and you do it recursively until it's sorted.

[tpb]

But it isn't really recursive, is it? If it can just be replaced with the simplest loop? But I haven't really thought about the sort much yet so I don't really know. Leave it the way it is if you want. It's actually not that bad and would be optimized into a loop by a good compiler anyway.

I think I spotted another error in your code:

			temp1 = arr[0];    // Line 60 above: should presumably be arr[i] 

But it will probably still crash. I think I've found where. Try inserting this test code before you access spatula.top() :

			        if (spatula.empty()) {
			            std::cerr << "empty!!\n";
			            std::exit(1);    //  #include <cstdlib>
			        }

[stonedviper]

it is empty and thank you but why?
I push arr[i] at the beginning of the loop why?

[tpb]

I don't really understand your algorithm so I'm not sure what's wrong.
I was able to implement the "naive" (not that I could think of anything better) algorithm of flipping the maximum to the top and then to the bottom (moving the bottom up as you go).

#include <iostream>

void print(int *arr, size_t sz) {
	for (size_t i = 0; i < sz; i++)
		std::cout << arr[i] << ' ';
	std::cout << '\n';
}

bool sorted(int arr[], size_t sz) {
	for (size_t i = 1; i < sz; i++)
		if (arr[i - 1] > arr[i])
			return false;
    return true;
}

size_t find_index_of_max(int *a, size_t sz) {
    size_t m = 0;
    for (size_t i = 1; i < sz; i++)
        if (a[i] > a[m])
            m = i;
    return m;
}

void flip(int *a, size_t m) {
    for (size_t i = 0; i <= m / 2; i++) {
        int t = a[i]; a[i] = a[m - i]; a[m - i] = t;
    }
}

void pancake(int arr[], size_t sz) {
    while (sz > 1) {
        size_t m = find_index_of_max(arr, sz);
        if (m < --sz) {   // if maximum is not already at the bottom
            flip(arr, m);    // flip it to the top
            flip(arr, sz);   // then flip it to the bottom
        }
    }
}

int main() {
	int arr[] = { 15,1,6,10,20,25,30,53,11,7,34,12,76,43,37 };
	size_t sz = sizeof arr / sizeof arr[0];
	print(arr, sz);
	pancake(arr, sz);
	print(arr, sz);
}

[lastchance]

#include <iostream>
#include <algorithm>
using namespace std;

template <typename T> void pancake( T *A, int size )
{
   if ( size > 1 )
   {
      reverse( min_element( A, A + size ), A + size );
      reverse( A, A + size );
      pancake( A + 1, size - 1 );
   }
}

int main()
{
   int A[] = { 3, 7, 3, 6, 2, 0, 4 };
   pancake( A, sizeof( A ) / sizeof( A[0] ) );
   for ( auto e : A ) cout << e << " ";
}

[tpb]

Very nice!
Here's the non-recursive version:

template <typename T> void pancake( T *A, size_t size )
{
   for (T *end = A + size; A < end; A++ )
   {
      reverse( min_element( A, end ), end );
      reverse( A, end );
   }
}

[stonedviper]

Sorry for the late reply haven't checked any of the solutions that you gave I will try them now.

Still I can't believe that pancake sort isn't that famous considering it's a recursive algorithm.