Last active
April 27, 2019 21:48
-
-
Save benfluleck/c62762cea29128c24ba35e0fcbc66597 to your computer and use it in GitHub Desktop.
Quick sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const items = [5,3,7,6,2,9]; | |
function swapNumbers(items, leftIndex, rightIndex){ | |
const temp = items[leftIndex]; | |
items[leftIndex] = items[rightIndex]; | |
items[rightIndex] = temp; | |
} | |
function partition(items, left, right) { | |
const pivotNumber = items[Math.floor((right + left) / 2)] | |
while (left <= right) { | |
while (items[left] < pivotNumber) { | |
left++; | |
} | |
while (items[right] > pivotNumber) { | |
right--; | |
} | |
if (left <= right) { | |
swapNumbers(items, left, right); | |
left++; | |
right--; | |
} | |
} | |
return left; | |
} | |
function quickSort(items, left, right) { | |
const index; | |
if (items.length > 1) { | |
index = partition(items, left, right); | |
if (left < index - 1) { | |
quickSort(items, left, index - 1); | |
} | |
if (index < right) { | |
quickSort(items, index, right); | |
} | |
} | |
return items; | |
} | |
const sortedArray = quickSort(items, 0, items.length - 1); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Order: O(nlogn)
Quick Sort is based on the concept of Divide and Conquer, just like merge sort. A pivot element is selected, this can be any element in the array. After selecting an element as pivot, we divide the array for the first time. Then the array undergoes partitioning, the array elements are so positioned that all the elements smaller than the pivot will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it.
And the pivot element will be at its final sorted position.
The elements to the left and right, may not be sorted.
Then we pick subarrays, elements on the left of pivot and elements on the right of pivot, and we perform partitioning on them by choosing a pivot in the subarrays.