GeezerVison is showing github.com — Add Pancake Sort to the sorting algorithms · Algorithms-Learn/JavaScript@9ed5d8c
File treeExpand file treeCollapse file tree Open diff view settings Expand file treeCollapse file tree Open diff view settings Collapse file Copy file name to clipboard +81Lines changed: 81 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +/* | | 2 | + * Unlike a traditional sorting algorithm, which attempts to sort with the fewest | | 3 | + * comparisons possible, the goal of pancake sort is to sort the sequence in as few reversals as | | 4 | + * possible. The idea is to do something similar to Selection Sort. We one by one place | | 5 | + * maximum element at the end and reduce the size of current array by one. | | 6 | + * | | 7 | + * Source: https://www.geeksforgeeks.org/pancake-sorting/ | | 8 | + * | | 9 | + * This sorting algorithm is inspired by the pancake problem (hence the name), | | 10 | + * where a spatula can be placed anywhere between two pancakes and flip all pancakes | | 11 | + * above. | | 12 | + * | | 13 | + * The interesting about this algorithm (besides its name) is that instead of comparisons, | | 14 | + * the algorithm relies on flipping an array. | | 15 | + * | | 16 | + * Source: https://en.wikipedia.org/wiki/Pancake_sorting#The_original_pancake_problem | | 17 | + * | | 18 | + */ | | 19 | + | | 20 | +/** | | 21 | + * Unlike Array.prototype.reverse, flipArray reverses only a subarray of the given | | 22 | + * array, determined by the parameters startIndex and endIndex | | 23 | + * | | 24 | + * @param {number[]} array The array to flip | | 25 | + * @param {number} startIndex The start of the subarray | | 26 | + * @param {number} endIndex The end of the subarray | | 27 | + * @returns The flipped array | | 28 | + */ | | 29 | +export function flipArray(array, startIndex, endIndex) { | | 30 | + while (startIndex < endIndex) { | | 31 | + // swap front and back of the subarray | | 32 | + const temp = array[startIndex] | | 33 | + array[startIndex] = array[endIndex] | | 34 | + array[endIndex] = temp | | 35 | + | | 36 | + // essentialy reducing the problem to a smaller subarray | | 37 | + startIndex++ | | 38 | + endIndex-- | | 39 | + } | | 40 | + | | 41 | + return array | | 42 | +} | | 43 | + | | 44 | +/** | | 45 | + * Returns the index of the maximum number of a subarray in a given array | | 46 | + * | | 47 | + * @param {number[]} array The array to found the maximum number's index | | 48 | + * @param {*} startIndex The start of the subarray | | 49 | + * @param {*} endIndex The end of the subarray | | 50 | + * @returns The index of the maximum number | | 51 | + */ | | 52 | +export function findMax(array, startIndex, endIndex) { | | 53 | + let maxIndex = 0 | | 54 | + for (let i = startIndex; i <= endIndex; i++) { | | 55 | + if (array[i] > array[maxIndex]) maxIndex = i | | 56 | + } | | 57 | + | | 58 | + return maxIndex | | 59 | +} | | 60 | + | | 61 | +/** | | 62 | + * The Pancake Sort algorithm. | | 63 | + * | | 64 | + * Note that even though it's a completely different concept of sorting an | | 65 | + * array, it's rather simple! | | 66 | + * | | 67 | + * @param {number[]} array The array to sort | | 68 | + * @returns The sorted array | | 69 | + */ | | 70 | +export function pancakeSort(array) { | | 71 | + for (let subarraySize = array.length; subarraySize > 1; subarraySize--) { | | 72 | + const maximumIndex = findMax(array, 0, subarraySize - 1) | | 73 | + | | 74 | + if (maximumIndex !== subarraySize - 1) { | | 75 | + flipArray(array, 0, maximumIndex) | | 76 | + flipArray(array, 0, subarraySize - 1) | | 77 | + } | | 78 | + } | | 79 | + | | 80 | + return array | | 81 | +} |
Collapse file Copy file name to clipboard +24Lines changed: 24 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +import { flipArray, findMax, pancakeSort } from '../PancakeSort' | | 2 | + | | 3 | +describe('flipArray', () => { | | 4 | + it('should flip any subarray of any array', () => { | | 5 | + expect(flipArray([1, 2, 3, 4], 0, 3)).toEqual([4, 3, 2, 1]) | | 6 | + expect(flipArray([1, 2, 3, 4, 5], 2, 4)).toEqual([1, 2, 5, 4, 3]) | | 7 | + expect(flipArray([], 0, 0)).toEqual([]) | | 8 | + }) | | 9 | +}) | | 10 | + | | 11 | +describe('findMax', () => { | | 12 | + it('should find the index of the maximum value in any subarray of any array', () => { | | 13 | + expect(findMax([1, 3, 2, 5], 0, 3)).toEqual(3) | | 14 | + expect(findMax([1, 3, 2, 5], 0, 2)).toEqual(1) | | 15 | + }) | | 16 | +}) | | 17 | + | | 18 | +describe('pancakeSort', () => { | | 19 | + it('should sort any array', () => { | | 20 | + expect(pancakeSort([4, 3, 2, 1])).toEqual([1, 2, 3, 4]) | | 21 | + expect(pancakeSort([3, 1, 4, 2])).toEqual([1, 2, 3, 4]) | | 22 | + expect(pancakeSort([100, 1000, 10, 1])).toEqual([1, 10, 100, 1000]) | | 23 | + }) | | 24 | +}) |
|