Talk:Pancake sorting

Algorithm?

How is this article describing an algorithm? It seems to be describing a problem, yet it's listed as a sorting algorithm on multiple other pages. 107.3.154.208 (talk) 19:51, 17 August 2013 (UTC)

Nerd Talk

The main page was written by nerds for nerds. It needs to be completely re-written in ENGLISH. Remember nerds, an encyclopaedia is supposed to be able to make even the most complex of subject matters understandable at a basic level by everyone and anyone. — Preceding unsigned comment added by 116.30.147.34 (talk) 16:04, 4 August 2012 (UTC)

That is an unrealistic aim. A more realistic aim for an article is to make the lead and the first half of the article easily understandable to someone who might reasonably be expected to learn about it in the next six months. Dmcq (talk) 21:16, 4 August 2012 (UTC)

Dear IP address, perhaps a "cool boy" like yourself is not supposed to read a computer science article. You may refer to the article about "pancake" as it definitely suits your kind better. Thanks for your attention. 128.97.84.170 (talk) 23:10, 16 January 2014 (UTC)

Hanoi

Reminds me of the Tower of Hanoi problem -gtaylor 16:44, 29 April 2005 (UTC)

Actually it's quite different:

• A larger pancake can be above a smaller one
• There is only one stack as opposed to 3 in tower of hanoi.

This changes the problem immensely. The bounds for towers is well known whereas the bounds for pancakes is not. -Horndude77 16:50, 30 April 2005 (UTC)

Not to mention that the operation of moving a pancake from one stack to another is quite different from the operation of flipping a pile of pancakes on top. But they use some of the same materials. It's sort of like the similarity between poker and cribbage. Deco 19:14, 30 April 2005 (UTC)

moved from main page

