Pancake Sort,inspired from sorting a stack of pancake using spatula, is a simple sorting algorithm that only have 1 operation called flip. </br> flip (i) : Reverse array from i to N where N is length of array

Complexity

  • Time: worst
  • Space: worst auxiliary

References

Implementations

  • 1

    # TODO: Implement in Python

  • 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

    console.log(`original array = [${D.join(', ')}]`);

const N = D.length;

function flip(start) {
  
  let idx = 0;
  for (let i = start; i < (start + N) / 2; i++) {
    
    const temp = D[i];
    D[i] = D[N - idx - 1];
    D[N - idx - 1] = temp;
    
    idx++;
  }
  
}

for (let i = 0; i < N - 1; i++) {
  
  console.log(`round ${i + 1}`);
  
  const currArr = D.slice(i, N);
  const currMax = currArr.reduce((prev, curr, idx) => ((curr > prev.val) ? { idx, val: curr } : prev), {
    idx: 0,
    val: currArr[0],
  });
  if (currMax.idx !== 0) { // if currMax.idx === 0 that means max element already at the bottom, no flip required
    
    console.log(`flip at ${currMax.idx + i} (step 1)`);
    
    flip(currMax.idx + i, N);
    
    console.log(`flip at ${i} (step 2)`);
    
    flip(i, N);
  }
}

console.log(`sorted array = [${D.join(', ')}]`);