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

# 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) {
} else {
}
}
ArrayList<Integer> sortedList = new ArrayList<Integer>();
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)
{
}
else
{
}
}
var sortedList = new List<int>();

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)
{
}
else
{
}
}
var sortedList = new List<int>();

return sortedList;
}
}
}
```