Login

Quick Sort

Implement a function that sorts an array using the quick sort algorithm.

Advanced

Instructions

The Quick Sort Algorithm is a sorting algorithm that uses a divide-and-conquer approach to sort an array efficiently. The algorithm works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot.

Tip

The Quick Sort algorithm works as follows:

  1. Choose a pivot element from the array.
  2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
  3. Recursively sort the two sub-arrays.
  4. Concatenate the sorted sub-arrays with the pivot element in between.

Implement a function quickSort that takes an array of integers as input and returns the sorted array using the Quick Sort algorithm.

The function should have the following signature:

const quickSort = (myArray) => {...}

The function should return an array of integers in non-decreasing order.

For example, quickSort([9,4,2,1,5,3,1,5,8,4,3]) should return [1,2,4,5,9].

PS. The tests don't check if the quick sort algorithm is implemented correctly, but if the array is sorted correctly.

Tests
0/4
Function Call:
Expected:
quickSort([9,4,2,1,5,3,1,5,8,4,3])
[ 1, 2, 4, 5, 9 ]
Run test
quickSort([])
[]
Run test
Hidden Test
?
Run test
Hidden Test
?
Run test

Question

Implement a function that sorts an array using the quick sort algorithm.

The Quick Sort Algorithm

Quick Sort is a sorting algorithm that uses a divide-and-conquer approach to sort an array efficiently. The algorithm works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

Ps. The tests don't check if the quick sort algorithm is implemented correctly, but if the array is sorted correctly.

Tests
0/4
Function Call:
Expected:
quickSort([9,4,2,1,5,3,1,5,8,4,3])
[ 1, 2, 4, 5, 9 ]
Run test
quickSort([])
[]
Run test
Hidden Test
?
Run test
Hidden Test
?
Run test
See Solution

Solution

const quickSort = (myArray) => {
 
 if(myArray.length <= 1){
    return myArray
  }
  
  const pivot = myArray[0]
  
  const left = []
  const right = []
  
for (let i = 1; i < myArray.length; i++) {
    if(item < pivot){
      left.push(item)
    } else {
      right.push(item)
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)]
  
  
}

const quickSort = (arr) => {
    // Base case: If the array has 0 or 1 element, it's already sorted
    if (arr.length <= 1) {
        return arr;
    }

    // Choose a pivot element (e.g., the last element)
    const pivot = arr[arr.length - 1];
    
    // Partition the array into two sub-arrays: elements less than pivot and elements greater than pivot
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    
    // Recursively sort the two sub-arrays and concatenate them with the pivot in between
    return [...quickSort(left), pivot, ...quickSort(right)];
}

Algorithm Detailed Explanation

  1. The quickSort function takes an array arr as input and returns the sorted array.
  2. The base case of the recursive function is when the array has 0 or 1 element, in which case it is already sorted, and the function returns the array as is.
  3. The pivot element is chosen as the last element of the array.
  4. The array is then partitioned into two sub-arrays: left and right. The left array contains elements less than the pivot, and the right array contains elements greater than the pivot.
  5. The left and right sub-arrays are recursively sorted using the quickSort function.
  6. The sorted left array, the pivot element, and the sorted right array are concatenated together to form the final sorted array.
  7. The function returns the sorted array.

Complexity Analysis

  • Time complexity: The worst-case time complexity of quick sort is O(n^2), but the average-case time complexity is O(n log n). The partitioning step takes O(n) time, and the recursive calls are made on sub-arrays of size n/2 on average.
  • Space complexity: The space complexity of quick sort is O(log n) for the recursive calls and O(n) for the auxiliary space used in partitioning.
Any improvement idea? Share with us!