Skip to content

Commit d0d208d

Browse files
mgechevmgechev
committed
Refactoring of the directory tree + quicksort with middle element for pivot
1 parent 32a6206 commit d0d208d

12 files changed

Lines changed: 665 additions & 0 deletions

File tree

‎src/sorting/bubblesort/bubblesort.js‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
var array = [3,5,2,4,7,9,6,4,5];
2+
3+
/**
4+
* The bubblesort algorithm. Complexity O(n^2).
5+
*
6+
* @public
7+
* @param {array} array Input array
8+
* @returns {array} array Sorted array
9+
*/
10+
function bubbleSort(array) {
11+
var temp;
12+
for (var i = 0; i < array.length; i += 1) {
13+
for (var j = i; j > 0; j -= 1) {
14+
if (array[j] < array[j - 1]) {
15+
temp = array[j];
16+
array[j] = array[j - 1];
17+
array[j - 1] = temp;
18+
}
19+
}
20+
}
21+
return array;
22+
}
23+
24+
console.log(bubbleSort(array));

‎src/sorting/heapsort/heapsort.js‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
var array = [3,4,6,2,3,6,8,9];
2+
3+
/**
4+
* The heapsort algorithm. It's complexity is O(nlog n).
5+
*
6+
* @public
7+
*/
8+
var heapSort = (function () {
9+
10+
/**
11+
* Finds the correct place of given element in given max heap.
12+
*
13+
* @private
14+
* @param {array} array Array
15+
* @param {number} index Index of the element which palce in the max heap should be found.
16+
*/
17+
function heapify(array, index, heapSize) {
18+
var left = 2 * index + 1,
19+
right = 2 * index + 2,
20+
largest = index;
21+
22+
if (left < heapSize && array[left] > array[index])
23+
largest = left;
24+
25+
if (right < heapSize && array[right] > array[largest])
26+
largest = right;
27+
28+
if (largest !== index) {
29+
var temp = array[index];
30+
array[index] = array[largest];
31+
array[largest] = temp;
32+
heapify(array, largest, heapSize);
33+
}
34+
}
35+
36+
/**
37+
* Builds max heap from given array.
38+
*
39+
* @private
40+
* @param {array} array Array which should be turned into max heap
41+
* @returns {array} array Array turned into max heap
42+
*/
43+
function buildMaxHeap(array) {
44+
for (var i = Math.floor(array.length / 2); i >= 0; i -= 1) {
45+
heapify(array, i, array.length);
46+
}
47+
return array;
48+
}
49+
50+
/**
51+
* Heapsort. Turns the input array into max heap and after that sorts it.
52+
*
53+
* @public
54+
* @param {array} array Input array
55+
* @returns {array} array Sorted array
56+
*/
57+
return function (array) {
58+
var size = array.length,
59+
temp;
60+
buildMaxHeap(array);
61+
for (var i = array.length - 1; i > 0; i -= 1) {
62+
temp = array[0];
63+
array[0] = array[i];
64+
array[i] = temp;
65+
size -= 1;
66+
heapify(array, 0, size);
67+
}
68+
return array;
69+
};
70+
}());
71+
72+
console.log(heapSort(array));

‎src/sorting/insertionsort/insertion-binary-sort.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
var array = [5,6,3,3,6,8,9,4,3];
2+
3+
/**
4+
* Modified version of insertionsort. It uses binary search for finding
5+
* where the current element should be inserted. It's correct because
6+
* the binary search looks just in the first part of the array
7+
* which is actually sorted. It's complexity is O(n^2)
8+
*
9+
* @public
10+
* @param {array} array Input array
11+
* @param {array} array Sorted array
12+
*/
13+
function insertionBinarySort(array) {
14+
var current,
15+
middle,
16+
left,
17+
right;
18+
for (var i = 1; i < array.length; i += 1) {
19+
current = array[i];
20+
left = 0;
21+
right = i;
22+
middle = Math.floor((left + right) / 2);
23+
while (left < right) {
24+
if (array[middle] <= current)
25+
left = middle + 1;
26+
else
27+
right = middle - 1;
28+
middle = Math.floor((left + right) / 2);
29+
}
30+
for (var j = i; j > middle; j -= 1)
31+
array[j] = array[j - 1];
32+
array[j] = current;
33+
}
34+
return array;
35+
}
36+
37+
console.log(insertionBinarySort(array));

