Skip to content

Commit 0224afb

Browse files
trekhlebtrekhleb
committed
Add BubbleSort.
1 parent 8520932 commit 0224afb

File tree

7 files changed

+161
-0
lines changed

7 files changed

+161
-0
lines changed

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,8 @@
3030
* Graph
3131
* [Depth-First Search (DFS)](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search)
3232
* [Breadth-First Search (BFS)](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/breadth-first-search)
33+
* Sorting
34+
* [Bubble Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/bubble-sort)
3335

3436
## Running Tests
3537

‎src/algorithms/sorting/Sort.js‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
import Comparator from '../../utils/comparator/Comparator';
2+
3+
/**
4+
* @typedef {Object} SorterCallbacks
5+
* @property {function(a: *, b: *)} compareCallback - If provided then all elements comparisons
6+
* will be done through this callback.
7+
* @property {function(a: *)} visitingCallback - If provided it will be called each time the sorting
8+
* function is visiting the next element.
9+
*/
10+
11+
export default class Sort {
12+
constructor(rawCallbacks) {
13+
this.callbacks = Sort.initSortingCallbacks(rawCallbacks);
14+
this.comparator = new Comparator(this.callbacks.compareCallback);
15+
}
16+
17+
/**
18+
* @param {SorterCallbacks} rawCallbacks
19+
* @returns {SorterCallbacks}
20+
*/
21+
static initSortingCallbacks(rawCallbacks) {
22+
const callbacks = rawCallbacks || {};
23+
const stubCallback = () => {};
24+
25+
callbacks.compareCallback = callbacks.compareCallback || undefined;
26+
callbacks.visitingCallback = callbacks.visitingCallback || stubCallback;
27+
28+
return callbacks;
29+
}
30+
31+
sort() {
32+
throw new Error('sort method must be implemented');
33+
}
34+
}

‎src/algorithms/sorting/SortTester.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
export const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2+
export const notSortedArray = [10, 5, 30, -1, 0, 0, 1, 2, -3, 2];
3+
export const equalArray = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
4+
5+
export class SortTester {
6+
static testSort(SortingClass) {
7+
const sorter = new SortingClass();
8+
9+
expect(sorter.sort([])).toEqual([]);
10+
expect(sorter.sort([1])).toEqual([1]);
11+
expect(sorter.sort([1, 2])).toEqual([1, 2]);
12+
expect(sorter.sort([2, 1])).toEqual([1, 2]);
13+
expect(sorter.sort([1, 1, 1])).toEqual([1, 1, 1]);
14+
expect(sorter.sort(sortedArray)).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
15+
expect(sorter.sort(notSortedArray)).toEqual([-3, -1, 0, 0, 1, 2, 2, 5, 10, 30]);
16+
expect(sorter.sort(equalArray)).toEqual([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]);
17+
}
18+
19+
static testSortWithCustomComparator(SortingClass) {
20+
const callbacks = {
21+
compareCallback: (a, b) => {
22+
if (a.length === b.length) {
23+
return 0;
24+
}
25+
26+
return a.length < b.length ? -1 : 1;
27+
},
28+
};
29+
30+
const sorter = new SortingClass(callbacks);
31+
32+
expect(sorter.sort([''])).toEqual(['']);
33+
expect(sorter.sort(['a'])).toEqual(['a']);
34+
expect(sorter.sort(['aa', 'a'])).toEqual(['a', 'aa']);
35+
expect(sorter.sort(['bb', 'aa', 'c'])).toEqual(['c', 'bb', 'aa']);
36+
}
37+
}

‎src/algorithms/sorting/__test__/Sort.test.js‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
import Sort from '../Sort';
2+
3+
describe('Sort', () => {
4+
it('should throw an error when trying to call Sort.sort() method directly', () => {
5+
function doForbiddenSort() {
6+
const sorter = new Sort();
7+
sorter.sort();
8+
}
9+
10+
expect(doForbiddenSort).toThrow();
11+
});
12+
});

‎src/algorithms/sorting/bubble-sort/BubbleSort.js‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
import Sort from '../Sort';
2+
3+
export default class BubbleSort extends Sort {
4+
sort(initialArray) {
5+
const array = initialArray;
6+
7+
for (let i = 0; i < array.length; i += 1) {
8+
for (let j = 0; j < array.length - 1; j += 1) {
9+
// Call visiting callback.
10+
this.callbacks.visitingCallback(array[j]);
11+
12+
// Swap elements if they are in wrong order.
13+
if (this.comparator.lessThen(array[j + 1], array[j])) {
14+
const tmp = array[j + 1];
15+
array[j + 1] = array[j];
16+
array[j] = tmp;
17+
}
18+
}
19+
}
20+
21+
return array;
22+
}
23+
}

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

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
# Bubble Sort
2+
3+
Bubble sort, sometimes referred to as sinking sort, is a
4+
simple sorting algorithm that repeatedly steps through
5+
the list to be sorted, compares each pair of adjacent
6+
items and swaps them if they are in the wrong order.
7+
The pass through the list is repeated until no swaps
8+
are needed, which indicates that the list is sorted.

‎src/algorithms/sorting/bubble-sort/__test__/bubbleSort.test.js‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
import BubbleSort from '../BubbleSort';
2+
import { equalArray, notSortedArray, sortedArray, SortTester } from '../../SortTester';
3+
4+
describe('bubbleSort', () => {
5+
it('should sort array', () => {
6+
SortTester.testSort(BubbleSort);
7+
});
8+
9+
it('should sort array with custom comparator', () => {
10+
SortTester.testSortWithCustomComparator(BubbleSort);
11+
});
12+
13+
it('should visit sorted array element specified number of times', () => {
14+
const visitingCallback = jest.fn();
15+
16+
const callbacks = { visitingCallback };
17+
const sorter = new BubbleSort(callbacks);
18+
19+
sorter.sort(sortedArray);
20+
21+
expect(visitingCallback).toHaveBeenCalledTimes(90);
22+
});
23+
24+
it('should visit not-sorted array element specified number of times', () => {
25+
const visitingCallback = jest.fn();
26+
27+
const callbacks = { visitingCallback };
28+
const sorter = new BubbleSort(callbacks);
29+
30+
sorter.sort(notSortedArray);
31+
32+
expect(visitingCallback).toHaveBeenCalledTimes(90);
33+
});
34+
35+
it('should visit equal array element specified number of times', () => {
36+
const visitingCallback = jest.fn();
37+
38+
const callbacks = { visitingCallback };
39+
const sorter = new BubbleSort(callbacks);
40+
41+
sorter.sort(equalArray);
42+
43+
expect(visitingCallback).toHaveBeenCalledTimes(90);
44+
});
45+
});

0 commit comments

Comments
 (0)