GeezerVison is showing github.com — Fix wiggle sort (#991) · Algorithms-Learn/JavaScript@01db0fb
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 +36Lines changed: 36 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +/* | | 2 | + * Wiggle sort sorts the array into a wave like array. | | 3 | + * An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] <= arr[1] >= arr[2] <= arr[3] >= arr[4] <= ….. | | 4 | + * KEEP IN MIND: there are also more strict definitions of wiggle sort which use | | 5 | + * the rule arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < … but this function | | 6 | + * allows for equality of values next to each other. | | 7 | + */ | | 8 | +import { quickSelectSearch } from '../Search/QuickSelectSearch.js' | | 9 | + | | 10 | +export const simplifiedWiggleSort = function (arr) { | | 11 | + // find Median using QuickSelect | | 12 | + let median = quickSelectSearch(arr, Math.floor(arr.length / 2.0)) | | 13 | + median = median[Math.floor(arr.length / 2.0)] | | 14 | + | | 15 | + const sorted = new Array(arr.length) | | 16 | + | | 17 | + let smallerThanMedianIndx = 0 | | 18 | + let greaterThanMedianIndx = arr.length - 1 - (arr.length % 2) | | 19 | + | | 20 | + for (let i = 0; i < arr.length; i++) { | | 21 | + if (arr[i] > median) { | | 22 | + sorted[greaterThanMedianIndx] = arr[i] | | 23 | + greaterThanMedianIndx -= 2 | | 24 | + } else { | | 25 | + if (smallerThanMedianIndx < arr.length) { | | 26 | + sorted[smallerThanMedianIndx] = arr[i] | | 27 | + smallerThanMedianIndx += 2 | | 28 | + } else { | | 29 | + sorted[greaterThanMedianIndx] = arr[i] | | 30 | + greaterThanMedianIndx -= 2 | | 31 | + } | | 32 | + } | | 33 | + } | | 34 | + | | 35 | + return sorted | | 36 | +} |
Collapse file Copy file name to clipboardExpand all lines: Sorts/WiggleSort.js -21Lines changed: 0 additions & 21 deletions 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 { simplifiedWiggleSort } from '../SimplifiedWiggleSort.js' | | 2 | + | | 3 | +describe('simplified wiggle sort', () => { | | 4 | + test('simplified wiggle sort for chars', () => { | | 5 | + const src = ['a', 'b', 'c'] | | 6 | + expect(simplifiedWiggleSort(src)).toEqual(['a', 'c', 'b']) | | 7 | + }) | | 8 | + | | 9 | + test('wiggle sort with duplicates, even array', () => { | | 10 | + const src = [2, 2, 1, 3] | | 11 | + expect(simplifiedWiggleSort(src)).toEqual([1, 3, 2, 2]) | | 12 | + }) | | 13 | + | | 14 | + test('wiggle sort with duplicates, odd array', () => { | | 15 | + const src = [1, 1, 1, 2, 4] | | 16 | + expect(simplifiedWiggleSort(src)).toEqual([1, 4, 1, 2, 1]) | | 17 | + }) | | 18 | + | | 19 | + test('simplified wiggle sort which leads to equal values next to ' + | | 20 | + 'each other', () => { | | 21 | + const src = [3, 3, 5, 1] | | 22 | + expect(simplifiedWiggleSort(src)).toEqual([1, 5, 3, 3]) | | 23 | + }) | | 24 | +}) |
|