(Note: the discussion here and on the referencing sort algorithm page is misleading, where it suggests O(n) for the overall sort. The 2n-3 bound is only the number of flips. One still needs to figure out where to "insert the spatula", which would involve scanning the stack. So this is probably an O(n^2) or worse algorithm (not even counting the flip cost). I don't have time to fully correct this now.)

What you say is true for a Von Neumann machine as the page suggests. The operation for finding the largest pancake however could be constant time in real life. (I hope it's also obvious that the operation for flipping a stack is constant time in real live.) The best way I can think of it is looking from the top. The operation to find the biggest pancake is constant time. The pancake we need is the outermost one. We don't need to scan every pancake to find it. After we flip that one the next largest is the one that is just inside the biggest one. Again constant time. This can be repeated until the stack is sorted. This gives an overall complexity of O(n). What you are saying is true if this were implemented as a sort algorithm on a computer. This is what the page is saying, so let's leave it for now. -HornDude77 18:45, 2 May 2005 (UTC)

We only claim that the number of flips is linear. Any other operations aren't counted. To my knowledge no machine has ever been constructed that can do prefix reversal in constant time, so issues of practicality are moot. If you built a machine that could do this, you might as well make it able to find the maximum of a consecutive range of numbers in constant time also, which would make the sort linear-time. I'll try to incorporate some of your ideas into the article though. Deco 21:17, 2 May 2005 (UTC)

Anyway, you need O(n²) space to flip the pancakes... —Preceding unsigned comment added by 82.120.141.85 (talk) 11:28, 21 June 2009 (UTC)

About Θ notation

I think, for reordering data in an order is the reason why it is just called sorting, but it is more of a added feature here. This algorithm will solve a certain type of problems. As a reader, i would want to know how "one still needs to figure out where to "insert the spatula"".

The simplest pancake sorting algorithm requires at most 2n−3 flips. In this algorithm, a variation of selection sort, we bring the largest pancake not yet sorted to the top with one flip, and then take it down to its final position with one more, then repeat this for the remaining pancakes.,

[5, 7, 9, 3, 6, 73, 32, 6, 2, 92]
flip(5): [73, 6, 3, 9, 7, 5, 32, 6, 2, 92]
flip(2): [2, 6, 32, 5, 7, 9, 3, 6, 73, 92]
flip(8): [32, 6, 2, 5, 7, 9, 3, 6, 73, 92]
flip(3): [6, 3, 9, 7, 5, 2, 6, 32, 73, 92]
flip(8): [9, 3, 6, 7, 5, 2, 6, 32, 73, 92]
flip(4): [6, 2, 5, 7, 6, 3, 9, 32, 73, 92]
flip(7): [7, 5, 2, 6, 6, 3, 9, 32, 73, 92]
flip(5): [3, 6, 6, 2, 5, 7, 9, 32, 73, 92]
flip(9): [6, 3, 6, 2, 5, 7, 9, 32, 73, 92]
flip(6): [5, 2, 6, 3, 6, 7, 9, 32, 73, 92]
flip(8): [6, 2, 5, 3, 6, 7, 9, 32, 73, 92]
flip(7): [3, 5, 2, 6, 6, 7, 9, 32, 73, 92]
flip(9): [5, 3, 2, 6, 6, 7, 9, 32, 73, 92]
flip(8): [2, 3, 5, 6, 6, 7, 9, 32, 73, 92]
Flip order: 5 2 8 3 8 4 7 5 9 6 8 7 9 8 0

Could use a code example as well. Searched more then an hour for an example and did not found one. Following should be simplest pancake sorting algorithm. Note that this is mainly meant for finding where the flips will be made and not for sorting.

	public ArrayList<Integer> iPANCAKE_SORT(Integer elems[]) {
		int i, j, n = elems.length;
		Integer temp;
		ArrayList<Integer> path = new ArrayList<Integer>();
		Integer Selems[] = elems.clone();

		Arrays.sort(Selems);

		for (i = n - 1; i > -1; i--) {
			// 1.find (j)
			for (j = 0; Selems[i] != elems[j] && j < i; j++);

			if (j == i)// IsInPlace
				continue;

			// 2.flip
			if (j != 0) {// IsNotReadyToSet
				path.add(n - j);
				for (int k = 0; k < 0.5 + (j / 2); k++) {
					temp = elems[k];
					elems[k] = elems[j - k];
					elems[j - k] = temp;
				}
			}

			// 3.set
			path.add(n - i);
			for (int k = 0; k < 0.5 + (i / 2); k++) {
				temp = elems[k];
				elems[k] = elems[i - k];
				elems[i - k] = temp;
			}
		}
		path.add(0);
		return path;
	}

--90.190.170.72 (talk) 01:20, 9 August 2009 (UTC)

The theoretically fastest algorithm

"The theoretically fastest algorithm has been shown to lie between (15/14)n and (5/3)n complexity, but the exact value is not known." I'm a bit bothered by this sentence which in my opinion should be rephrased. Indeed, the aforementioned bounds refer to the maximum number of flips that are needed (the so-called diameter), and not to the actual algorithmic complexity, which can lead to confusion. 87.66.217.170 (talk) 09:46, 26 November 2009 (UTC)

Algorithm Explanation

I am not familiar with the pancake algorithm but there doesn't seem to be any explanation of how the algorithm works. Compare this to the page on selection sort where the algorithm is described in steps —Preceding unsigned comment added by 86.15.187.208 (talk) 19:37, 25 April 2011 (UTC)

NP-completeness results

This section of the article is unclear. NPC is a class of decision problems. What are the decision problems considered? What did Heydari prove? The statement regarding the latter is both vague and unsourced. AmirOnWiki (talk) 17:29, 31 October 2011 (UTC)

Moving memory

The burnt pancake problem sounds to me like an old problem of moving memory partitions around in physical store. Old operating systems used to do this all the time to free up a contiguous block when a process ended. To put partitions 123 in order 312 you'd reverse the 12 giving 213, then reverse the lot to312 then reverse the 3 to give 312. That way no extra memory was used. One could use a bit of free storage to do less moves but at the cost of quite a bit of extra complexity. There was no restriction to just flipping the first few though even though that what I showed here. Any idea what the memory shuffling algorithm was?, it probably should be linked from a see also here. I think what I gave is also used as a toy programming problem to rotate the characters of a string in place. Dmcq (talk) 10:05, 16 March 2012 (UTC)

Sorting by reversals

How about defining sorting by reversals and moving it from the History to the Variations section? — Preceding unsigned comment added by 90.13.13.215 (talk) 14:17, 12 February 2015 (UTC)

Pancake Flipping is hard

The article proving the problem is NP-Hard has appeared on journal.--Zetifree (talk) 17:18, 26 August 2015 (UTC)

The problem on strings

"transforming a compatible string into another" is a generalization of sorting (in which the target string must colocate repeated letters). Do the hardness results apply to sorting? AmirOnWiki (talk) 16:51, 8 November 2015 (UTC)