Skip to content

Commit c7110be

Browse files
trekhlebtrekhleb
committed
Add quick sort.
1 parent 250d90a commit c7110be

5 files changed

Lines changed: 158 additions & 10 deletions

File tree

‎README.md‎

Lines changed: 11 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -36,7 +36,8 @@
3636
* [Insertion Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/insertion-sort)
3737
* [Heap Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/heap-sort)
3838
* [Merge Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort)
39-
* [Quick Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort)
39+
* [Quicksort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort)
40+
* [Shellsort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/shell-sort)
4041

4142
## Running Tests
4243

@@ -106,11 +107,12 @@ Below is the list of some of the most used Big O notations and their performance
106107

107108
### Array Sorting Algorithms Complexity
108109

109-
| Name | Best | Average | Worst | Memory | Stable |
110-
| --------------------- | :-------: | :-------: | :-------: | :-------: | :-------: |
111-
| **Bubble sort** | n | n^2 | n^2 | 1 | Yes |
112-
| **Insertion sort** | n | n^2 | n^2 | 1 | Yes |
113-
| **Selection sort** | n^2 | n^2 | n^2 | 1 | No |
114-
| **Heap sort** | n log(n) | n log(n) | n log(n) | 1 | No |
115-
| **Merge sort** | n log(n) | n log(n) | n log(n) | n | Yes |
116-
| **Quick sort** | n log(n) | n log(n) | n^2 | log(n) | No |
110+
| Name | Best | Average | Worst | Memory | Stable |
111+
| --------------------- | :-------: | :-------: | :-----------: | :-------: | :-------: |
112+
| **Bubble sort** | n | n^2 | n^2 | 1 | Yes |
113+
| **Insertion sort** | n | n^2 | n^2 | 1 | Yes |
114+
| **Selection sort** | n^2 | n^2 | n^2 | 1 | No |
115+
| **Heap sort** | n log(n) | n log(n) | n log(n) | 1 | No |
116+
| **Merge sort** | n log(n) | n log(n) | n log(n) | n | Yes |
117+
| **Quick sort** | n log(n) | n log(n) | n^2 | log(n) | No |
118+
| **Shell sort** | n log(n) | depends on gap sequence | n (log(n))^2 | 1 | No |

‎src/algorithms/sorting/SortTester.js‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,7 @@ export class SortTester {
3232
expect(sorter.sort([''])).toEqual(['']);
3333
expect(sorter.sort(['a'])).toEqual(['a']);
3434
expect(sorter.sort(['aa', 'a'])).toEqual(['a', 'aa']);
35-
expect(sorter.sort(['aa', 'q', 'a', 'bbbb', 'ccc'])).toEqual(['q', 'a', 'aa', 'ccc', 'bbbb']);
35+
expect(sorter.sort(['aa', 'q', 'bbbb', 'ccc'])).toEqual(['q', 'aa', 'ccc', 'bbbb']);
3636
expect(sorter.sort(['aa', 'aa'])).toEqual(['aa', 'aa']);
3737
}
3838

@@ -49,6 +49,7 @@ export class SortTester {
4949
const sorter = new SortingClass(callbacks);
5050

5151
expect(sorter.sort(['bb', 'aa', 'c'])).toEqual(['c', 'bb', 'aa']);
52+
expect(sorter.sort(['aa', 'q', 'a', 'bbbb', 'ccc'])).toEqual(['q', 'a', 'aa', 'ccc', 'bbbb']);
5253
}
5354

