**Things You Can Run Through** by Togashi Ni

July 22nd, 2010 8:59 AM *run through*a Quick Sort Algorithm. While doing this, we will also

*run through*

- an example

- a list

- a loop (or two or three)

- and finally, a block of code!

What is Quick Sort you ask? Well, think of it as a method of sorting that is usually faster than a worst case sorting scenario. Lets

*run through*an example:

**1) Find a list**

Oh look, here's one.. (25, 1, 8, 6, 12, 57, 23, 13, 9, 75, 54, 39, 27, 92, 21, 10, 40, 58, 67, 20)

**2) Pick a pivot point**

For simplicity sake, we will pick the first number for a pivot.. 25

**3) Now, go through your list. Place all numbers less than your pivot number in front of the pivot number, and all numbers greater than your pivot number after your pivot number**

After doing this, our new list will look thusly: (1, 8, 6, 12, 23, 13, 9, 21, 10, 20, 25, 57, 75, 54, 39, 27, 92, 40, 58, 67)

**4) Break your list into two lists. Everything before the pivot, and everything after the pivot. Repeat the sorting process with the new lists.**

Here's that loop I said we would

*run through*

**Iteration 1**

List A1: (1, 8, 6, 12, 23, 13, 9, 21, 10, 20)

List A2: (25)

List A3: (57, 75, 54, 39, 27, 92, 40, 58, 67)

**Iteration 2**

List A1B1: (1)

List A1B2: (8, 6, 12, 23, 13, 9, 21, 10, 20)

List A2: (25)

List A3B1: (54, 39, 27, 40)

List A3B2: (57)

List A3B3: (75, 92, 58, 67)

**Iteration 3**

List A1B1: (1)

List A1B2: (8, 6, 12, 23, 13, 9, 21, 10, 20)

List A1B2C1: (6)

List A1B2C2: (8)

List A1B2C3: (12, 23, 13, 9, 21, 10, 20)

List A2: (25)

List A3B1: (54, 39, 27, 40)

List A3B1C1: (39, 27, 40)

List A3B1C2: (54)

List A3B2: (57)

List A3B3: (75, 92, 58, 67)

List A3B3C1: (58, 67)

List A3B3C2: (75)

List A3B3C3: (92)

**And another few iterations (I went ahead and did them all, in the interest of time and space)**

List A1B1: (1)

List A1B2: (8, 6, 12, 23, 13, 9, 21, 10, 20)

List A1B2C1: (6)

List A1B2C2: (8)

List A1B2C3: (12, 23, 13, 9, 21, 10, 20)

List A2B2C3D1: (9, 10)

List A2B2C3D1E1: (9)

List A2B2C3D1E2: (10)

List A1B2C3D2: (12)

List A1B2C3D3: (23, 13, 21, 20)

List A1B2C3D3E1: (13, 21, 20)

List A1B2C3D3E1F1: (13)

List A1B2C3D3E1F2: (21, 20)

List A1B2C3D3E1F2G1: (20)

List A1B2C3D3E1F2G2: (21)

List A1B2C3D3E2: (23)

List A2: (25)

List A3B1: (54, 39, 27, 40)

List A3B1C1: (39, 27, 40)

List A3B1C1D1: (27)

List A3B1C1D2(39, 40)

List A3B1C1D1E1: (39)

List A3B1C1D1E2: (40)

List A3B1C2: (54)

List A3B2: (57)

List A3B3: (75, 92, 58, 67)

List A3B3C1: (58, 67)

List A3B3C1D1: (58)

List A3B3C1D2: (67)

List A3B3C2: (75)

List A3B3C3: (92)

Phew! If we take all the 1 item arrays, and put them back together we get our sorted list!

(1, 6, 8, 9, 10, 12, 13, 20, 21, 23, 25, 27, 39, 40, 54, 58, 67, 75, 92)

Now lest

*run through*the code:

Here's the MAIN method that will initialize our array (list), output it to the screen, and call our initial QuickSort to kick the whole shebang off.

static void Main( string[] args)

{

// Here's the instantiation of our list

int[] numbers = new int[20] { 25, 1, 8, 6, 12, 57, 23, 13, 9, 75, 54, 39, 27, 92, 21, 10, 40, 58, 67, 20 };

// Output the list so we can see it

Console.WriteLine("List prior to sorting");

OutputList(numbers);

if (numbers.Count() <= 1)

{

if(numbers.Count() > 0)

Console.WriteLine("1: " + numbers[0]);

}

// Call our QuickSort

int left = 0;

int rightIndex = numbers.Count() - 1;

int[] result = QuickSort(numbers, left,rightIndex);

OutputList(result);

Console.ReadLine();

}

