Skip to content
This repository was archived by the owner on Dec 3, 2023. It is now read-only.

Commit c716a35

Browse files
sumtypesumtype
committed
Updated Merge Sort and Quick Sort algorithms.
1 parent 66107d6 commit c716a35

File tree

4 files changed

+123
-141
lines changed

4 files changed

+123
-141
lines changed

‎algorithms/es/mergeSort.js

Lines changed: 35 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -4,52 +4,47 @@
44

55
'use strict'
66

7-
let input = null
8-
9-
const mergeSort = (a = null) => {
10-
if (a === null) return null
11-
input = a
12-
return partition(0, input.length - 1)
13-
}
14-
15-
const partition = (low, high) => {
16-
if (low < high) {
17-
let mid = parseInt((low + high) / 2, 10)
18-
partition(low, mid)
19-
partition(mid + 1, high)
20-
return merge(low, mid, high)
21-
}
22-
return input
23-
}
24-
25-
const merge = (low, mid, high) => {
26-
let index = low
27-
let lowIndex = low
28-
let midIndex = mid + 1
29-
let holder = []
30-
while (lowIndex <= mid && midIndex <= high) {
31-
if (input[lowIndex] <= input[midIndex]) {
32-
holder[index] = input[lowIndex]
33-
lowIndex += 1
34-
} else {
35-
holder[index] = input[midIndex]
36-
midIndex += 1
7+
const mergeSort = (input = null) => {
8+
if (input === null) return null
9+
const partition = (low, high) => {
10+
if (low < high) {
11+
let mid = parseInt((low + high) / 2, 10)
12+
partition(low, mid)
13+
partition(mid + 1, high)
14+
return merge(low, mid, high)
3715
}
38-
index += 1
16+
return input
3917
}
40-
if (lowIndex > mid) {
41-
for (let i = midIndex; i <= high; i++) {
42-
holder[index] = input[i]
18+
const merge = (low, mid, high) => {
19+
let index = low
20+
let lowIndex = low
21+
let midIndex = mid + 1
22+
let holder = []
23+
while (lowIndex <= mid && midIndex <= high) {
24+
if (input[lowIndex] <= input[midIndex]) {
25+
holder[index] = input[lowIndex]
26+
lowIndex += 1
27+
} else {
28+
holder[index] = input[midIndex]
29+
midIndex += 1
30+
}
4331
index += 1
4432
}
45-
} else {
46-
for (let i = lowIndex; i <= mid; i++) {
47-
holder[index] = input[i]
48-
index += 1
33+
if (lowIndex > mid) {
34+
for (let i = midIndex; i <= high; i++) {
35+
holder[index] = input[i]
36+
index += 1
37+
}
38+
} else {
39+
for (let i = lowIndex; i <= mid; i++) {
40+
holder[index] = input[i]
41+
index += 1
42+
}
4943
}
44+
for (let i = low; i <= high; i++) input[i] = holder[i]
45+
return input
5046
}
51-
for (let i = low; i <= high; i++) input[i] = holder[i]
52-
return input
47+
return partition(0, input.length - 1)
5348
}
5449

5550
export default mergeSort

‎algorithms/es/quickSort.js

Lines changed: 25 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -4,38 +4,34 @@
44

55
'use strict'
66

7-
let input = null
8-
9-
const quickSort = (a = null) => {
10-
if (a === null) return null
11-
input = a
12-
return sort()
13-
}
14-
15-
const sort = (first, last) => {
16-
if (typeof first === 'undefined') first = 0
17-
if (typeof last === 'undefined') last = input.length - 1
18-
if (first < last) {
19-
let swap = null
20-
let pivot = first
21-
let lowIndex = first
22-
let highIndex = last
23-
while (lowIndex < highIndex) {
24-
while (input[lowIndex] <= input[pivot] && lowIndex < last) lowIndex += 1
25-
while (input[highIndex] > input[pivot]) highIndex -= 1
26-
if (lowIndex < highIndex) {
27-
swap = input[lowIndex]
28-
input[lowIndex] = input[highIndex]
29-
input[highIndex] = swap
7+
const quickSort = (input = null) => {
8+
if (input === null) return null
9+
const sort = (first, last) => {
10+
if (typeof first === 'undefined') first = 0
11+
if (typeof last === 'undefined') last = input.length - 1
12+
if (first < last) {
13+
let swap = null
14+
let pivot = first
15+
let lowIndex = first
16+
let highIndex = last
17+
while (lowIndex < highIndex) {
18+
while (input[lowIndex] <= input[pivot] && lowIndex < last) lowIndex += 1
19+
while (input[highIndex] > input[pivot]) highIndex -= 1
20+
if (lowIndex < highIndex) {
21+
swap = input[lowIndex]
22+
input[lowIndex] = input[highIndex]
23+
input[highIndex] = swap
24+
}
3025
}
26+
swap = input[pivot]
27+
input[pivot] = input[highIndex]
28+
input[highIndex] = swap
29+
sort(first, highIndex - 1)
30+
sort(highIndex + 1, last)
3131
}
32-
swap = input[pivot]
33-
input[pivot] = input[highIndex]
34-
input[highIndex] = swap
35-
sort(first, highIndex - 1)
36-
sort(highIndex + 1, last)
32+
return input
3733
}
38-
return input
34+
return sort()
3935
}
4036

4137
export default quickSort

‎algorithms/es5/mergeSort.js

Lines changed: 36 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -16,55 +16,50 @@
1616
Object.defineProperty(exports, '__esModule', {
1717
value: true
1818
})
19-
var input = null
20-
2119
var mergeSort = function mergeSort () {
22-
var a = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : null
23-
24-
if (a === null) return null
25-
input = a
26-
return partition(0, input.length - 1)
27-
}
20+
var input = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : null
2821

29-
var partition = function partition (low, high) {
30-
if (low < high) {
31-
var mid = parseInt((low + high) / 2, 10)
32-
partition(low, mid)
33-
partition(mid + 1, high)
34-
return merge(low, mid, high)
35-
}
36-
return input
37-
}
38-
39-
var merge = function merge (low, mid, high) {
40-
var index = low
41-
var lowIndex = low
42-
var midIndex = mid + 1
43-
var holder = []
44-
while (lowIndex <= mid && midIndex <= high) {
45-
if (input[lowIndex] <= input[midIndex]) {
46-
holder[index] = input[lowIndex]
47-
lowIndex += 1
48-
} else {
49-
holder[index] = input[midIndex]
50-
midIndex += 1
22+
if (input === null) return null
23+
var partition = function partition (low, high) {
24+
if (low < high) {
25+
var mid = parseInt((low + high) / 2, 10)
26+
partition(low, mid)
27+
partition(mid + 1, high)
28+
return merge(low, mid, high)
5129
}
52-
index += 1
30+
return input
5331
}
54-
if (lowIndex > mid) {
55-
for (var i = midIndex; i <= high; i++) {
56-
holder[index] = input[i]
32+
var merge = function merge (low, mid, high) {
33+
var index = low
34+
var lowIndex = low
35+
var midIndex = mid + 1
36+
var holder = []
37+
while (lowIndex <= mid && midIndex <= high) {
38+
if (input[lowIndex] <= input[midIndex]) {
39+
holder[index] = input[lowIndex]
40+
lowIndex += 1
41+
} else {
42+
holder[index] = input[midIndex]
43+
midIndex += 1
44+
}
5745
index += 1
5846
}
59-
} else {
60-
for (var _i = lowIndex; _i <= mid; _i++) {
61-
holder[index] = input[_i]
62-
index += 1
47+
if (lowIndex > mid) {
48+
for (var i = midIndex; i <= high; i++) {
49+
holder[index] = input[i]
50+
index += 1
51+
}
52+
} else {
53+
for (var _i = lowIndex; _i <= mid; _i++) {
54+
holder[index] = input[_i]
55+
index += 1
56+
}
6357
}
58+
for (var _i2 = low; _i2 <= high; _i2++) {
59+
input[_i2] = holder[_i2]
60+
} return input
6461
}
65-
for (var _i2 = low; _i2 <= high; _i2++) {
66-
input[_i2] = holder[_i2]
67-
} return input
62+
return partition(0, input.length - 1)
6863
}
6964

7065
exports.default = mergeSort

‎algorithms/es5/quickSort.js

Lines changed: 27 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -16,42 +16,38 @@
1616
Object.defineProperty(exports, '__esModule', {
1717
value: true
1818
})
19-
var input = null
20-
2119
var quickSort = function quickSort () {
22-
var a = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : null
20+
var input = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : null
2321

24-
if (a === null) return null
25-
input = a
26-
return sort()
27-
}
28-
29-
var sort = function sort (first, last) {
30-
if (typeof first === 'undefined') first = 0
31-
if (typeof last === 'undefined') last = input.length - 1
32-
if (first < last) {
33-
var swap = null
34-
var pivot = first
35-
var lowIndex = first
36-
var highIndex = last
37-
while (lowIndex < highIndex) {
38-
while (input[lowIndex] <= input[pivot] && lowIndex < last) {
39-
lowIndex += 1
40-
} while (input[highIndex] > input[pivot]) {
41-
highIndex -= 1
42-
} if (lowIndex < highIndex) {
43-
swap = input[lowIndex]
44-
input[lowIndex] = input[highIndex]
45-
input[highIndex] = swap
22+
if (input === null) return null
23+
var sort = function sort (first, last) {
24+
if (typeof first === 'undefined') first = 0
25+
if (typeof last === 'undefined') last = input.length - 1
26+
if (first < last) {
27+
var swap = null
28+
var pivot = first
29+
var lowIndex = first
30+
var highIndex = last
31+
while (lowIndex < highIndex) {
32+
while (input[lowIndex] <= input[pivot] && lowIndex < last) {
33+
lowIndex += 1
34+
} while (input[highIndex] > input[pivot]) {
35+
highIndex -= 1
36+
} if (lowIndex < highIndex) {
37+
swap = input[lowIndex]
38+
input[lowIndex] = input[highIndex]
39+
input[highIndex] = swap
40+
}
4641
}
42+
swap = input[pivot]
43+
input[pivot] = input[highIndex]
44+
input[highIndex] = swap
45+
sort(first, highIndex - 1)
46+
sort(highIndex + 1, last)
4747
}
48-
swap = input[pivot]
49-
input[pivot] = input[highIndex]
50-
input[highIndex] = swap
51-
sort(first, highIndex - 1)
52-
sort(highIndex + 1, last)
48+
return input
5349
}
54-
return input
50+
return sort()
5551
}
5652

5753
exports.default = quickSort

0 commit comments

Comments
 (0)