Part 3: Quick sort!

THE SORTENING

Quick sort is another divide-and-conquer sorting algorithm. It is different from merge sort in that it has no "merge" function and it does not form the sublists by simply halving the superlist. Quick sort chooses a "pivot," to which it compares each item in the list and places those items less than the pivot in one list, and those greater than (or equal to) in the other. Quick sort is then run on each list, and the results thereof are concatenated, with the pivot between them.

Part 2: Merge sort

Merge sort is another of the sorts we looked at in class and, like it's cousin quick sort, it's a recursive divide-and-conquer algorithm that works by dividing the list to be sorted into two smaller lists and applying the sort algorithm to each. Merge sort does this in the most obvious way: by simply taking the first and second halves of the list to be each sublist.

Sorting: Selection Sort

Okay, so the first sorting algorithm I will describe is selection sort. This sort is simple to implement, but simple to criticize, as it performs the worst of the three we will discuss. Also perhaps of note is that this is the only non-inherently recursive algorithm, by which I mean that, while it can be implemented recursively, there is little benefit; the recursive algorithm does the same as an iterative one that includes a loop in which the "fenceposts" are moved on each pass through. But I digress—onto the algorithm itself.

Sorting algorithms

So it seems to be time to talk about the perennial topic of programming courses: sorting.
Sorting is essential to completing many programming tasks, it serves as a good way to introduce students to different approaches and programming paradigms, and it is a great example to demonstrate how to compare the complexity and efficiency of competing algorithms and discuss ways to minimize and maximize these. The second and third reasons are why it is beneficial to learn about various sorting algorithms and how to implement them. despite the fact that python has an excellent algorithm coded into it which performs better than any that students in a first year course would conceive or easily grasp. To detail some of the algorithms we discussed in class, the following few posts will describe selection, quick, and merge sort, as well as compare their relative efficiencies and display the various types of input data on which they perform best and worst.

Assigniety

So it's that time of year again.
No, not Christmas, that's still a few weeks away yet (despite what the department stores seem to think.)
And no, I don't mean Guy Fawkes' night either, although that is tonight. ('Remember, remember...')

I mean assignment submission time.

Yes; in just a few hours I'll be sending my baby away to be marked; and though I've been preparing him for this for days—leading him by hand through dozens of test cases and making tiny improvements to his efficiency—I can't help but feel that there's something I've forgotten.

While I'm sipping mulled wine by the flickering light of a burning effigy, little Reggie will be torn apart line by line, scrutinized intensely, ran through tests by unsympathetic people he's never met, and I'll just have to sit there and hope he's not missing a comment or parenthesis.

Here's to you, Reggie.