Here is our QuickSort method. It takes our number array (list), left index, and right index as the input parameters. It will output a sorted list. The method uses the pivot, reorders the list (as in our example), and then calls itself to sort the resulting smaller lists until everything is sorted. Then, it returns the sorted list.

public static int<[] QuickSort(int[] numbers, int left, int right)

{

// Create and set some placeholder variables

int pivot, lindex, rindex;

lindex = left;

rindex = right;

pivot = numbers[left];

Console.WriteLine("Pivot Number: " + pivot);

while (left < right)

{

// Look for a number less than the pivot

while(numbers[right] >= pivot && (left{

right--;

}

// Number found! Move it to the Left location

if(left != right)

{

numbers[left] = numbers[right];

left++;

}

// Look for a number greather than the pivot

while((numbers[left] <= pivot) && (left < right))

{

left++;

}

// Number found, move it to the Right

if (left != right)

{

numbers[right] = numbers[left];

right--;

}

}

// Place pivot back in its proper place

numbers[left] = pivot;

// Restore values

pivot = left;

left = lindex;

right = rindex;

// Iteratively call sort on the sub-arrays

if (left < pivot)

{

QuickSort(numbers, left, pivot - 1);

}

if (right > pivot)

{

QuickSort(numbers, pivot + 1, right);

}

return numbers;

}

And there you have it! If I get sufficiently bored later today, I might update this and run through a proof to show how the average run time for Quick sort is O(n log n) instead of O(n

^{2}) which is typically seen in a Bubble or Insertion sort.

### 17 vote(s)

Pixie

3Zenobia

5LittleMonk

5Dela Dejavoo

4Ombwah

5Happy McDeath

5Amby D

5MsGoblinPants Extraordinaire

5rehsamsevoL Lovesmasher

2Mr. O.

5teucer

5Jefftownâ„˘

4Indy

3Gremlin

5Markov Walker

4Bet Monty

5PsyDlocke

### Terms

foecake, chicago### 11 comment(s)

You end on a weak note sir. Here are my quibbles with your statement that Quicksort is in O(n log n) and not O(n^{2}).

1) The definition of the big O:

O(h) = {f | there exists constants x_{0} and M such that for every x>x_{0}, |f(x)| =< M |h(x)|}

This entails that O(n log n) is a subset of O(n^{2}). Nothing can be a member of a subset and not its superset.

2) Quicksort's *average case* running time is in O(n log n), but it's *worst case* running time is not. It's worst case running time is in O(n^{2}).

I mean that in the absolutely most endearing way possible

You are correct. I did end on a weak note, and not properly discern between the average and worst case running time. I have updated the ending to reflect the proper terms.

Yeah. Point 1) is about a standard abuse of notation. Technically your statement about the running time being in O(n log n) instead of O(n^{2}) is still false (it is in both), but it is the way many in programming and CS talk.

Now Mergesort is in O(n log n) in both the average and worst case. In fact, the most common variant of the algorithm is in O(n log n) in the best case.

Personally, I'm a fan of radix sort. It's not just for integers.

So, first, how did you format your source code all pretty like that in this proof? I took a look at the source for this and I doubt you did that by hand. Did you copy and paste and SF0 generated the proper source, or did you use a tool and put the source in there yourself?

Second, I just found quicksort for OCaml on Wikipedia, and it's so short and beautiful, I had to share:

let rec qsort = function

| [] -> []

| pivot :: rest ->

let is_less x = x < pivot in

let left, right = List.partition is_less rest in

qsort left @ [pivot] @ qsort right

To format the code, I used hand coded HTML span tags. Each line of code got a Span tag. I incremented the "padding-left" value for the indentations, and changed the color tag for the text color. It took a bit... but I think was worth the effort.

That is a pretty sweet QuickSort. I like how compressed it is.

I've been trying to find another task to do with Code, but haven't been struck by any ideas yet.. hmm..

The Ocaml quicksort algorithm hides a lot of work in List.partition. Still, I like it because it reads like a clever mathematical definition of a sorted list.

Is this C#? It seems very Java-like, but not quite Java.

As for tasks to do with Code, I was just looking through the Task list and got a few ideas. Some I might keep for myself, but here's one you might try:

Build a random BACKRONYM generator. The user submits a word and it generates a BACKRONYM for it based on a probabilistic language model (trigrams will probably do) constrained by the first letter for each word.

oh, that's not really a quicksort, either. It does not sort in place. I believe the list is immutable (they are in Haskell, anyway, which has a similar looking "quicksort" implementation), so it returns a new list that is sorted. In fact, every recursive call creates new sublists.

Just so you know that it's not an apples to apples comparison, if you're going for code golf.

You are brave. I usually run

awayfrom numbers.