‎src/sorting/insertionsort/insertionsort.js‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
var array = [2,3,5,1,2,4,7,9,0,3,3];
2+
3+
/**
4+
* Insertionsort algorithm. It's complexity is O(n^2).
5+
*
6+
* @public
7+
* @param {array} array Input array
8+
* @returns {array} array Sorted array
9+
*/
10+
function insertionSort(array) {
11+
var current,
12+
j;
13+
for (var i = 1; i < array.length; i += 1) {
14+
current = array[i];
15+
j = i - 1;
16+
while (j >= 0 && array[j] > current) {
17+
array[j + 1] = array[j];
18+
j -= 1;
19+
}
20+
array[j + 1] = current;
21+
}
22+
return array;
23+
}
24+
25+
console.log(insertionSort(array));

‎src/sorting/insertionsort/recursive-insertionsort.js‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
var array = [4,6,2,2,4,56,7,7,51,23,5,7];
2+
3+
/**
4+
* Recursive version of insertionsort. Complexity O(n^2).
5+
*
6+
* @public
7+
* @param {array} array Input array
8+
* @param {number} [max] Index of the element which place we should find in the current function call
9+
*/
10+
function recursiveInsertionSort(array, max) {
11+
if (max <= 0)
12+
return array;
13+
if (max === undefined)
14+
max = array.length - 1;
15+
recursiveInsertionSort(array, max - 1);
16+
for (var i = max - 1, current = array[max]; i >= 0 && current < array[i]; i -= 1)
17+
array[i + 1] = array[i];
18+
array[i + 1] = current;
19+
return array;
20+
}
21+
22+
console.log(recursiveInsertionSort(array));

‎src/sorting/linearsort/bucketsort.js‎

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
var array = [0.21, 0.44, 0.221, 0.01, 0.88];
2+
3+
/**
4+
* Bucketsort. This algorithm has complexity O(n) but it's not
5+
* correct for every input.
6+
*
7+
* @public
8+
*/
9+
var bucketSort = (function () {
10+
11+
/**
12+
* Insertionsort.
13+
*
14+
* @private
15+
* @param {array} array Input array
16+
* @returns {array} array Sorted input array
17+
*/
18+
function insertionSort(array) {
19+
var current,
20+
j;
21+
for (var i = 1; i < array.length; i += 1) {
22+
current = array[i];
23+
j = i - 1;
24+
while (j >= 0 && current < array[j]) {
25+
array[j + 1] = array[j];
26+
j -= 1;
27+
}
28+
array[j + 1] = current;
29+
}
30+
return array;
31+
}
32+
33+
/**
34+
* Creates buckets for given array
35+
*
36+
* @private
37+
* @param {array} array Input array
38+
* @returns {array} buckets Array whith array for each bucket.
39+
* Each bucket contains an array with all elements from the input which are with suitable size.
40+
*/
41+
function createBuckets(array) {
42+
var buckets = [],
43+
currentBucket,
44+
current,
45+
sectorSize = 1 / array.length;
46+
for (var i = 0; i < array.length; i += 1) {
47+
current = array[i];
48+
console.log(current / sectorSize);
49+
currentBucket = Math.floor(current / sectorSize);
50+
if (buckets[currentBucket] === undefined) {
51+
buckets[currentBucket] = [];
52+
}
53+
buckets[currentBucket].push(current);
54+
}
55+
return buckets;
56+
}
57+
58+
/**
59+
* Sorts the arrays from each bucket.
60+
*
61+
* @private
62+
* @param {array} buckets Given buckets
63+
* @returns {array} buckets Buckets with sorted arrays for each bucket
64+
*/
65+
function sortBuckets(buckets) {
66+
for (var i = 0; i < buckets.length; i += 1) {
67+
if (buckets[i] !== undefined)
68+
insertionSort(buckets[i]);
69+
}
70+
return buckets;
71+
}
72+
73+
/**
74+
* Unions all buckets' arrays
75+
*
76+
* @private
77+
* @param {array} buckets Input buckets
78+
* @returns {array} result Sorted array which contains all elements form each bucket
79+
*/
80+
function unionBuckets(buckets) {
81+
var result = [],
82+
currentBucket;
83+
for (var i = 0; i < buckets.length; i += 1) {
84+
currentBucket = buckets[i];
85+
if (currentBucket !== undefined) {
86+
for (var j = 0; j < currentBucket.length; j += 1) {
87+
result.push(currentBucket[j]);
88+
}
89+
}
90+
}
91+
return result;
92+
}
93+
94+
/**
95+
* Sorts given array with bucketsort
96+
*
97+
* @public
98+
* @param {array} array Input array which should be sorted
99+
* @returns {array} Sorted array
100+
*/
101+
return function (array) {
102+
var buckets = createBuckets(array);
103+
sortBuckets(buckets);
104+
return unionBuckets(buckets);
105+
};
106+
}());
107+
108+
console.log(bucketSort(array));

