# Algorithms Visualized

--

Quick Sort

The **Quick Sort** algorithm uses a **Divide and Conquer** strategy for sorting an array of items.** Divide and Conquer **is a technique that can be divided into the following three parts:

**Divide**the problem into two or more sub-problems of the same or related type**Conquer**the sub-problems by calling recursively until all the sub-problems are solved**Combine**the solutions to the sub-problems are then combined to give a solution to the original problem.

Here is the plan for a quick sort implementation in JavaScript.

First, pick a **pivot **element in the array. The pivot element should be the element that is as close to the middle of the array as possible.

Second, rearrange the array elements so that all elements smaller than the pivot element move to left side of of the **pivot**, and all greater elements move to right side of the **pivot**.

Third, recursively sort the subarrays on left and right of **pivot **element.

Let’s look at some code.

**Line 50**: populate a random unsorted array named unsortedArray.**Line 54**: set a const to the lowest index (lowIndex) in the the array passed in, in this case 0.**Line 57**: set a const to the highest index in the array (highIndex). In this case this value will be 5, because the array has 6 elements.**Line 61**: call the quickSort function, passing in the array along with lowIndex and highIndex.

Next, have a look at the **quickSort** function.

**Line 3–7**: **swap** is a helper function that swaps items in the targetArray, based on the lowIndex and highIndex values, swapping the values at the indexes. It is used later in the **quickSort **function.

**Line 10**: This is where the midpoint, or **pivot, **in the array is determined. The value of **pivotElement **after line 10 executes (the first time) is **2**, the element closest to the middle of the array:

`[7, 0, `**2**, 1, 9, 2]

**Line 13**: Set a variable, **leftPointer** to the value of the **lowIndex** passed, in this case **0**.

**Line 16**: Set a variable, **rightPointer** to the value of the **highIndex** passed, in this case **5**.

**Lines 19–35**: This is where the magic happens. The array elements are rearranged so that all elements smaller than the pivot element move to left side of of the **pivot**, and all greater elements move to right side of the **pivot**. The swap function is used to move elements from left of the pivot to the right and vice-versa.

**Line 35**: the values of the variables are as follows (after the first time through).

targetArray = [2, 0, 1, 2, 9, 7]

(all values lower than 2 are left of 2 and all values larger than 2 are on the right of 2)lowIndex = 0

highIndex = 5leftPointer = 3

rightPointer = 2

(the leftPointer has passed the rightPointer)

Remember, the **quickSort** function is going to be called recursively.

**Line 37–48**: The quicksort function is called recursively in order to sort the subarrays on left and right of **pivot **element.

**Line 47:** the **targetArray **is returned, fully sorted.

`[0, 1, 2, 2, 7, 9, 2]`

Why is it important to understand different methods of array sorting such as quick sort? Why not just use the built in array.sort() method in **JavaScript**?

Under the hood, the built in **JavaScript** array.sort() method, is actually implemented *using different sorting algorithms based on the browser the client is using*. Here is a stack overflow post discussing the differences.

The built in sort() uses **Insertion sort** in **V8 Engine of Chrome** and **Merge sort** in **Mozilla Firefox** and **Safari**.

There is a great animation of different sorting algorithms here. It can be seen that the quick sort algorithm performs faster than the insertion or merge sort.