function bubbleSort(arr) {
for(let i=0, len=arr.length;i < len-1;i++) {
for(let j=0;j < len-i-1;j++) {
if(arr[j] > arr[j+1]) {
arr[j] += arr[j+1];
arr[j+1] = arr[j] - arr[j+1];
arr[j] = arr[j] - arr[j+1];
}
}
}
return arr;
}
console.log("bubbleSort", bubbleSort([5,2,3,9,1,2,7,3]));
function selectionSort(arr) {
for(let i=0, len=arr.length;i < len-1;i++) {
let minVal = arr[i], minIndex = i;
for(let j=i+1;j < len;j++) {
if(arr[j] < minVal) {
minVal = arr[j];
minIndex = j;
}
}
arr[minIndex] = arr[i];
arr[i] = minVal;
}
return arr;
}
console.log("selectionSort", selectionSort([5,2,3,9,1,2,7,3]));
function insertionSort(arr) {
for(let i=1, len=arr.length;i < len;i++) {
for(let j=i;j > 0;j--) {
if(arr[j] < arr[j-1]) {
arr[j] += arr[j-1];
arr[j-1] = arr[j] - arr[j-1];
arr[j] = arr[j] - arr[j-1];
}else {
break;
}
}
}
return arr;
}
console.log("insertionSort", insertionSort([5,2,3,9,1,2,7,3]));
function mergeSort(arr) {
const len = arr.length;
if(len <= 1) {
return arr;
}
const mid = Math.floor(len/2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
arr = [];
let leftIndex = 0, rightIndex = 0;
while(left[leftIndex] !== undefined || right[rightIndex] !== undefined) {
if(right[rightIndex] === undefined || (left[leftIndex] !== undefined && left[leftIndex] <= right[rightIndex])) {
arr.push(left[leftIndex]);
leftIndex++;
}else {
arr.push(right[rightIndex]);
rightIndex++;
}
}
return arr;
}
console.log("mergeSort", mergeSort([5,2,3,9,1,2,7,3]));
function quickSort(arr) {
const len = arr.length;
if(len <= 1) {
return arr;
}
let pivot = len - 1, i = 0;
while(pivot > i) {
if(arr[i] > arr[pivot]) {
if(i === pivot-1) {
arr[pivot] = arr[i]+arr[pivot];
arr[i] = arr[pivot] - arr[i];
arr[pivot] = arr[pivot] - arr[i];
}else {
const temp = arr[pivot-1];
arr[pivot-1] = arr[pivot];
arr[pivot] = arr[i];
arr[i] = temp;
}
pivot--;
}else {
i++;
}
}
const left = quickSort(arr.slice(0, pivot));
const right = quickSort(arr.slice(pivot+1));
return [...left, arr[pivot], ...right];
}
console.log("quickSort", quickSort([5,2,3,9,1,2,7,3]));
function countingSort(arr, min, max) {
const countArrLen = max-min+1;
const countArr = new Array(countArrLen).fill(0);
for(let i=0;i<arr.length;i++){
const index = arr[i]-min;
countArr[index]++;
}
for(let i=1;i<countArrLen;i++) {
countArr[i] += countArr[i-1]
}
countArr.pop();
countArr.unshift(0);
const resultArr = new Array(arr.length);
for(let i=0;i<arr.length;i++) {
const index = countArr[arr[i]-min];
resultArr[index] = arr[i];
countArr[arr[i]-min]++;
}
return resultArr;
}
console.log("countingSort", countingSort([5,2,3,9,1,2,7,3], 0, 9));