Inserting and Sorting stuff(Quick Sort)

QuickSort (Almost like merge sort but worse).

Unlike merge sort it is somewhat weird but trust me the javascript implementation is quite easy to grasp unlike C or JAVA.It is a divide and conquer algorithm with time complexity O(nlogn) in best case and O(n^2) in worst case scenario.

So  let’s get into it .

Quick review(Pun intended):
Main thing to grasp is that you take a random element , call it pivot and put it in it’s place .No exactly you put the element where it will remain for the rest of implementation.So you do that by moving all the element less than  the pivot element  to left and all the element greater than pivot element right of it.Now make two new arrays called left and right give them the values that are present in the left and right of the original array respectively .Now the run the sort function on them until the length of either array is 0.

After that concatenate left right array along with the pivot element in each recursion of the algo.

Algo:
Step 1 :If length of input array is  0 return the array.
STEP 2 :take the first element as pivot element
STEP 3 : Push all the element less than the pivot element to a left array 
and all the element greater than pivot element to a right array
STEP 4 :go to step 1 by taking  an array( that is concatenation of first 
left then pivot element and then right array).as input.

Implementation in JS.

 


    function qsort(arr){
    if(arr.length==0)return [];
    var pivot=arr[0];
    var left=[],right=[];
    for(var j=1;j<arr.length;j++){

        if(arr[j]<pivot)
        left.push(arr[j]);
        else
        right.push(arr[j]);
    }
    return qsort(left).concat(pivot,qsort(right));
}
var c=[2,3,4,5,6,7,8,3,4,43,6,6,7,8,9,5,3,5,7,89,4];
console.log(qsort(c));

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s