forked from SiZapPaaiGwat/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquicksort-middle.js
More file actions
98 lines (89 loc) · 2.76 KB
/
Copy pathquicksort-middle.js
File metadata and controls
98 lines (89 loc) · 2.76 KB
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
(function (exports) {
'use strict';
function compare(a, b) {
return a - b;
}
/**
* Quicksort algorithm
*
* @public
* @param {array} array Array which should be sorted.
* @return {array} Sorted array.
*/
var quickSort = (function () {
/**
* Partitions the array in two parts by the middle elements.
* All elemnts which are less than the chosen one goes left from it
* all which are greater goes right from it.
* Uses Hoare's partitioning algorithm.
*
* @param {array} array Array which should be partitioned
* @param {number} left Left part of the array
* @param {number} right Right part of the array
* @return {number}
*/
function partition(array, left, right, cmp) {
var pivot = array[Math.floor((left + right) / 2)];
var temp;
while (left <= right) {
while (cmp(array[left], pivot) < 0) {
left += 1;
}
while (cmp(array[right], pivot) > 0) {
right -= 1;
}
if (left <= right) {
temp = array[left];
array[left] = array[right];
array[right] = temp;
left += 1;
right -= 1;
}
}
return left;
}
/**
* Recursively calls itself with different values for
* left/right part of the array which should be processed
*
* @private
* @param {array} array Array which should be processed
* @param {number} left Left part of the array which should be processed
* @param {number} right Right part of the array which should be processed
*/
function quicksort(array, left, right, cmp) {
var mid = partition(array, left, right, cmp);
if (left < mid - 1) {
quicksort(array, left, mid - 1, cmp);
}
if (right > mid) {
quicksort(array, mid, right, cmp);
}
}
/**
* Quicksort algorithm. In this version of quicksort used
* middle element of array for the pivot.<br><br>
* Time complexity: O(N log(N)).
*
* @example
*
* var sort = require('path-to-algorithms/src' +
* '/sorting/quicksort-middle').quickSort;
* console.log(sort([2, 5, 1, 0, 4])); // [ 0, 1, 2, 4, 5 ]
*
* @public
* @module sorting/quicksort-middle
* @param {Array} array Input array.
* @param {Function} cmp Optional. A function that defines an
* alternative sort order. The function should return a negative,
* zero, or positive value, depending on the arguments.
* @return {Array} Sorted array.
*/
return function (array, cmp) {
cmp = cmp || compare;
quicksort(array, 0, array.length - 1, cmp);
return array;
};
}());
exports.quickSort = quickSort;
})(typeof window === 'undefined' ? module.exports : window);