Horje
JavaScript Program for Quick Sort

What is Quick Sort Algorithm?

Quick sort is one of the sorting algorithms that works on the idea of divide and conquer. It takes an element as a pivot and partitions the given array around that pivot by placing it in the correct position in the sorted array. The pivot element can be selected in the following ways:

  • Select the First element as a pivot
  • Select the Last element as a pivot
  • Select the Middle element as a pivot
  • Select a Random element as a pivot

We will use the Last element as a pivot for this article.

Working of Quick Sort Algorithm

QuickSort works on divide and conquer. It takes one element as a pivot and moves it to the correct position in a way that all elements at left are smaller and all elements at right are greater than the pivot and hence partitions the array at the pivot and again applies the same for the created partition subarray as shown below…

How Quicksort works

Partition Steps in Quick Sort

The steps in the partition function are as follows:

Step 1: First, assign the last value as a pivot and start comparing it with the elements while iterations. Here, compare 10 with 40 as the element is smaller so swap it with first available position. As 10 itself is at the correct possition there will be no change.

Partition in QuickSort: Compare pivot with 10

Step 2: Here compare 2nd value with the pivot as the value 80 is greater so there will be no swapping.

Partition in QuickSort: Compare pivot with 80

Step 3: Now, compare the third element i.e. 30 with pivot value 40. as it is smallar so swap 30 with the next available position i.e. 2 nd. Hence, swap 80 and 30.

Partition in QuickSort: Compare pivot with 30

Step 4: For position 4 the value 90 is larger. Hence, there will be no swap.

Partition in QuickSort: Compare pivot with 90

Step 5: In the last step swap the pivot element woth the next position available for swapping which is position 3 with value 80. So swap pivot with 80 as shown.

Partition in QuickSort: Place pivot in its correct position

Programmatic Approach for Quick Sort

  • First, create a recursive function that takes array, low value and high value as input and calls the partition fucntion for recursive call for partitioned arrays.
  • Define a partition function for last element as pivot and give the partition index of array.
  • Partition function iterate the given array and compare elements to pivot. If smallar then swap them to a sequential postion else no swap is performed.
  • At the end for iteration the pivot element is swapped to its correct position stored in i for the exact place.
  • Now return the latest position of the pivot element

Example: Here is the complete code for the Quick Sort algorithm using JavaScript.

Javascript

function partition(arr, low, high) {
    let pivot = arr[high];
    let i = low - 1;
  
    for (let j = low; j <= high - 1; j++) {
        // If current element is smaller than the pivot
        if (arr[j] < pivot) {
            // Increment index of smaller element
            i++;
            // Swap elements
            [arr[i], arr[j]] = [arr[j], arr[i]]; 
        }
    }
    // Swap pivot to its correct position
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; 
    return i + 1; // Return the partition index
}
  
function quickSort(arr, low, high) {
    if (low >= high) return;
    let pi = partition(arr, low, high);
  
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
}
  
let arr = [10, 80, 30, 90, 40];
console.log("Original array: " + arr);
  
quickSort(arr, 0, arr.length - 1);
console.log("Sorted array: " + arr);

Output

Original array: 10,80,30,90,40
Sorted array: 10,30,40,80,90

Conclusion

Quick sort is simple and easily implementable sorting technique that works on the divide and conquer approach. It is efficient for working on large dataset.

Time complexity of quickk sort is O(N log(N)) and auxiilary space required is O(N).


 


Reffered: https://www.geeksforgeeks.org

JavaScript

Related
Most Frequent Element in an Array using JavaScript Most Frequent Element in an Array using JavaScript
JavaScript Program to Check Whether the String is Symmetrical or Not JavaScript Program to Check Whether the String is Symmetrical or Not
JavaScript Program to Count the Occurrences of Each Character JavaScript Program to Count the Occurrences of Each Character
JavaScript Program to Find if a Character is a Vowel or Consonant JavaScript Program to Find if a Character is a Vowel or Consonant
JavaScript Program to Update the Value for a Specific Key in Map JavaScript Program to Update the Value for a Specific Key in Map

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje