One of the funnest things about being fluent in multiple languages is porting code from one language to another or in my case, porting a piece of code to 6 or 7 languages and allowing any newbie the opportunity to learn algorithms despite their language. It also makes it great to see the differences between languages and some challenges (as we will see with our Java example). On this entry we will take a mystical adventure with quicksort that will take us through the depths of C++, across the hills of the .NET platform, and through the caves of Java and PHP. So sit back, put on your seatbelts and enjoy the ride with this entry of the Programming Underground!
There are many sorts in the world and quicksort is neither the worst or the best of them. The sort uses the idea of picking a pivot point value in a list of numbers and moving all items less than that value before it and all those values higher than the pivot after it. The same number as the pivot can go to either side. It then takes the lower values and calls itself to do the sort all over again followed by a sort of the higher numbers. By the time all the recursive calls have happened, you have a sorted list. It is a divide and conquer type strategy that gives on average an O(log n log) timing with worst case being O(n^2). This is especially great for shorter lists and provides better speed than something like bubblesort.
In this entry I am going to show you the quicksort implementation known as the “in-place partitioning” which means rather than breaking the values out into something like a separate set of arrays and then merging them together again, we are going to do a bunch of swapping. This provides even greater speed with reduced use of memory than one that has to create separate arrays and run a merge. So if you are limited on time and space, this is a great mechanism for sorting a nice list of values. Our examples are going to be handling an integer array we setup but with little modifications on the comparisons, you could get it to work for strings and even objects if you overload the appropriate operator or implement the right interface.
Lets start the journey with C++!
#include <iostream>
using namespace std;
void quicksort(int*, int, int);
int partition(int*, int, int, int);
void swap(int &, int &);
int main()
{
int myarray[10] = { 2, 5, 3, 6, 7, 9, 1, 4, 8, 0 };
quicksort(myarray, 0, 9);
for (int i = 0; i < 10; i++) {
cout << myarray[i] << endl;
}
return 0;
}
// Quicksort controller function, it partitions the different pieces of our array.
void quicksort(int *arIntegers, int left, int right) {
if (right > left) {
int pivotIndex = left;
int pivotNewIndex = partition(arIntegers, left, right, pivotIndex);
// Recursive call to quicksort to sort each half.
quicksort(arIntegers, left, pivotNewIndex-1);
quicksort(arIntegers, pivotNewIndex+1, right);
}
}
// This function takes an array (or one half an array) and sorts it.
// It then returns a new pivot index number back to quicksort.
int partition(int *arIntegers, int left, int right, int pivot) {
int pivotValue = arIntegers[pivot];
// Swap it out all the way to the end of the array
// So we know where it always is.
swap(arIntegers[pivot], arIntegers[right]);
int storeIndex = left;
// Move through the array from start to finish comparing each to our
// pivot value (not index, the value that was located at the pivot index)
for (int i = left; i < right; i++) {
if (arIntegers[i] <= pivotValue) {
swap(arIntegers[i], arIntegers[storeIndex]);
storeIndex++;
}
}
swap(arIntegers[storeIndex], arIntegers[right]);
return storeIndex;
}
// Simple swap function for our in place swapping.
void swap(int &val1, int &val2) {
int temp = val1;
val1 = val2;
val2 = temp;
}
For those of you who are old C++ gurus, you probably have seen a lot of variations on this quicksort. Some probably more condensed than this, but I wanted to break it out a bit to show those who are new to programming (or this algorithm) how we might look at the different parts of this sort. It also provides for greater reuse in that, for instance, we could use the swap for another sort like a bubblesort we might have implemented later. This template is the standard setup for all of the other examples and will allow those newwwwbies to see the subtle differences in implementation between languages.
As you can see we have our classic main function and three other functions. The quicksort function here acts as a controller function, calling the appropriate pieces on our data as needed to get the job done. The second function is our partitioning function which essentially works on a piece of our overall array at a time, calling swap when it needs to move two values. Lastly is our swap function for swapping values.
One thing I want people to notice about this is the use of pass by reference calls. I could have used pointers here as well but I thought why not be a bit different and keep some pointer work out of everything as much as possible (you see I still use it for the arrays). Using pass by reference I am modifying actual values passed to the function, not a copy of the data. So if I was to set a variable to 5 and pass it to the function where I change it to 6, the original value of 5 is gone. If I had passed this by value I would have modified the value to 6 [u]inside the function[/u] and after the function goes out of scope, the original value would have still been 5.
The beauty of doing it this way is that I don’t need to use additional memory to copy values and I also can modify elements of the array directly without having copies of some variables (not that it really matters too much with today’s computers but still).
Lets take a look at this implementation in C#, a natural port over from C++. As you will notice, not too many differences other than having to change syntax a little and create some objects using the new keyword.
namespace quicksort
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
int[] myarray = new int[]{ 2, 5, 3, 6, 7, 9, 1, 4, 8, 0 };
quicksort(myarray, 0, 9);
for (int i = 0; i < 10; i++) {
list1.Items.Add(myarray[i]);
}
}
// Quicksort controller function, it partitions the different pieces of our array.
private void quicksort(int[] arIntegers, int left, int right) {
if (right > left) {
int pivotIndex = left;
int pivotNewIndex = partition(arIntegers, left, right, pivotIndex);
// Recursive call to quicksort to sort each half.
quicksort(arIntegers, left, pivotNewIndex-1);
quicksort(arIntegers, pivotNewIndex+1, right);
}
}
// This function takes an array (or one half an array) and sorts it.
// It then returns a new pivot index number back to quicksort.
private int partition(int[] arIntegers, int left, int right, int pivot) {
int pivotValue = arIntegers[pivot];
// Swap it out all the way to the end of the array
// So we know where it always is.
swap(ref arIntegers[pivot], ref arIntegers[right]);
int storeIndex = left;
// Move through the array from start to finish comparing each to our
// pivot value (not index, the value that was located at the pivot index)
for (int i = left; i < right; i++) {
if (arIntegers[i] <= pivotValue) {
swap(ref arIntegers[i], ref arIntegers[storeIndex]);
storeIndex++;
}
}
swap(ref arIntegers[storeIndex], ref arIntegers[right]);
return storeIndex;
}
// Simple swap function for our in place swapping.
private void swap(ref int val1, ref int val2) {
int temp = val1;
val1 = val2;
val2 = temp;
}
}
}
Here we have made a few changes. First one is the use of the form_load event to launch our quicksort instead of a main. Second, we declare the array using the “new” keyword. You will also notice that when we pass our variables by reference to the swap function, we use the “ref” keyword in both the call and in the function signature of swap. Lastly we spit the values into a listbox instead of to screen like in our C++ implementation. In the end you should have a listbox with the sorted list of numbers in it.
How about a little Java shall we? This implementation has a little quirk since it doesn’t support pass by reference directly. To get the pass by reference to work, we create our own little wrapper class called “MyInteger” which will wrap around our ints and allow us the chance to pass them by reference using our object. We then need to configure them, swap them, and then pull the values back out and into the array. It is a little bit more wordy and such, but the idea is pretty straight forward.
public class quicksort {
public static void main(String args[]) {
int[] myarray = new int[]{ 2, 5, 3, 6, 7, 9, 1, 4, 8, 0 };
quicksort(myarray, 0, 9);
for (int i = 0; i < 10; i++) {
System.out.println(myarray[i]);
}
}
// Quicksort controller function, it partitions the different pieces of our array.
private static void quicksort(int[] arIntegers, int left, int right) {
if (right > left) {
int pivotIndex = left;
int pivotNewIndex = partition(arIntegers, left, right, pivotIndex);
// Recursive call to quicksort to sort each half.
quicksort(arIntegers, left, pivotNewIndex-1);
quicksort(arIntegers, pivotNewIndex+1, right);
}
}
// This function takes an array (or one half an array) and sorts it.
// It then returns a new pivot index number back to quicksort.
private static int partition(int[] arIntegers, int left, int right, int pivot) {
int pivotValue = arIntegers[pivot];
// Create a copy of our inner custom class so we can pass by a reference type
quicksort quick = new quicksort();
quicksort.MyInteger value1 = quick.new MyInteger();
quicksort.MyInteger value2 = quick.new MyInteger();
// Swap it out all the way to the end of the array
// So we know where it always is.
// We do this using our custom class so we can swap by reference types since Java doesn't support pass-by-reference.
value1.insertValue(arIntegers[pivot]);
value2.insertValue(arIntegers[right]);
swap(value1, value2);
// After swap is made, we dump back to integer array to make the actual switch.
arIntegers[pivot] = value1.getValue();
arIntegers[right] = value2.getValue();
int storeIndex = left;
// Move through the array from start to finish comparing each to our
// pivot value (not index, the value that was located at the pivot index)
for (int i = left; i < right; i++) {
if (arIntegers[i] <= pivotValue) {
value1.insertValue(arIntegers[i]);
value2.insertValue(arIntegers[storeIndex]);
swap(value1, value2);
arIntegers[i] = value1.getValue();
arIntegers[storeIndex] = value2.getValue();
storeIndex++;
}
}
value1.insertValue(arIntegers[storeIndex]);
value2.insertValue(arIntegers[right]);
swap(value1, value2);
arIntegers[storeIndex] = value1.getValue();
arIntegers[right] = value2.getValue();
return storeIndex;
}
// Simple swap function for our in place swapping.
private static void swap(MyInteger val1, MyInteger val2) {
int temp = val1.getValue();
val1.insertValue(val2.getValue());
val2.insertValue(temp);
}
// Integer wrapper class so we can pass by reference to our swap function.
class MyInteger {
private int x;
public MyInteger() {}
public int getValue() { return x; }
public void insertValue(int xIn) { x = xIn;}
}
}
Just read through the comments and you will see where I have created two instances of our inner class, dumped some values into them using the classes mutator method, passed them to swap to be swapped, and then pull the values back out to place them in the array. There are a bit simpler implementations out there, but in keeping with our pass by reference methodology, we will do it like this. (Oh and just so I don’t get any comments about this not being true pass by reference, I know.)
Lets move on over to the beauty of VB.NET and how it goes about handling this little snippet!
Public Class Form1
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
Dim myarray() As Integer = {2, 5, 3, 6, 7, 9, 1, 4, 8, 0}
quicksort(myarray, 0, 9)
Dim i As Integer = 0
For i = 0 To 9
list1.Items.Add(myarray(i))
Next
End Sub
' Quicksort controller function, it partitions the different pieces of our array.
Private Sub quicksort(ByRef arIntegers() As Integer, ByVal left As Integer, ByVal right As Integer)
If Right > Left Then
Dim pivotIndex As Integer = Left
Dim pivotNewIndex As Integer = partition(arIntegers, left, right, pivotIndex)
' Recursive call to quicksort to sort each half.
quicksort(arIntegers, left, pivotNewIndex - 1)
quicksort(arIntegers, pivotNewIndex + 1, Right)
End If
End Sub
' This function takes an array (or one half an array) and sorts it.
'It then returns a new pivot index number back to quicksort.
Private Function partition(ByRef arIntegers() As Integer, ByVal left As Integer, ByVal right As Integer, ByVal pivot As Integer) As Integer
Dim pivotvalue As Integer = arIntegers(pivot)
' Swap it out all the way to the end of the array
' So we know where it always is.
swap(arIntegers(pivot), arIntegers(right))
Dim storeIndex As Integer = left
' Move through the array from start to finish comparing each to our
' pivot value (not index, the value that was located at the pivot index)
Dim i As Integer = left
For i = left To right - 1
If arIntegers(i) <= pivotvalue Then
swap(arIntegers(i), arIntegers(storeIndex))
storeIndex = storeIndex + 1
End If
Next
swap(arIntegers(storeIndex), arIntegers(right))
Return storeIndex
End Function
' Simple swap function for our in place swapping.
Private Sub swap(ByRef val1 As Integer, ByRef val2 As Integer)
Dim temp As Integer = val1
val1 = val2
val2 = temp
End Sub
End Class
As you can see we have a bit of syntax change, just because VB is more focused on the wordy readability methodology, and a few little changes in the way this works using the “ByRef” keyword to pass by reference and in one of our for loops we subtract one from the “right” variable because the for loop is initially setup to be inclusive when we need it to be exclusive on our far right value. Again we dump the values out to a listbox so you can see the sorted list and that it is working correctly.
Don’t worry programmers in web page land, I have created a PHP version for you too! You probably could have taken the C++ or C# versions and easily adapted it to PHP, but I figured why not do one for you guys and save you some trouble. The syntax is very similar and the principles are all there, it is just a matter of changing the variables to include dollar signs ($) and to declare your test array slightly different.
<?php
$myarray = array( 2, 5, 3, 6, 7, 9, 1, 4, 8, 0 );
quicksort($myarray, 0, 9);
for ($i = 0; $i < 10; $i++) {
echo $myarray[$i] . "<br/>";
}
// Quicksort controller function, it partitions the different pieces of our array.
function quicksort(&$arIntegers, $left, $right) {
if ($right > $left) {
$pivotIndex = $left;
$pivotNewIndex = partition($arIntegers, $left, $right, $pivotIndex);
// Recursive call to quicksort to sort each half.
quicksort($arIntegers, $left, $pivotNewIndex-1);
quicksort($arIntegers, $pivotNewIndex+1, $right);
}
}
// This function takes an array (or one half an array) and sorts it.
// It then returns a new pivot index number back to quicksort.
function partition(&$arIntegers, $left, $right, $pivot) {
$pivotValue = $arIntegers[$pivot];
// Swap it out all the way to the end of the array
// So we know where it always is.
swap($arIntegers[$pivot], $arIntegers[$right]);
$storeIndex = $left;
// Move through the array from start to finish comparing each to our
// pivot value (not index, the value that was located at the pivot index)
for ($i = $left; $i < $right; $i++) {
if ($arIntegers[$i] <= $pivotValue) {
swap($arIntegers[$i], $arIntegers[$storeIndex]);
$storeIndex++;
}
}
swap($arIntegers[$storeIndex], $arIntegers[$right]);
return $storeIndex;
}
// Simple swap function for our in place swapping.
function swap(&$val1, &$val2) {
$temp = $val1;
$val1 = $val2;
$val2 = $temp;
}
?>
Again notice the use of an ampersand on the parameters of our swap function variables to denote that they are by reference. Other than that and a few changes in the function signatures, it is pretty close to the C++ implementation.
Wow, what a big mission it was to create this entry. Lots of conversion, little bit of writing, but hopefully I slammed the quicksort out of the park for a bunch of newbies in the future. Feel free to take whichever version you like and adapt it to meet your needs. I just ask that you don’t use it if it is part of an assignment for school. It would help you much more if you did the work yourself and learned it, so that in the future when your employer asks you to “code one up real quick” you won’t need to run to DIC and pull it from my blog.
Thanks for reading and I hope this entry proves useful to all those programmers out there! Now I got to go clean up Tinky Winky off the rocks. A clean firing range is a happy firing range so says the firing squad Sargent… but he said it in Spanish. At least I hope that is what he said. :unsure:
