Skip to content

Commit b3ba466

Browse files
VitaminvpVitaminvp
committed
Add Shell Sort & Counting Sort
1 parent 0ae0fa2 commit b3ba466

14 files changed

+249
-70
lines changed

‎README.md‎

Lines changed: 38 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,9 @@ Sorting Algorithms in JavaScript
55
+ [Selection Sort](#selectionSort)
66
+ [Insertion Sort](#insertionSort)
77
+ [Merge Sort](#mergeSort)
8+
+ [Quick Sort](#quickSort)
9+
+ [Shell Sort](#shellSort)
10+
+ [Counting Sort](#сountingSort)
811

912

1013
## Bubble sort
@@ -64,6 +67,40 @@ Sorting Algorithms in JavaScript
6467
По сути, это означает, что вместо работы с массивом в целом он непрерывно разбивает его на две части,
6568
пока обе половины не отсортированы, а затем половины объединяются в один решенный список.
6669

67-
> Сложность алгоритма: O(n<sup>2</sup>).
70+
> Сложность алгоритма: O(n log n).
6871
6972
![Merge Sort](./public/merge-sort-animation2.gif "Merge sort animation")
73+
74+
## Quick Sort
75+
76+
<a name="quickSort"></a>
77+
78+
> Сложность алгоритма: O(n<sup>2</sup>).
79+
80+
![Quick Sort](./public/quick-sort-animation.gif "Quick sort animation")
81+
82+
## Shell Sort
83+
84+
<a name="shellSort"></a>Shell Sort «сортировкой по убыванию», улучшает Insertion Sort,
85+
разбивая исходный массив на несколько меньших подмассивов, каждый из которых сортируется с использованием Insertion Sort.
86+
Способ выбора этих подмассивов - уникальность Shell Sort. Вместо того, чтобы разбивать массив на подмассивы смежных элементов,
87+
сортировка оболочки использует интервал *d*, иногда называемый интервал *gap*, для создания подмассива, выбирая все элементы,
88+
которые являются d-ми элементами, отдельно.
89+
90+
+ Самый простой пример *d = n / 2*, *d<sub>2</sub> = d / 2 … d<sub>n</sub> = 1*. ***O(n<sup>2</sup>)***
91+
+ Предложение Хиббарда: проверить на всем n<sup>i — 1</sup> <= n. ***O(n<sup>3/2</sup>)***
92+
+ Числа Седжвика ...
93+
94+
> Сложность алгоритма: O(n<sup>2</sup>) или O(n<sup>3/2</sup>).
95+
96+
![Shell Sort](./public/shell-sort.gif "Shell sort animation")
97+
[![Shell Sort](https://img.youtube.com/vi/lvts84Qfo8o/0.jpg)](https://www.youtube.com/watch?v=lvts84Qfo8o)
98+
99+
## Counting Sort
100+
101+
Вначале для каждого элемента массива подсчитывается количество элементов, меньших, чем он, и на основе этой
102+
информации текущий элемент помещается в соответствующее место отсортированного массива.
103+
104+
> Сложность алгоритма: O(n<sup>2</sup>).
105+
106+
![Counting Sort](./public/counting-sort-animation.gif "Counting sort animation")

‎algorithms/bubbleSort.js‎

Lines changed: 29 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,34 @@
1-
const bubbleSort = arr => {
2-
const len = arr.length;
3-
for (let i = len - 1; i >= 0; i--) {
4-
for (let j = 1; j <= i; j++) {
5-
if (arr[j - 1] > arr[j]) {
6-
const temp = arr[j - 1];
7-
arr[j - 1] = arr[j];
8-
arr[j] = temp;
1+
// const bubbleSort = arr => {
2+
// const result = [...arr];
3+
// const length = result.length;
4+
// for (let i = 0; i < length - 1; i++) {
5+
// for (let j = 0; j < length - 1 - i; j++) {
6+
// if (result[j + 1] < result[j]) {
7+
// const temp = result[j + 1];
8+
// result[j + 1] = result[j];
9+
// result[j] = temp;
10+
// }
11+
// }
12+
// }
13+
// return result;
14+
// };
15+
16+
let bubbleSort = arr => {
17+
const result = [...arr];
18+
const length = result.length;
19+
let swapped;
20+
do {
21+
swapped = false;
22+
for (let i = 0; i < length; i++) {
23+
if (result[i] > result[i + 1]) {
24+
let temp = result[i];
25+
result[i] = result[i + 1];
26+
result[i + 1] = temp;
27+
swapped = true;
928
}
1029
}
11-
}
12-
return arr;
30+
} while (swapped);
31+
return result;
1332
};
1433

1534
module.exports = bubbleSort;

‎algorithms/countingSort.js‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
const countingSort = arr => {
2+
const array = [...arr];
3+
const length = array.length;
4+
const count = [];
5+
const result = [];
6+
for (let i = 0; i < length; i++) count[i] = 0;
7+
for (let i = 0; i < length - 1; i++) {
8+
for (let j = i + 1; j < length; j++) {
9+
if (array[i] < array[j]) count[j]++;
10+
else count[i]++;
11+
}
12+
}
13+
for (let i = 0; i < length; i++) result[count[i]] = array[i];
14+
return result;
15+
};
16+
17+
module.exports = countingSort;

‎algorithms/insertionSort.js‎

Lines changed: 9 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,16 @@
11
const insertionSort = arr => {
2-
const n = arr.length;
3-
for (let i = 0; i < n; i++) {
4-
let v = arr[i],
5-
j = i - 1;
6-
while (j >= 0 && arr[j] > v) {
7-
arr[j + 1] = arr[j];
2+
const result = [...arr];
3+
const length = result.length;
4+
for (let i = 1; i < length; i++) {
5+
let temp = result[i];
6+
let j = i - 1;
7+
while (j >= 0 && result[j] > temp) {
8+
result[j + 1] = result[j];
89
j--;
910
}
10-
arr[j + 1] = v;
11+
result[j + 1] = temp;
1112
}
12-
return arr;
13+
return result;
1314
};
1415

1516
module.exports = insertionSort;

‎algorithms/selectionSort.js‎

Lines changed: 13 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,18 @@
11
const selectionSort = arr => {
2-
let minIdx,
3-
temp,
4-
len = arr.length;
5-
for (let i = 0; i < len; i++) {
6-
minIdx = i;
7-
for (let j = i + 1; j < len; j++) {
8-
if (arr[j] < arr[minIdx]) {
9-
minIdx = j;
10-
}
2+
const result = [...arr];
3+
const length = arr.length;
4+
for (let i = 0; i < length - 1; i++) {
5+
let min = i;
6+
for (let j = i + 1; j < length; j++) {
7+
if (result[j] < result[min]) min = j;
8+
}
9+
if (min !== i) {
10+
let temp = result[min];
11+
result[min] = result[i];
12+
result[i] = temp;
1113
}
12-
temp = arr[i];
13-
arr[i] = arr[minIdx];
14-
arr[minIdx] = temp;
1514
}
16-
return arr;
15+
return result;
1716
};
1817

19-
20-
module.exports = selectionSort;
18+
module.exports = selectionSort;

‎algorithms/shellSort.js‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
const shellSort = arr => {
2+
const result = [...arr];
3+
const length = arr.length;
4+
let i = Math.floor(length / 2);
5+
while (i > 0) {
6+
for (let j = 0; j < length; j++) {
7+
let k = j,
8+
t = result[j];
9+
while (k >= i && result[k - i] > t) {
10+
result[k] = result[k - i];
11+
k -= i;
12+
}
13+
result[k] = t;
14+
}
15+
i = i == 2 ? 1 : Math.floor((i * 5) / 11);
16+
}
17+
return result;
18+
};
19+
20+
module.exports = shellSort;

‎helpers/consts.js‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
const positiveCases = [
2+
[[7, 5, 2, 4, 3, 9], [2, 3, 4, 5, 7, 9]],
3+
[[9, 7, 5, 4, 3, 1], [1, 3, 4, 5, 7, 9]],
4+
[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]],
5+
[
6+
[4, 50, 28, 47, 9, 2097, 30, 41, 11, 3, 68],
7+
[3, 4, 9, 11, 28, 30, 41, 47, 50, 68, 2097]
8+
],
9+
[
10+
[
11+
2,
12+
6,
13+
5,
14+
12,
15+
-1,
16+
3,
17+
8,
18+
7,
19+
1,
20+
-4,
21+
0,
22+
23,
23+
1,
24+
-55,
25+
20,
26+
37,
27+
54,
28+
210,
29+
-23,
30+
7,
31+
483,
32+
9339,
33+
29,
34+
-3,
35+
90,
36+
-2,
37+
81,
38+
54,
39+
7372,
40+
-92,
41+
93,
42+
93,
43+
18,
44+
-43,
45+
21
46+
],
47+
[
48+
-92,
49+
-55,
50+
-43,
51+
-23,
52+
-4,
53+
-3,
54+
-2,
55+
-1,
56+
0,
57+
1,
58+
1,
59+
2,
60+
3,
61+
5,
62+
6,
63+
7,
64+
7,
65+
8,
66+
12,
67+
18,
68+
20,
69+
21,
70+
23,
71+
29,
72+
37,
73+
54,
74+
54,
75+
81,
76+
90,
77+
93,
78+
93,
79+
210,
80+
483,
81+
7372,
82+
9339
83+
]
84+
],
85+
[[], []]
86+
];
87+
88+
const negativeCases = [
89+
[5, undefined],
90+
["John", undefined],
91+
[{ a: 5, b: 6 }, undefined]
92+
];
93+
94+
module.exports = { positiveCases, negativeCases };

public/counting-sort-animation2.gif renamed to public/counting-sort-animation.gif

File renamed without changes.

‎public/shell-sort.gif‎

61.9 KB
Loading

‎test/bubleSort.test.js‎

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,9 @@
11
/* eslint-env jest */
22

33
const bubbleSort = require("../algorithms/bubbleSort");
4+
const { positiveCases } = require("../helpers/consts");
5+
46

5-
const positiveCases = [
6-
[[7, 5, 2, 4, 3, 9], [2, 3, 4, 5, 7, 9]],
7-
[[9, 7, 5, 4, 3, 1], [1, 3, 4, 5, 7, 9]],
8-
[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]],
9-
[[], []]
10-
];
117

128
const negativeCases = [
139
[5, undefined],

0 commit comments

Comments
 (0)