Brian Yang algorithm designer Apr 14, 2020
2 min read
Implement Quicksort
Path from Comprehension to Implementation
The path to implementation is filled with gaps. It’s one thing to understand an algorithm. It’s another thing to be able to implement it. Often a course of learning explains the concept. The learner is left on their own, to implement this. Other factors make this more of a challenge. Nervousness, unfamiliarity, subtle changes to requirements, are some examples. The goal here is to provide you with tools to master implementation.
explain the concept
provide sample implementation
provide a means for you to partially implement a solution, with clues
full implementation from a blank slate
Video
Explanation
Partition helper moves smaller items to the left of the pivot and larger items to the right. Pointer tracks position, to be able to split the array in the next step.
const arr = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8]
function quickSort(items, left, right) {
if () {
//index returned from partition
if () {
//more elements on the left side of the pivot
}
if (index < right) {
//more elements on the right side of the pivot
}
}
}
quickSort(arr, 0, arr.length-1)
// helper methods provided
function swap(items, leftIndex, rightIndex){
var temp = items[leftIndex];
items[leftIndex] = items[rightIndex];
items[rightIndex] = temp;
}
function partition(items, left, right) {
var pivot = items[Math.floor((right + left) / 2)], //middle element
i = left, //left pointer
j = right; //right pointer
while (i <= j) {
while (items[i] < pivot) {
i++;
}
while (items[j] > pivot) {
j--;
}
if (i <= j) {
swap(items, i, j); //sawpping two elements
i++;
j--;
}
}
return i;
}
const arr = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8]
function quickSort(items, left, right) {
var index;
if (items.length > 1) {
index = partition(items, left, right); //index returned from partition
if (left < index - 1) { //more elements on the left side of the pivot
quickSort(items, left, index - 1);
}
if (index < right) { //more elements on the right side of the pivot
quickSort(items, index, right);
}
}
return items;
}
quickSort(arr, 0, arr.length-1)
function swap(items, leftIndex, rightIndex){
var temp = items[leftIndex];
items[leftIndex] = items[rightIndex];
items[rightIndex] = temp;
}
function partition(items, left, right) {
var pivot = items[Math.floor((right + left) / 2)], //middle element
i = left, //left pointer
j = right; //right pointer
while (i <= j) {
while (items[i] < pivot) {
i++;
}
while (items[j] > pivot) {
j--;
}
if (i <= j) {
swap(items, i, j); //sawpping two elements
i++;
j--;
}
}
return i;
}
Implement Full Solution
const array = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8];
function quickSort(){
// write code here
}
quickSort(arr, 0, arr.length-1)
// helper methods provided
function swap(items, leftIndex, rightIndex){
var temp = items[leftIndex];
items[leftIndex] = items[rightIndex];
items[rightIndex] = temp;
}
function partition(items, left, right) {
var pivot = items[Math.floor((right + left) / 2)], //middle element
i = left, //left pointer
j = right; //right pointer
while (i <= j) {
while (items[i] < pivot) {
i++;
}
while (items[j] > pivot) {
j--;
}
if (i <= j) {
swap(items, i, j); //sawpping two elements
i++;
j--;
}
}
return i;
}
output:
references: PennX: SD3x, Algorithm Design and Analysis
