VISUALIZED
npm install to install dependencies in the project root directorynpm install to install dependencies in the project root directorynpm install to install dependencies in the project root directorynpm install to install dependencies in the project root directorynpm install to install dependencies in the project root directorynpm install to install dependencies in the project root directoryBubble Sort: (array)
n := length(array)
repeat
swapped = false
for i := 1 to n - 1 inclusive do
/* if this pair is out of order */
if array[i - 1] > array[i] then
/* swap them and remember something changed */
swap(array, i - 1, i)
swapped := true
end if
end for
until not swapped for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end iffunction swap(array, idx1, idx2) {
let temp = array[idx1];
array[idx1] = array[idx2];
array[idx2] = temp;
}
function bubbleSort(array) {
let swapped = true;
while (swapped) {
swapped = false;
for (let i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
swap(array, i, i + 1);
swapped = true;
}
}
}
return array;
}
let array1 = [2, -1, 4, 3, 7, 3];
bubbleSort(array1);
console.log(" bubbleSort(array): ", bubbleSort(array1));
module.exports = { bubbleSort: bubbleSort, swap: swap };procedure selection sort(list)
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedurefunction swap(arr, index1, index2) {
let temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function selectionSort(list) {
let length = list.length;
for (let i = 0; i < length - 1; i++) {
let minPos = i;
for (let j = i + 1; j < length; j++) {
if (list[j] < list[minPos]) {
minPos = j;
}
}
if (minPos !== i) {
swap(list, minPos, i);
}
}
}
module.exports = {
selectionSort,
swap,
};procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedurefunction insertionSort(list) {
for (let i = 1; i < list.length; i++) {
let val = list[i];
let pos = i;
// console.trace("1");
while (pos > 0 && list[pos - 1] > val) {
// console.trace("2");
list[pos] = list[pos - 1];
pos -= 1;
}
list[pos] = val;
}
}
let array = [2, -1, 4, 3, 7, 3];
insertionSort(array);
module.exports = {
insertionSort,
};procedure mergesort( a as array )
if ( n == 1 ) return a
/* Split the array into two */
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( a as array, b as array )
var result as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of result
remove b[0] from b
else
add a[0] to the end of result
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of result
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of result
remove b[0] from b
end while
return result
end procedure// Implement Merge Sort
function merge(array1, array2) {
let merged = [];
while (array1.length || array2.length) {
let el1 = array1.length ? array1[0] : Infinity;
let el2 = array2.length ? array2[0] : Infinity;
el1 < el2 ? merged.push(array1.shift()) : merged.push(array2.shift());
}
return merged;
}
merge([1, 5, 10, 15], [0, 2, 3, 7, 10]);
function mergeSort(array) {
if (array.length <= 1) return array;
let midIdx = Math.floor(array.length / 2);
let left = array.slice(0, midIdx);
let right = array.slice(midIdx);
let sortedLeft = mergeSort(left);
let sortedRight = mergeSort(right);
return merge(sortedLeft, sortedRight);
}
module.exports = {
merge,
mergeSort,
};procedure quick sort (array)
if the length of the array is 0 or 1, return the array
set the pivot to the first element of the array
remove the first element of the array
put all values less than the pivot value into an array called left
put all values greater than the pivot value into an array called right
call quick sort on left and assign the return value to leftSorted
call quick sort on right and assign the return value to rightSorted
return the concatenation of leftSorted, the pivot value, and rightSorted
end procedure quick sort// Implement Quick Sort
function quickSort(array) {
if (array.length <= 1) return array;
let pivot = array.shift();
let left = array.filter((el) => el < pivot);
let right = array.filter((el) => el >= pivot);
let sortedLeft = quickSort(left);
let sortedRight = quickSort(right);
return [...sortedLeft, pivot, ...sortedRight];
}
module.exports = {
quickSort,
};
/*
bryan@LAPTOP-F699FFV1:/mnt/c/Users/15512/Google Drive/a-A-September/weeks/week7-outer/week-7/projects/D2/first-attempt/algorithms-sorting-starter/algorithms-sorting-starter-master/problems$ npm test
> bubble_sort_project_solution@1.0.0 test /mnt/c/Users/15512/Google Drive/a-A-September/weeks/week7-outer/week-7/projects/D2/first-attempt/algorithms-sorting-starter/algorithms-sorting-starter-master
> mocha
bubbleSort(array): [ -1, 2, 3, 3, 4, 7 ]
bubbleSort()
✓ should sort the elements of the array in increasing order, in-place
swap()
✓ should swap the elements at the given indices, mutating the original array
selectionSort()
✓ should sort the elements of the array in increasing order, in-place
insertionSort()
✓ should sort the elements of the array in increasing order, in-place
merge()
✓ should return a single array containing elements of the original sorted arrays, in order
mergeSort()
when the input array contains 0 or 1 elements
✓ should return the array
when the input array contains more than 1 element
✓ should return an array containing the elements in increasing order
quickSort()
when the input array contains 0 or 1 elements
1) should return the array
when the input array contains more than 1 element
2) should return an array containing the elements in increasing order
7 passing (210ms)
2 failing
1) quickSort()
when the input array contains 0 or 1 elements
should return the array:
AssertionError: expected undefined to deeply equal []
at Context.<anonymous> (test/05-quick-sort-spec.js:9:32)
at processImmediate (internal/timers.js:456:21)
2) quickSort()
when the input array contains more than 1 element
should return an array containing the elements in increasing order:
AssertionError: expected undefined to deeply equal [ -1, 2, 3, 3, 4, 7 ]
at Context.<anonymous> (test/05-quick-sort-spec.js:16:49)
at processImmediate (internal/timers.js:456:21)
npm ERR! Test failed. See above for more details.
bryan@LAPTOP-F699FFV1:/mnt/c/Users/15512/Google Drive/a-A-September/weeks/week7-outer/week-7/projects/D2/first-attempt/algorithms-sorting-starter/algorithms-sorting-starter-master/problems$ npm test
> bubble_sort_project_solution@1.0.0 test /mnt/c/Users/15512/Google Drive/a-A-September/weeks/week7-outer/week-7/projects/D2/first-attempt/algorithms-sorting-starter/algorithms-sorting-starter-master
> mocha
bubbleSort(array): [ -1, 2, 3, 3, 4, 7 ]
bubbleSort()
✓ should sort the elements of the array in increasing order, in-place
swap()
✓ should swap the elements at the given indices, mutating the original array
selectionSort()
✓ should sort the elements of the array in increasing order, in-place
insertionSort()
✓ should sort the elements of the array in increasing order, in-place
merge()
✓ should return a single array containing elements of the original sorted arrays, in order
mergeSort()
when the input array contains 0 or 1 elements
✓ should return the array
when the input array contains more than 1 element
✓ should return an array containing the elements in increasing order
quickSort()
when the input array contains 0 or 1 elements
✓ should return the array
when the input array contains more than 1 element
✓ should return an array containing the elements in increasing order
9 passing (149ms)
*/procedure binary search (list, target)
parameter list: a list of sorted value
parameter target: the value to search for
if the list has zero length, then return false
determine the slice point:
if the list has an even number of elements,
the slice point is the number of elements
divided by two
if the list has an odd number of elements,
the slice point is the number of elements
minus one divided by two
create an list of the elements from 0 to the
slice point, not including the slice point,
which is known as the "left half"
create an list of the elements from the
slice point to the end of the list which is
known as the "right half"
if the target is less than the value in the
original array at the slice point, then
return the binary search of the "left half"
and the target
if the target is greater than the value in the
original array at the slice point, then
return the binary search of the "right half"
and the target
if neither of those is true, return true
end procedure binary searchprocedure binary search index(list, target, low, high)
parameter list: a list of sorted value
parameter target: the value to search for
parameter low: the lower index for the search
parameter high: the upper index for the search
if low is equal to high, then return -1 to indicate
that the value was not found
determine the slice point:
if the list has an even number of elements,
the slice point is the number of elements
divided by two
if the list has an odd number of elements,
the slice point is the number of elements
minus one divided by two
if the target is less than the value in the
original array at the slice point, then
return the binary search of the array,
the target, low, and the slice point
if the target is greater than the value in the
original array at the slice point, then return
the binary search of the array, the target,
the slice point plus one, and high
if neither of those is true, return true
end procedure binary search index
