Pancake Sort — VisualAlgorithms Docs

How it works

Sorts by repeatedly flipping sub-arrays, like arranging pancakes by size. Only uses a "flip" operation (reversing a prefix of the array).

Implementation

      
 function pancakeSort(arr, stats) {
  const n = arr.length;
  function flip(k) {
    let left = 0, right = k;
    while (left < right) {
      [arr[left], arr[right]] = [arr[right], arr[left]];
      swap(left, right);
      left++;
      right--;
    }
  }
  for (let size = n; size > 1; size--) {
    let maxIdx = 0;
    for (let i = 1; i < size; i++) {
      if (arr[i] > arr[maxIdx]) maxIdx = i;
    }
    if (maxIdx !== size - 1) {
      if (maxIdx > 0) flip(maxIdx);
      flip(size - 1);
    }
    checkpoint(n - size, n - 1);
  }
}
 def pancakeSort(arr, stats):
    def flip(k):
        left = 0
        right = k
        while (left < right):
            arr[left], arr[right] = arr[right], arr[left]
            swap(left, right)
            left += 1
            right -= 1

    for size in range(n, 1, -1):
        maxIdx = 0
        for i in range(1, size):
            if (arr[i] > arr[maxIdx]):
                maxIdx = i
        if (maxIdx != (size - 1)):
            if (maxIdx > 0):
                flip(maxIdx)
            flip((size - 1))
        checkpoint((n - size), (n - 1))
 #include <vector>
#include <algorithm>
void flip(int k);

void flip(int k) {
    int left = 0;
    int right = k;
    while((left < right)) {
        std::swap(arr[left], arr[right]);
        swap(left, right);
        left++;
        right--;
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    for(int size=n; size>1; size--) {
        int maxIdx = 0;
        for(int i=1; i<size; i++) {
            if((arr[i] > arr[maxIdx])) {
                maxIdx = i;
            }
        }
        if((maxIdx != (size - 1))) {
            if((maxIdx > 0)) {
                flip(maxIdx);
            }
            flip((size - 1));
        }
        checkpoint((n - size), (n - 1));
    }
} void flip(int k) {
    int left = 0;
    int right = k;
    while((left < right)) {
        { int _t = arr[left]; arr[left] = arr[right]; arr[right] = _t; }
        swap(left, right);
        left++;
        right--;
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    for(int size=n; size>1; size--) {
        int maxIdx = 0;
        for(int i=1; i<size; i++) {
            if((arr[i] > arr[maxIdx])) {
                maxIdx = i;
            }
        }
        if((maxIdx != (size - 1))) {
            if((maxIdx > 0)) {
                flip(maxIdx);
            }
            flip((size - 1));
        }
        checkpoint((n - size), (n - 1));
    }
} #include <stdio.h>
void flip(int k);

void flip(int k) {
    int left = 0;
    int right = k;
    while((left < right)) {
        { int _t = arr[left]; arr[left] = arr[right]; arr[right] = _t; }
        swap(left, right);
        left++;
        right--;
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    for(int size=n; size>1; size--) {
        int maxIdx = 0;
        for(int i=1; i<size; i++) {
            if((arr[i] > arr[maxIdx])) {
                maxIdx = i;
            }
        }
        if((maxIdx != (size - 1))) {
            if((maxIdx > 0)) {
                flip(maxIdx);
            }
            flip((size - 1));
        }
        checkpoint((n - size), (n - 1));
    }
} 