Pancake Sort

Here's one I've gotten a few times lately. Took me a while to visualize the sort, but once I did it was a kick in the head. Simple really. If it looks like I hosed something, send me some mail.

Back to Code Samples

public static class PancakeSort
{
//=======================================================================
/// <summary>
/// Sorts the passed in array using the pancake sort algorithm.
/// </summary>
/// <param name="array">The array to sort.</param>
//=======================================================================
public static void SortArray(List<int> array)
{
int arrayLength;

#region Validate arguments
if (array == null)
{
throw new ArgumentException("Invalid array.");
}

arrayLength = array.Count;

if (arrayLength <= 1)
return;

#endregion

int largestValuePosition = arrayLength - 1;
int sortedStackBottom = largestValuePosition;

while (sortedStackBottom > 0)
{
largestValuePosition = findLargestValuePosition(array, sortedStackBottom);
flipStack(array, largestValuePosition);
flipStack(array, sortedStackBottom--);
}
}

//=======================================================================
/// <summary>
/// Gets the position of the largest value in the array up to the maxIndex.
/// </summary>
/// <param name="array">The array to scan.</param>
/// <param name="maxIndex">The maximum location to scan.</param>
/// <returns>The index of the largest value found.</returns>
//=======================================================================
private static int findLargestValuePosition(List<int> array, int maxIndex)
{
#region Validate arguments
if (array == null)
{
throw new ArgumentException("Invalid array.");
}

int arrayLength = array.Count;

if (maxIndex >= arrayLength)
{
throw new ArgumentException("Invalid maxIndex value.", "maxIndex");
}

if (arrayLength <= 1)
return 0;

#endregion

int currentIndex = 0;
int maxValue = int.MinValue;
int maxValueIndex = -1;

do
{
if (array[currentIndex] > maxValue)
{
maxValue = array[currentIndex];
maxValueIndex = currentIndex;
}

} while (currentIndex++ < maxIndex);

return maxValueIndex;
}

//=======================================================================
/// <summary>
/// Flips the stack of pancakes at the given position.
/// </summary>
/// <param name="array">The array of pancakes</param>
/// <param name="lastPosition">The position at which to flip.</param>
//=======================================================================
private static void flipStack(List<int> array, int lastPosition)
{
int arrayMaxIndex;

#region Validate arguments
if (array == null)
{
throw new ArgumentException("Invalid array.");
}

arrayMaxIndex = array.Count - 1;

if (lastPosition > arrayMaxIndex)
{
throw new ArgumentException("Invalid maxIndex value.", "maxIndex");
}

if (arrayMaxIndex <= 0)
return;

#endregion

int temp;
int secondSwapPoint = lastPosition;

for (int firstSwapPoint = 0; firstSwapPoint < secondSwapPoint; firstSwapPoint++)
{
secondSwapPoint = lastPosition - firstSwapPoint;
temp = array[firstSwapPoint];
array[firstSwapPoint] = array[secondSwapPoint];
array[secondSwapPoint] = temp;
}
}
}

Back to Code Samples