What's wrong with my pancake sort?

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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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);
}
Last edited on
You must have used some kind of resource otherwise you wouldn't know what a pancake sort was. Do you have pseudocode?
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
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.
1
2
3
4
5
6
7
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.
Last edited on
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.
Last edited on
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:
1
2
3
do {
    ...
} while (!sorted(arr, k));


BTW, I made an error in the sorted function above but it's fixed now.
Last edited on
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.
Last edited on
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() :
1
2
3
4
			        if (spatula.empty()) {
			            std::cerr << "empty!!\n";
			            std::exit(1);    //  #include <cstdlib>
			        }

Last edited on
it is empty and thank you but why?
I push arr[i] at the beginning of the loop why?
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).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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);
}

Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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 << " ";
}
Very nice!
Here's the non-recursive version:
1
2
3
4
5
6
7
8
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 );
   }
}

Last edited on
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.
Topic archived. No new replies allowed.