5455
static testAlgorithmTimeComplexity(SortingClass, arrayToBeSorted, numberOfVisits) {

‎src/algorithms/sorting/shell-sort/README.md‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# Shellsort
2+
3+
Shellsort, also known as Shell sort or Shell's method,
4+
is an in-place comparison sort. It can be seen as either a
5+
generalization of sorting by exchange (bubble sort) or sorting
6+
by insertion (insertion sort). The method starts by sorting
7+
pairs of elements far apart from each other, then progressively
8+
reducing the gap between elements to be compared. Starting
9+
with far apart elements, it can move some out-of-place
10+
elements into position faster than a simple nearest neighbor
11+
exchange
12+
13+
![Shellsort](https://upload.wikimedia.org/wikipedia/commons/d/d8/Sorting_shellsort_anim.gif)
14+
15+
## How Shell Sort Works
16+
17+
For our example and ease of understanding, we take the interval
18+
of `4`. Make a virtual sub-list of all values located at the
19+
interval of 4 positions. Here these values are
20+
`{35, 14}`, `{33, 19}`, `{42, 27}` and `{10, 44}`
21+
22+
![Shellsort](https://www.tutorialspoint.com/data_structures_algorithms/images/shell_sort_gap_4.jpg)
23+
24+
We compare values in each sub-list and swap them (if necessary)
25+
in the original array. After this step, the new array should
26+
look like this
27+
28+
![Shellsort](https://www.tutorialspoint.com/data_structures_algorithms/images/shell_sort_step_1.jpg)
29+
30+
Then, we take interval of 2 and this gap generates two sub-lists
31+
- `{14, 27, 35, 42}`, `{19, 10, 33, 44}`
32+
33+
![Shellsort](https://www.tutorialspoint.com/data_structures_algorithms/images/shell_sort_gap_2.jpg)
34+
35+
We compare and swap the values, if required, in the original array.
36+
After this step, the array should look like this
37+
38+
![Shellsort](https://www.tutorialspoint.com/data_structures_algorithms/images/shell_sort_step_2.jpg)
39+
40+
Finally, we sort the rest of the array using interval of value 1.
41+
Shell sort uses insertion sort to sort the array.
42+
43+
![Shellsort](https://www.tutorialspoint.com/data_structures_algorithms/images/shell_sort.jpg)
44+
45+
## References
46+
47+
* [Tutorials Point](https://www.tutorialspoint.com/data_structures_algorithms/shell_sort_algorithm.htm)
48+
* [Wikipedia](https://en.wikipedia.org/wiki/Shellsort)

‎src/algorithms/sorting/shell-sort/ShellSort.js‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
import Sort from '../Sort';
2+
3+
export default class ShellSort extends Sort {
4+
sort(originalArray) {
5+
// Prevent original array from mutations.
6+
const array = originalArray.slice(0);
7+
8+
// Define a gap distance.
9+
let gap = Math.floor(array.length / 2);
10+
11+
// Until gap is bigger then zero do elements comparisons and swaps.
12+
while (gap > 0) {
13+
// Go and compare all distant element pairs.
14+
for (let i = 0; i < (array.length - gap); i += 1) {
15+
let currentIndex = i;
16+
let gapShiftedIndex = i + gap;
17+
18+
while (currentIndex >= 0) {
19+
// Call visiting callback.
20+
this.callbacks.visitingCallback(array[currentIndex]);
21+
22+
// Compare and swap array elements if needed.
23+
if (this.comparator.lessThen(array[gapShiftedIndex], array[currentIndex])) {
24+
const tmp = array[currentIndex];
25+
array[currentIndex] = array[gapShiftedIndex];
26+
array[gapShiftedIndex] = tmp;
27+
}
28+
29+
gapShiftedIndex = currentIndex;
30+
currentIndex -= gap;
31+
}
32+
}
33+
34+
// Shrink the gap.
35+
gap = Math.floor(gap / 2);
36+
}
37+
38+
// Return sorted copy of an original array.
39+
return array;
40+
}
41+
}

‎src/algorithms/sorting/shell-sort/__test__/ShellSort.test.js‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
import ShellSort from '../ShellSort';
2+
import {
3+
equalArr,
4+
notSortedArr,
5+
reverseArr,
6+
sortedArr,
7+
SortTester,
8+
} from '../../SortTester';
9+
10+
// Complexity constants.
11+
const SORTED_ARRAY_VISITING_COUNT = 320;
12+
const NOT_SORTED_ARRAY_VISITING_COUNT = 320;
13+
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 320;
14+
const EQUAL_ARRAY_VISITING_COUNT = 320;
15+
16+
describe('ShellSort', () => {
17+
it('should sort array', () => {
18+
SortTester.testSort(ShellSort);
19+
});
20+
21+
it('should sort array with custom comparator', () => {
22+
SortTester.testSortWithCustomComparator(ShellSort);
23+
});
24+
25+
it('should visit EQUAL array element specified number of times', () => {
26+
SortTester.testAlgorithmTimeComplexity(
27+
ShellSort,
28+
equalArr,
29+
EQUAL_ARRAY_VISITING_COUNT,
30+
);
31+
});
32+
33+
it('should visit SORTED array element specified number of times', () => {
34+
SortTester.testAlgorithmTimeComplexity(
35+
ShellSort,
36+
sortedArr,
37+
SORTED_ARRAY_VISITING_COUNT,
38+
);
39+
});
40+
41+
it('should visit NOT SORTED array element specified number of times', () => {
42+
SortTester.testAlgorithmTimeComplexity(
43+
ShellSort,
44+
notSortedArr,
45+
NOT_SORTED_ARRAY_VISITING_COUNT,
46+
);
47+
});
48+
49+
it('should visit REVERSE SORTED array element specified number of times', () => {
50+
SortTester.testAlgorithmTimeComplexity(
51+
ShellSort,
52+
reverseArr,
53+
REVERSE_SORTED_ARRAY_VISITING_COUNT,
54+
);
55+
});
56+
});

0 commit comments

Comments
 (0)