PLAYERS TASKS PRAXIS TEAMS EVENTS
Username:Password:
New player? Sign Up Here
Togashi Ni
Human Googlebot
Level 6: 1127 points
Last Logged In: December 16th, 2011
TEAM: Team FOEcakes BART Psychogeographical Association Rank 1: Commuter EquivalenZ Rank 2: Human Googlebot The University of Aesthematics Rank 1: Expert Humanitarian Crisis Rank 1: Peacekeeper Biome Rank 1: Hiker Society For Nihilistic Intent And Disruptive Efforts Rank 1: Anti




5 + 75 points

Things You Can Run Through by Togashi Ni

July 22nd, 2010 8:59 AM

INSTRUCTIONS: Find some.

Certainly, you'll have to make certain said things can be run through.

Slow day today.. I wish I could run through the day. Maybe if I do a task the day will run by (or at least go by faster). Hmm.. what to do.. I know, let's do some programming! Our lesson plan will be simple, to 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(n2) which is typically seen in a Bubble or Insertion sort.

17 vote(s)



Terms

chicago, foecake

11 comment(s)

(no subject) -1
posted by LittleMonk on July 22nd, 2010 9:56 AM

You are brave. I usually run away from numbers.

(no subject) +1
posted by Markov Walker on July 22nd, 2010 11:01 AM

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(n2).

1) The definition of the big O:
O(h) = {f | there exists constants x0 and M such that for every x>x0, |f(x)| =< M |h(x)|}

This entails that O(n log n) is a subset of O(n2). 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(n2).

DORK +1
posted by Pixie on July 22nd, 2010 11:38 AM

I mean that in the absolutely most endearing way possible

(no subject)
posted by Togashi Ni on July 22nd, 2010 11:42 AM

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.

(no subject)
posted by Markov Walker on July 22nd, 2010 12:27 PM

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(n2) 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.

(no subject)
posted by Mr. O. on July 24th, 2010 12:21 PM

Nerd!

Nerd praxis is the best kind.
posted by teucer on July 24th, 2010 1:51 PM

Yeah he is.

(no subject)
posted by Markov Walker on August 4th, 2010 6:39 PM

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

Code Formatting
posted by Togashi Ni on August 12th, 2010 2:25 PM

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..

(no subject)
posted by Markov Walker on August 27th, 2010 11:46 AM

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.

(no subject)
posted by Markov Walker on January 11th, 2011 7:34 PM

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.