Skip to content

Commit a019404

Browse files
Lakhan-Nadgithub-actions
Lakhan-Nad
and
github-actions
authored
Added Introsort Implementation in JS. (TheAlgorithms#267)
* Feature: Added IntroSort in JS Closes TheAlgorithms#265 * updating DIRECTORY.md Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
1 parent 4a1be28 commit a019404

File tree

2 files changed

+308
-0
lines changed

2 files changed

+308
-0
lines changed

‎DIRECTORY.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -102,6 +102,7 @@
102102
* [HeapSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/HeapSort.js)
103103
* [HeapSortV2](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/HeapSortV2.js)
104104
* [InsertionSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/InsertionSort.js)
105+
* [IntroSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/IntroSort.js)
105106
* [MergeSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/MergeSort.js)
106107
* [QuickSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/QuickSort.js)
107108
* [RadixSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/RadixSort.js)

‎Sorts/IntroSort.js

Lines changed: 307 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,307 @@
1+
/**
2+
* @function Intosort (As implemented in STD C++ Lib)
3+
* The function performs introsort which is used in
4+
* C++ Standard LIbrary, the implemntation is inspired from]
5+
* library routine itself.
6+
* ALGORITHM:
7+
* 1) It performs quicksort on array until the recursion depth
8+
* exceeds a pre determined limit.
9+
* 2) If the limit is reached it switches to heapsort
10+
* 3) For array size less than a threshold(16) directly
11+
* does insertion sort on array
12+
* @param {Array} array the array to be sorted
13+
* @param {Function} compare the comparison function
14+
*
15+
* @see [Introsort](https://en.wikipedia.org/wiki/Introsort)
16+
* @author [Lakhan Nad](https://github.com/Lakhan-Nad)
17+
*/
18+
function introsort (array, compare) {
19+
/**
20+
* @function Default Comparison Function
21+
* This function is same as implemented by
22+
* Array.sort method
23+
* @see [StackOverflow](https://stackoverflow.com/questions/47334234/how-to-implement-array-prototype-sort-default-compare-function)
24+
* @param {*} a variable 1
25+
* @param {*} b variable 2
26+
* @returns {Number}
27+
* -1 if a is less than b
28+
* 0 if a is equal to b
29+
* 1 if a greater than b
30+
*/
31+
var defaultComparator = function (x, y) {
32+
if (x === undefined && y === undefined) return 0
33+
if (x === undefined) return 1
34+
if (y === undefined) return -1
35+
var xString = toString(x)
36+
var yString = toString(y)
37+
if (xString < yString) return -1
38+
if (xString > yString) return 1
39+
return 0
40+
}
41+
/**
42+
* @function helper function for defaultComparator
43+
* Converts a given object to String
44+
* @throws TypeError()
45+
* @param {Object} obj
46+
* @returns {String} String representation of given object
47+
*/
48+
var toString = function (obj) {
49+
if (obj === null) return 'null'
50+
if (typeof obj === 'boolean' || typeof obj === 'number') {
51+
return obj.toString()
52+
}
53+
if (typeof obj === 'string') return obj
54+
if (typeof obj === 'symbol') throw new TypeError()
55+
return obj.toString()
56+
}
57+
/**
58+
* Checks if the value passed is an array
59+
* or not
60+
*/
61+
if (Array.isArray(array) === false) {
62+
return
63+
}
64+
/**
65+
* If the compare parameter is not a function
66+
* or not passed at all use default comparator
67+
* function
68+
*/
69+
if (typeof compare !== 'function') {
70+
compare = defaultComparator // If compare is not a comparator function
71+
}
72+
/**
73+
* Use a closure to define the whole sort
74+
* implementation this is done through
75+
* [IIFE](https://en.wikipedia.org/wiki/Immediately_invoked_function_expression)
76+
*/
77+
return (function (array, comparator) {
78+
var swap = function (index1, index2) {
79+
var temp = array[index1]
80+
array[index1] = array[index2]
81+
array[index2] = temp
82+
}
83+
/**
84+
* @constant THRESHOLD
85+
* If the length of array is less than
86+
* this then we simply perform insertion sort
87+
*/
88+
var THRESHOLD = 16
89+
/**
90+
* @constant TUNEMAXDEPTH
91+
* Constant usec to increase or decrease value
92+
* of maxDepth
93+
*/
94+
var TUNEMAXDEPTH = 1
95+
var len = array.length
96+
/**
97+
* Return if array is only of length 1
98+
* Array of size 1 is always sorted
99+
*/
100+
if (len === 1) {
101+
return
102+
}
103+
/**
104+
* Calculate maxDepth = log2(len)
105+
* Taken from implementation in stdc++
106+
*/
107+
var maxDepth = Math.floor(Math.log2(len)) * TUNEMAXDEPTH
108+
/**
109+
* The very first call to quicksort
110+
* this initiates sort routine
111+
*/
112+
quickSort(0, len, maxDepth)
113+
/**
114+
* A final checlk call to insertion sort
115+
* on sorted array
116+
*/
117+
insertionSort(0, len)
118+
/** ********************* Implementation of various routines **************************/
119+
/**
120+
* @function
121+
* This is recursive quicksort implementation in array
122+
* of segment [start,last-1]
123+
* [QuickSort](https://en.wikipedia.org/wiki/Quicksort)
124+
* @param {Number} start the start index of array segment to be sorted
125+
* @param {Number} last one more than the last index of array segment
126+
* @param {Number} depth this measures how many recursive calls are done
127+
*/
128+
function quickSort (start, last, depth) {
129+
if (last - start <= THRESHOLD) {
130+
insertionSort(start, last)
131+
return
132+
} else if (depth <= 0) {
133+
heapSort(start, last)
134+
return
135+
}
136+
var pivot = (last + start) >> 1
137+
pivot = partition(start, last, pivot)
138+
quickSort(start, pivot, depth - 1)
139+
quickSort(pivot + 1, last, depth - 1)
140+
}
141+
/**
142+
* @function Helper function to quicksort
143+
* @param {Number} start the start of array segment to partitiion
144+
* @param {Number} last one more than last index of the array segment
145+
* @param {Number} pivot the index of pivot to be used
146+
* @returns {Number} the index of pivot after partition
147+
*/
148+
function partition (start, last, pivot) {
149+
swap(start, pivot)
150+
pivot = start
151+
var lo = start
152+
var hi = last
153+
while (true) {
154+
lo++
155+
while (comparator(array[lo], array[pivot]) <= 0 && lo !== last) {
156+
lo++
157+
}
158+
hi--
159+
while (comparator(array[hi], array[pivot]) > 0 && hi !== start) {
160+
hi--
161+
}
162+
if (lo >= hi) {
163+
break
164+
}
165+
swap(lo, hi)
166+
}
167+
swap(start, hi)
168+
return hi
169+
}
170+
/**
171+
* @function
172+
* Performs insertion sort on array of range
173+
* [start, last-1]
174+
* @param {Number} start the first index of array segment to be sorted
175+
* @param {Number} last one more than last index of array to be sorted
176+
*/
177+
function insertionSort (start, last) {
178+
var i, j
179+
for (i = start + 1; i < last; i++) {
180+
j = i - 1
181+
while (j >= 0 && comparator(array[j], array[j + 1]) > 0) {
182+
swap(j, j + 1)
183+
j--
184+
}
185+
}
186+
}
187+
/**
188+
* @function
189+
* Performs heapsort in array segment of range [start, last-1]
190+
* [HeapSort](https://en.wikipedia.org/wiki/Heapsort)
191+
* @param {Number} start the first index of array segment to be sorted
192+
* @param {Number} last one more than last index of array to be sorted
193+
*/
194+
function heapSort (start, last) {
195+
var x = (last + start) >> 1
196+
while (x - start >= 0) {
197+
heapify(x, start, last)
198+
x--
199+
}
200+
x = last - 1
201+
while (x - start > 0) {
202+
swap(start, x)
203+
heapify(start, start, x)
204+
x--
205+
}
206+
}
207+
/**
208+
* @function Helper function to heapsort routine
209+
* @param {Number} cur the index we need to heapify
210+
* @param {Number} start the start index of array segment that cur belongs to
211+
* @param {Number} last one more than last index of segment that cur belongs to
212+
*/
213+
function heapify (cur, start, last) {
214+
var size = last - start
215+
var max, lt, rt
216+
cur = cur - start
217+
while (true) {
218+
max = cur
219+
lt = 2 * max + 1
220+
rt = 2 * max + 2
221+
if (
222+
lt < size &&
223+
comparator(array[start + max], array[start + lt]) < 0
224+
) {
225+
max = lt
226+
}
227+
if (
228+
rt < size &&
229+
comparator(array[start + max], array[start + rt]) < 0
230+
) {
231+
max = rt
232+
}
233+
if (max !== cur) {
234+
swap(start + cur, start + max)
235+
cur = max
236+
} else {
237+
break
238+
}
239+
}
240+
}
241+
})(array, compare)
242+
}
243+
244+
/**
245+
* @example Demo run of the sort routine
246+
* The data is randomly generated
247+
* Prints RIGHT:) if the sort routine worked as expected
248+
* If not prints WRONG!!
249+
*/
250+
(function demo () {
251+
const data = []
252+
const size = 1000000
253+
var i = 0
254+
var temp
255+
var c = function (a, b) {
256+
return a - b
257+
}
258+
for (i = 0; i < size; i++) {
259+
temp = Math.random() * Number.MAX_SAFE_INTEGER
260+
data.push(temp)
261+
}
262+
introsort(data, c)
263+
var faulty = false
264+
for (i = 1; i < size; i++) {
265+
if (data[i] < data[i - 1]) {
266+
faulty = true
267+
break
268+
}
269+
}
270+
if (faulty) {
271+
console.log('WRONG!!')
272+
} else {
273+
console.log('RIGHT:)')
274+
}
275+
})();
276+
277+
/**
278+
* @example Demo run of the sort routine
279+
* using the default compare function and
280+
* comparing the results with Array.sort
281+
*/
282+
(function demo () {
283+
const data = []
284+
const data2 = []
285+
const size = 1000000
286+
var i = 0
287+
var temp
288+
for (i = 0; i < size; i++) {
289+
temp = Math.random() * Number.MAX_SAFE_INTEGER
290+
data.push(temp)
291+
data2.push(temp)
292+
}
293+
introsort(data)
294+
data2.sort()
295+
var faulty = false
296+
for (i = 1; i < size; i++) {
297+
if (data[i] !== data2[i]) {
298+
faulty = true
299+
break
300+
}
301+
}
302+
if (faulty) {
303+
console.log('WRONG Implented Comparator!!')
304+
} else {
305+
console.log('Comparator Works Fine:)')
306+
}
307+
})()

0 commit comments

Comments
 (0)