Algorithms and Data Structures implemented in JavaScript for beginners, following best practices.
|
/*
|
|||
|
|
* Wiggle sort sorts the array into a wave like array.
|
|||
|
|
* An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] <= arr[1] >= arr[2] <= arr[3] >= arr[4] <= …..
|
|||
|
|
* KEEP IN MIND: there are also more strict definitions of wiggle sort which use
|
|||
|
|
* the rule arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < … but this function
|
|||
|
|
* allows for equality of values next to each other.
|
|||
|
|
*/
|
|||
|
|
import { quickSelectSearch } from '../Search/QuickSelectSearch.js'
|
|||
|
|
|
|||
|
|
export const simplifiedWiggleSort = function (arr) {
|
|||
|
|
// find Median using QuickSelect
|
|||
|
|
let median = quickSelectSearch(arr, Math.floor(arr.length / 2.0))
|
|||
|
|
median = median[Math.floor(arr.length / 2.0)]
|
|||
|
|
|
|||
|
|
const sorted = new Array(arr.length)
|
|||
|
|
|
|||
|
|
let smallerThanMedianIndx = 0
|
|||
|
|
let greaterThanMedianIndx = arr.length - 1 - (arr.length % 2)
|
|||
|
|
|
|||
|
|
for (let i = 0; i < arr.length; i++) {
|
|||
|
|
if (arr[i] > median) {
|
|||
|
|
sorted[greaterThanMedianIndx] = arr[i]
|
|||
|
|
greaterThanMedianIndx -= 2
|
|||
|
|
} else {
|
|||
|
|
if (smallerThanMedianIndx < arr.length) {
|
|||
|
|
sorted[smallerThanMedianIndx] = arr[i]
|
|||
|
|
smallerThanMedianIndx += 2
|
|||
|
|
} else {
|
|||
|
|
sorted[greaterThanMedianIndx] = arr[i]
|
|||
|
|
greaterThanMedianIndx -= 2
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return sorted
|
|||
|
|
}
|