DEV Community

raquelhn
raquelhn

Posted on

Understanding Sorting Algorithms - Javascript

QUICKSORT
The first step is to find a pivot, and once this is picked, the array is divided in 2 sub arrays, one of them with the values less than the pivot value and the other other with values more than the pivot value, and this would be sorted by using the quicksort algorithm recursively
It has a complexity of O(n log(n)) so it's more efficient than the others

function quickSort(arr){
//its important to have a base case when it's a recursion
if(arr<=1){
return arr
}
let pivot = arr[arr.length-1]
left=[]
right=[]
for(let i=0;i<arr.length-1;i++){
if(arr[i]<pivot){
left.push(arr[i])
}else{
right.push(arr[i])
}
}

return [...quickSort(left),pivot,...quickSort(right)]
}

SELECTION SORT
Selects the minimum value in the list and swaps it with the first element of the list, it continues to do this until the list is sorted.
The idea to implement this algorithm is to sort through the whole list, and in an inner loop sort to find the index of the min number, so once we have this we can swap this number with the first one of that inner loop.

It's important to mention that this is not the most efficient algorithm, since it has an O complexity of O(n^2)

function sortSel(arr){
for(let i=0;i<arr.length-1;i++){
let minIndex=i
for(let j=i+1;j<arr.length;j++){
//if the min num changes then the index updates
if(arr[j]<arr[minIndex]){
minIndex=j
}
}

temp=arr[i]
arr[i]=arr[minIndex]
arr[minIndex]=arr[i]
}

return arr

}

Discussion (0)