This content originally appeared on DEV Community and was authored by ShubhamTiwari909
Hello Everyone Today I am going to show you how to write QuickSort Algorithm in Javascript.
QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
Here is The Code Part -
function QuickSort(Arr){
if(Arr.length <= 1){
return Arr;
}
const pivot = Arr[Arr.length - 1];
const leftArr = [];
const rightArr = [];
for(let i=0; i < Arr.length-1;i++){
if(Arr[i] < pivot){
leftArr.push(Arr[i]);
}
else{
rightArr.push(Arr[i])
}
}
return [...QuickSort(leftArr) ,pivot,...QuickSort(rightArr)];
}
const items = [1,5,2,99,81,100,144,121,91,85,74,10];
console.log(QuickSort(items));
- So, First we will check the length of the Array and if it is 1 then we will return the array as it is.
- Then we will select a pivot element which is last element in our case.
- Then we will create two empty arrays leftarr and rightarr to compare elements with pivot and place the element accodingly.
- Then we will iterate the array using for loop and inside for loop we will check each element that it is smaller than pivot or greater than pivot
- If the Element is smaller than pivot, then we will push it into left array and if the element is greater than pivot then we will push the element into right array.
- Then we will recursively call QuickSort for left and right array to partition the arrays until it get sorted completely.
Output -
[1,2,5,10,74,81,85,91,99,100,121,144]
I am New to Data Structures and Algorithm.So, if you find any mistake in this post please correct it in the comment section
THANK YOU
Instagram - https://instagram.com/w_a_a_d_u__h_e_c_k
This content originally appeared on DEV Community and was authored by ShubhamTiwari909
ShubhamTiwari909 | Sciencx (2021-08-28T14:02:14+00:00) QuickSort Algorithm in Javascript. Retrieved from https://www.scien.cx/2021/08/28/quicksort-algorithm-in-javascript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.