Java Tutorials
Top 100 Java Interview Questions and Answers (Download PDF)
Download PDF We have compiled the most frequently asked Java Interview Questions and Answers that...
Quick Sort algorithm follows Divide and Conquer approach. It divides elements into smaller parts based on some condition and performing the sort operations on those divided smaller parts.
Quick Sort algorithm is one of the most used and popular algorithms in any programming language. But, if you are a JavaScript developer, then you might of heard of sort() which is already available in JavaScript. Then, you might have been thinking what the need of this Quick Sort algorithm is. To understand this, first we need what is sorting and what is the default sorting in JavaScript.
Sorting is nothing but, arranging elements in the order we want. You might have come across this in your school or college days. Like arranging numbers from smaller to greater (ascending) or from greater to smaller (descending) is what we saw till now and is called sorting.
As mentioned earlier, JavaScript has sort(). Let us take an example with few array of elements like [5,3,7,6,2,9] and want to sort this array elements in ascending order. Just call sort() on items array and it sorts array elements in ascending order.
Code:
var items = [5,3,7,6,2,9]; console.log(items.sort()); //prints [2, 3, 5, 6, 7, 9]
What is the reason to choose Quick sort over default sort() in JavaScript
Though sort() gives the result we want, problem lies with the way it sorts the array elements. Default sort() in JavaScript uses insertion sort by V8 Engine of Chrome and Merge sort by Mozilla Firefox and Safari.
But, other this is not suitable if you need to sort large number of elements. So, the solution is to use Quick sort for large dataset.
So, to understand completely, you need to know how Quick sort works and let us see that in detail now.
Quick sort follows Divide and Conquer algorithm. It is dividing elements in to smaller parts based on some condition and performing the sort operations on those divided smaller parts. Hence, it works well for large datasets. So, here are the steps how Quick sort works in simple words.
So, that is the basic outline of Quick sort. Here are the steps which need to be followed one by one to perform Quick sort.
So, let us see these steps with an example. Let us consider array of elements which we need to sort is [5,3,7,6,2,9].
But before going forward with the Quick sort, selecting the pivot element plays a major role. If you select the first element as the pivot element, then it gives worst performance in the sorted array. So, it is always advisable to pick the middle element (length of the array divided by 2) as the pivot element and we do the same.
Here are the steps to perform Quick sort that is being shown with an example [5,3,7,6,2,9].
STEP 1: Determine pivot as middle element. So, 7 is the pivot element.
STEP 2: Start left and right pointers as first and last elements of the array respectively. So, left pointer is pointing to 5 at index 0 and right pointer is pointing to 9 at index 5.
STEP 3: Compare element at the left pointer with the pivot element. Since, 5 < 6 shift left pointer to the right to index 1.
STEP 4: Now, still 3 <6 so shift left pointer to one more index to the right. So now 7 > 6 stop incrementing the left pointer and now left pointer is at index 2.
STEP 5: Now, compare value at the right pointer with the pivot element. Since 9 > 6 move the right pointer to the left. Now as 2 < 6 stop moving the right pointer.
STEP 6: Swap both values present at left and right pointers with each other.
STEP 7: Move both pointers one more step.
STEP 8: Since 6 = 6, move pointers to one more step and stop as left pointer crosses the right pointer and return the index of the left pointer.
So, here based on the above approach, we need to write code for swapping elements and partitioning the array as mentioned in above steps.
function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; }
function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //swap two elements i++; j--; } } return i; }
Once you perform above steps, index of the left pointer will be returned and we need to use that to divide the array and perform the Quick sort on that part. Hence, it is called Divide and Conquer algorithm.
So, Quick sort is performed until all elements on the left array and right array are sorted.
Note: Quick sort is performed on the same array and no new arrays are created in the process.
So, we need to call this partition() explained above and based on that we divide the array in to parts. So here is the code where you use it,
function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var result = quickSort(items, 0, items.length - 1);
var items = [5,3,7,6,2,9]; function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; } function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //sawpping two elements i++; j--; } } return i; } function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var sortedArray = quickSort(items, 0, items.length - 1); console.log(sortedArray); //prints [2,3,5,6,7,9]
NOTE: Quick sort runs with the Time Complexity of O(nlogn).
Download PDF We have compiled the most frequently asked Java Interview Questions and Answers that...
What is Bubble Sort? Bubble sort is a simple algorithm which compares the first element of the...
What is Polymorphism in Java? Polymorphism in Java occurs when there are one or more classes or...
JavaScript is an open-source and most popular client-side scripting language supported by all...
In this tutorial, we will learn- How to use Loop? Different Types of Loops for loop while loop...
What is OOPS Concept in JavaScript? Many times, variables or arrays are not sufficient to simulate...