Quick sort for doubly linked lists

Sun, 15 May 2011

As soon as I got out of bed this morning I felt like writing a quick sort for linked lists. I had no idea why, but I decided to do it anyway (over a nice plate of scrambled eggs and bread – thanks mom!). The program ran correctly first compile! I proceeded to add a prettyprinter for each step. Here’s some output:

Sorting: 34 5 42 3 8 77 3 8 11 9 

  9   11   8   3   8   3   5  :34:  77   42 
  9   11   8   3   8   3   5  |34|  42  :77:
  5   3   8   3   8  :9:  11  |34|  42  |77|
  3   3  :5:  8   8  |9|  11  |34|  42  |77|
  3   3  |5| :8:  8  |9|  11  |34|  42  |77|
 :3:  3  |5| |8|  8  |9|  11  |34|  42  |77|

Sorted: 3 3 5 8 8 9 11 34 42 77

The first element is taken as the pivot at each step. Here, 34 is the first pivot. You can see that in the first step it’s put elements lesser than 34 before it, and those greater after. The next pivot is 77 (it recurses into the right side partition first).

Find the code here.

Back to posts

Menu

Home
Log
Biography
Projects
Music
Art

About
Contact
GitHub

Links

Ogre
Blender
Bullet
Arch

Unix is user-friendly. It's just very selective about who its friends are.

- Anonymous