JavaScript Coding Test Course, Quick Sort

One of the frequently encountered problems in coding tests is array sorting. In this tutorial, we will learn about the Quick Sort algorithm and explain in detail how to implement it in JavaScript. Quick sort is an efficient sorting algorithm that uses the divide and conquer technique.

Problem Description

Sort the given array in ascending order using the quick sort algorithm.

Example Input: [34, 7, 23, 32, 5, 62]
Example Output: [5, 7, 23, 32, 34, 62]

Overview of Quick Sort Algorithm

Quick sort proceeds through the following steps.

  1. Select one element from the array as the pivot.
  2. Divide the array into two subarrays based on the pivot. One consists of elements smaller than the pivot, while the other consists of elements larger than the pivot.
  3. Apply the same method recursively to each subarray.
  4. Repeat until the subarrays have a size of 0 or 1.

Example Explanation

If the input array is [34, 7, 23, 32, 5, 62], it undergoes the following process.

  1. Selecting Pivot: Choose 62, the last element of the array, as the pivot.
  2. Partitioning: Divide the array into elements smaller than pivot 62 ([34, 7, 23, 32, 5]) and larger elements ([]) based on the pivot.
  3. Recursive Call: Repeat the same process for the subarray [34, 7, 23, 32, 5], which is smaller than the pivot.
  4. By repeating this process, the array will ultimately be sorted.

JavaScript Implementation

Now, let’s implement the quick sort algorithm in JavaScript.

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr; // Return as is if the size is 0 or 1
    }
    
    const pivot = arr[arr.length - 1]; // Choose the last element as pivot
    const left = []; // Array to store elements less than the pivot
    const right = []; // Array to store elements greater than the pivot

    // Iterate through the array and compare with the pivot
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    // Recursive calls and return the result array
    return [...quickSort(left), pivot, ...quickSort(right)];
}

// Example array
const array = [34, 7, 23, 32, 5, 62];
const sortedArray = quickSort(array);
console.log(sortedArray); // [5, 7, 23, 32, 34, 62]

Time Complexity of the Algorithm

The average time complexity of the quick sort algorithm is O(n log n). However, in the worst case, it can have a time complexity of O(n²). This can occur when the pivot selection is imbalanced. For this reason, quick sort can be optimized through techniques such as randomly selecting the pivot to enhance performance.

Advantages and Disadvantages of Quick Sort

Advantages

  • An efficient sorting algorithm suitable for sorting large datasets.
  • It uses less memory, allowing for in-place sorting.

Disadvantages

  • In the worst case, the time complexity of O(n²) is inefficient.
  • It uses stack memory due to recursive calls.

Conclusion

In this tutorial, we learned about the quick sort algorithm and how to implement it in JavaScript. Quick sort is a simple and efficient sorting algorithm frequently used in coding tests and algorithm problem solving. Based on what you have learned, try solving various array sorting problems.

In the next tutorial, we will cover another sorting algorithm, Merge Sort. Please stay tuned!