Instruction
Code for Quicksort
Quicksort works by picking a pivot value, then splitting the full list into two sub-lists. The first sub-list has all the values less than or equal to the pivot, and the second sub-list has all the values greater than the pivot. The quicksort function recursively calls itself to sort these sublists, and then to sort the sublists of those sub-lists, until the full list is sorted.
Python
# Again, you can ignore these lines at the top. We're just using them
# to load a file full of numbers into a list.
import sys
from load import load_numbers
numbers = load_numbers(sys.argv[1])
# The Quicksort algorithm relies on recursion. To implement it, we'll
# write a recursive function. We'll accept the list of numbers to
# sort as a parameter.
def quicksort(values):
# Quicksort is recursive because it keeps calling itself with
# smaller and smaller subsets of the list you're trying to
# sort. We're going to need a base case where the recursion stops,
# so it doesn't enter an infinite loop. Lists that are empty don't
# need to be sorted. And lists with just one element don't need to
# be sorted, either. In both cases, there's nothing to flip
# around. So we'll make that our base case; if there are 0 or 1
# elements in the list passed to the "quicksort" function, we'll
# return the unaltered list to the caller.
if len(values) <= 1:
return values
# The code from here on out represents the recursive case. We need
# to create a list that will hold all the values less than the
# pivot. That list will be empty at first.
less_than_pivot = []
# We do the same for values greater than the pivot.
greater_than_pivot = []
# Next we need to choose the pivot value. For now, we just grab the
# first item from the list.
pivot = values[0]
# Then we loop through all the items in the list following the pivot.
for value in values[1:]:
# We check to see whether the current value is less than or equal
# to the pivot.
if value <= pivot:
# If it is, we copy it to the sub-list of values less than the
# pivot.
less_than_pivot.append(value)
# Otherwise, the current value must be greater than the pivot...
else:
# So we copy it to the other list.
greater_than_pivot.append(value)
# This last line is where the recursive magic happens. We call
# quicksort recursively on the sub-list that's less than the
# pivot. We do the same for the sub-list that's greater than the
# pivot. Those two calls will return sorted lists, so we combine
# the sorted values less than the pivot, the pivot itself, and the
# sorted values greater than the pivot. That gives us a complete,
# sorted list, which we return.
return quicksort(less_than_pivot) + [pivot] +
quicksort(greater_than_pivot)
# Lastly, we need to call our quicksort function with our list of
# numbers, and print the list it returns.
sorted_numbers = quicksort(numbers)
print(sorted_numbers)
Now, in your numbers subdirectory, save the following to a file named 8.txt:
4
6
3
2
9
7
3
5
And run this command in your terminal:
python quicksort.py numbers/8.txt
It outputs our sorted list!
[2, 3, 3, 4, 5, 6, 7, 9]
JavaScript
function quicksort(values) {
if (values.length <= 1) {
return values
}
var lessThanPivot = [];
var greaterThanPivot = [];
var pivot = values[0];
for (var i = 1; i < values.length; i++) {
if (values[i] <= pivot) {
lessThanPivot.push(values[i]);
} else {
greaterThanPivot.push(values[i]);
}
}
return quicksort(lessThanPivot).concat(pivot, quicksort(greaterThanPivot));
}
const testValues = [32, 100, 1, 2, 29, 28, 88, 3, 50, 67, 37, 1, 57, 20];
var sorted = quicksort(testValues);
console.log(sorted);
Java
import java.util.*;
public class Sort {
static ArrayList<Integer> quicksort(ArrayList<Integer> list) {
if (list.size() <= 1) {
return list;
}
ArrayList<Integer> lessThanPivot = new ArrayList<Integer>();
ArrayList<Integer> greaterThanPivot = new ArrayList<Integer>();
int pivot = list.get(0);
int length = list.size();
for (int i = 1; i < length; i++) {
int currentValue = list.get(i);
if (currentValue <= pivot) {
lessThanPivot.add(currentValue);
} else {
greaterThanPivot.add(currentValue);
}
}
ArrayList<Integer> sortedList = new ArrayList<Integer>();
sortedList.addAll(quicksort(lessThanPivot));
sortedList.add(pivot);
sortedList.addAll(quicksort(greaterThanPivot));
return sortedList;
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(32, 100, 1, 2, 29, 28, 88, 3, 50, 67, 37, 1, 57, 20));
System.out.println(quicksort(list));
}
}
C-Sharp
using System;
using System.Collections.Generic;
namespace SortMethods
{
class MainClass
{
public static void Main(string[] args)
{
var list = new List<int>() { 32, 100, 1, 2, 29, 28, 88, 3, 50, 67, 37, 1, 57, 20 };
var sortedList = SortExamples.Quicksort(list);
Console.WriteLine(String.Join(", ", sortedList));
}
}
public static class SortExamples
{
public static List<int> Quicksort(List<int> list)
{
if (list.Count <= 1)
{
return list;
}
var lessThanPivot = new List<int>();
var greaterThanPivot = new List<int>();
int pivot = list[0];
int length = list.Count;
for (int i = 1; i < length; i++)
{
int currentValue = list[i];
if (currentValue <= pivot)
{
lessThanPivot.Add(currentValue);
}
else
{
greaterThanPivot.Add(currentValue);
}
}
var sortedList = new List<int>();
sortedList.AddRange(Quicksort(lessThanPivot));
sortedList.Add(pivot);
sortedList.AddRange(Quicksort(greaterThanPivot));
return sortedList;
}
}
}
C-Sharp
using System;
using System.Collections.Generic;
namespace Quicksort
{
class MainClass
{
public static void Main(string[] args)
{
var list = new List<int>() { 32, 100, 1, 2, 29, 28, 88, 3, 50, 67, 37, 1, 57, 20 };
var sortedList = Quicksort(list);
Console.WriteLine(String.Join(", ", sortedList));
}
public static List<int> Quicksort(List<int> list)
{
if (list.Count <= 1)
{
return list;
}
var lessThanPivot = new List<int>();
var greaterThanPivot = new List<int>();
int pivot = list[0];
int length = list.Count;
for (int i = 1; i < length; i++)
{
int currentValue = list[i];
if (currentValue <= pivot)
{
lessThanPivot.Add(currentValue);
}
else
{
greaterThanPivot.Add(currentValue);
}
}
var sortedList = new List<int>();
sortedList.AddRange(Quicksort(lessThanPivot));
sortedList.Add(pivot);
sortedList.AddRange(Quicksort(greaterThanPivot));
return sortedList;
}
}
}