‎src/sorting/linearsort/countingsort.js‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
var array = [44,2,34,6,7,34,4,4,2,3,6,8];
2+
3+
/**
4+
* Counting sort algorithm. It's with complexity O(n) but it's
5+
* correct for specific input.
6+
*
7+
* @public
8+
*/
9+
var countingSort = function () {
10+
11+
/**
12+
* Gets the count of the elements into the input array
13+
*
14+
* @private
15+
* @param {array} array The input array
16+
* @returns {array} count The count of each element from the input array
17+
*/
18+
function getCount(array) {
19+
var count = [],
20+
current;
21+
for (var i = 0; i < array.length; i += 1) {
22+
current = array[i];
23+
if (count[current] !== undefined) {
24+
count[current] += 1;
25+
} else {
26+
count[current] = 1;
27+
}
28+
}
29+
return count;
30+
}
31+
32+
/**
33+
* Gets the count of the elements which are less than a given
34+
*
35+
* @private
36+
* @param {array} array The input array
37+
* @returns {array} less The count of the elements which are less than each element from the input
38+
*/
39+
function getLessCount(array) {
40+
var less = [],
41+
last;
42+
less[0] = array[0] || 0;
43+
for (var i = 1; i < array.length; i += 1) {
44+
last = array[i - 1] || 0;
45+
less[i] = last + less[i - 1];
46+
}
47+
return less;
48+
}
49+
50+
/**
51+
* Sorts the input array
52+
*
53+
* @private
54+
* @param {array} array Input which should be sorted
55+
* @param {array} less Count of the less elements for each element
56+
* @returns {array} result The sorted input
57+
*/
58+
function sort(array, less) {
59+
var result = [],
60+
currentPositions = [],
61+
current,
62+
position;
63+
for (var i = 0; i < array.length; i += 1) {
64+
current = array[i];
65+
position = less[current];
66+
if (currentPositions[current] === undefined) {
67+
currentPositions[current] = position;
68+
}
69+
result[currentPositions[current]] = current;
70+
currentPositions[current] += 1;
71+
}
72+
return result;
73+
}
74+
75+
/**
76+
* Sorts a given array
77+
*
78+
* @public
79+
* @param {array} array Array which should be sorted
80+
* @returns {array} array Sorted array
81+
*/
82+
return function (array) {
83+
var less = getLessCount(getCount(array));
84+
return sort(array, less);
85+
};
86+
}();
87+
88+
console.log(countingSort(array));

0 commit comments

Comments
 (0)