algoalgo-world
algoalgo-world/sort/pancake-sort
sort/pancake-sort

Pancake Sort

best
O(n^2)
average
O(n^2)
worst
O(n^2)
space
O(1)
stability
unstable
method
comparison

pick a language to open the code

def flip(a, end):
    lo, hi = 0, end
    while lo < hi:
        a[lo], a[hi] = a[hi], a[lo]
        lo += 1
        hi -= 1


def pancake_sort(a):
    for size in range(len(a), 1, -1):
        top = max(range(size), key=lambda i: a[i])
        if top == size - 1:
            continue
        if top > 0:
            flip(a, top)
        flip(a, size - 1)
function flip(a, end) {
  for (let lo = 0, hi = end; lo < hi; lo++, hi--) {
    [a[lo], a[hi]] = [a[hi], a[lo]];
  }
}

function pancakeSort(a) {
  for (let size = a.length; size > 1; size--) {
    let top = 0;
    for (let i = 1; i < size; i++) {
      if (a[i] > a[top]) top = i;
    }
    if (top === size - 1) continue;
    if (top > 0) flip(a, top);
    flip(a, size - 1);
  }
}
static void flip(int a[], int end) {
    for (int lo = 0, hi = end; lo < hi; lo++, hi--) {
        int t = a[lo];
        a[lo] = a[hi];
        a[hi] = t;
    }
}

void pancake_sort(int a[], int n) {
    for (int size = n; size > 1; size--) {
        int top = 0;
        for (int i = 1; i < size; i++) {
            if (a[i] > a[top]) top = i;
        }
        if (top == size - 1) continue;
        if (top > 0) flip(a, top);
        flip(a, size - 1);
    }
}
void pancake_sort(std::vector<int>& a) {
    for (size_t size = a.size(); size > 1; size--) {
        auto top = std::max_element(a.begin(), a.begin() + size);
        if (top == a.begin() + size - 1) continue;
        if (top != a.begin()) std::reverse(a.begin(), top + 1);
        std::reverse(a.begin(), a.begin() + size);
    }
}
static void Flip(int[] a, int end) {
    for (int lo = 0, hi = end; lo < hi; lo++, hi--) {
        (a[lo], a[hi]) = (a[hi], a[lo]);
    }
}

static void PancakeSort(int[] a) {
    for (int size = a.Length; size > 1; size--) {
        int top = 0;
        for (int i = 1; i < size; i++) {
            if (a[i] > a[top]) top = i;
        }
        if (top == size - 1) continue;
        if (top > 0) Flip(a, top);
        Flip(a, size - 1);
    }
}
static void flip(int[] a, int end) {
    for (int lo = 0, hi = end; lo < hi; lo++, hi--) {
        int t = a[lo];
        a[lo] = a[hi];
        a[hi] = t;
    }
}

static void pancakeSort(int[] a) {
    for (int size = a.length; size > 1; size--) {
        int top = 0;
        for (int i = 1; i < size; i++) {
            if (a[i] > a[top]) top = i;
        }
        if (top == size - 1) continue;
        if (top > 0) flip(a, top);
        flip(a, size - 1);
    }
}
watch it run, then read it