In a long standing tradition here on the Programming Underground we are going to add another entry to the definitive series. For those of you who are still relatively new to my blog, the definitive series is a series of blog entries where we take an algorithm and run it through the paces of five different languages: C++/C#/Java/VB.NET/PHP. With the code side by side we can see the similarities as well as show the code for your preferred language of choice. In this blog entry we show two styles of the selection sort.. one where we place the maximum found value at the end of an array and one where we find the minimum value and place it at the beginning of the array. So sit right back and run through the code at your leisure, we are going to hack some metal here on the Programming Underground!
So the idea behind the selection sort is to take an array, loop through the array from a starting point through to the end. We are looking for the largest/smallest value and swapping it to the end/beginning of the array respectively. We then modify the start point and look for the next highest/lowest value and swap it again. With each pass we are looping through a smaller and smaller subset of the original array.
Lets assume that our array has the values 3, 9, 1, 8, 5, 4, 6. The selection sort will start at the first value (3 in our case) and will keep going all the way through to the value 6. As it goes through the elements, it is keeping track what is the largest value (9) and where it was found in the array (subscript 1). When it reaches the end, it then swaps subscript 1 with the end of the array (where value 6 is located at subscript 6). Now our array is 3, 6, 1, 8, 5, 4, 9. We decrement our end value and again loop from 3 to 4. Since 8 is the largest of those numbers, it is swapped to the end and results in our array having the order 3, 6, 1, 4, 5, 8, 9.
As you can see we are slowly stacking the largest values at the end of the array in this variation. We can also run this in reverse and looking for the lowest value (1 in our example) and swap it to the beginning of the array. The value of the array would then be 1, 9, 3, 8, 5, 4, 6. The value 1 has been swapped with the value at subscript 1 which was the value 3. We then increment the start value and start from 9 on our next pass through.
Lets see how this is done in the various languages. Lets start with our favorite C++….
#include <iostream>
using namespace std;
void selectionSort1(int a[], int maxlen);
void selectionSort2(int a[], int maxlen);
int main() {
// Create first array and sort it using selection sort 1
int arr[10] = {4, 6, 5, 7, 8, 9, 1, 2, 3, 0};
selectionSort1(arr,10);
// Print out the sorted array
cout << "After selection sort 1..." << endl;
for (int i = 0; i < 10; i++) {
cout << arr[i] << endl;
}
cout << endl;
int arr2[10] = {4, 6, 5, 7, 8, 9, 1, 2, 3, 0};
selectionSort2(arr2,10);
cout << "After selection sort 2..." << endl;
for (int i = 0; i < 10; i++) {
cout << arr[i] << endl;
}
return 0;
}
// Selection sort in reverse, placing highest values at the end of the array
void selectionSort1(int a[], int maxlen) {
while (maxlen > 0) {
int position = 0;
int maxvalue = a[0];
// Loop through array from 0 to current end value looking for maximum value and its position
for (int i = 0; i < maxlen; i++) {
if (a[i] > maxvalue) {
maxvalue = a[i];
position = i;
}
}
// Swap
int temp = a[maxlen - 1];
a[maxlen - 1] = a[position];
a[position] = temp;
maxlen--;
}
}
// Minimum selection sort variant using while loop and for loop
void selectionSort2(int a[], int maxlen) {
int start = 0;
while (start < maxlen) {
int minvalue = a[start];
int position = start;
// Loop through array from start to end, looking for minimum value and its position
for (int i = start; i < maxlen; i++) {
if (a[i] < minvalue) {
minvalue = a[i];
position = i;
}
}
// Swap
int temp = a[start];
a[start] = a[position];
a[position] = temp;
start++;
}
}
As you can see from the code we have two variations. One is selectionSort1 and runs in “reverse” putting the largest values at the end of the array. selectionSort2 runs “forward” and places the minimum value at the beginning of the array. selectionSort2 is typically the one you see most often and is easier to comprehend for most beginners. As usual I have supplied in-code comments to show you what is being done and where.
How does this compare to C#?
namespace selectionSort
{
class Program
{
static void Main(string[] args)
{
// Create first array and sort it using selection sort 1
int[] arr = new int[]{4, 6, 5, 7, 8, 9, 1, 2, 3, 0};
selectionSort1(arr,10);
// Print out the sorted array
Console.WriteLine("After selection sort 1...");
for (int i = 0; i < 10; i++) {
Console.WriteLine(arr[i]);
}
Console.WriteLine();
// Create second array and sort it using seleciton sort 2
int[] arr2 = new int[]{4, 6, 5, 7, 8, 9, 1, 2, 3, 0};
selectionSort2(arr2,10);
// Print it out after sorting
Console.WriteLine("After selection sort 2...");
for (int i = 0; i < 10; i++) {
Console.WriteLine(arr2[i]);
}
}
// Selection sort in reverse, placing highest values at the end of the array
public static void selectionSort1(int[] a, int maxlen) {
while (maxlen > 0) {
int position = 0;
int maxvalue = a[0];
// Loop through array from 0 to current end value looking for maximum value and its position
for (int i = 0; i < maxlen; i++) {
if (a[i] > maxvalue) {
maxvalue = a[i];
position = i;
}
}
// Swap
int temp = a[maxlen - 1];
a[maxlen - 1] = a[position];
a[position] = temp;
maxlen--;
}
}
// Minimum selection sort variant using while loop and for loop
public static void selectionSort2(int[] a, int maxlen) {
int start = 0;
while (start < maxlen) {
int minvalue = a[start];
int position = start;
// Loop through array from start to end, looking for minimum value and its position
for (int i = start; i < maxlen; i++) {
if (a[i] < minvalue) {
minvalue = a[i];
position = i;
}
}
// Swap
int temp = a[start];
a[start] = a[position];
a[position] = temp;
start++;
}
}
}
}
You will notice that a lot of the syntax is the same, but here we have placed it within a console project. Some of the subtle changes are how we declare our function signatures, how we define our arrays, and how we print array values. Notice the use of Console.WriteLine to output the values to our console screen.
Jumping over to Java now…
public class selectionSort {
public static void main(String args[]) {
// Create first array and sort it using selection sort 1
int[] arr = new int[]{4, 6, 5, 7, 8, 9, 1, 2, 3, 0};
selectionSort1(arr,10);
// Print out the sorted array
System.out.println("After selection sort 1...");
for (int i = 0; i < 10; i++) {
System.out.println(arr[i]);
}
System.out.println();
// Create second array and sort it using seleciton sort 2
int[] arr2 = new int[]{4, 6, 5, 7, 8, 9, 1, 2, 3, 0};
selectionSort2(arr2,10);
// Print it out after sorting
System.out.println("After selection sort 2...");
for (int i = 0; i < 10; i++) {
System.out.println(arr2[i]);
}
}
// Selection sort in reverse, placing highest values at the end of the array
public static void selectionSort1(int a[], int maxlen) {
while (maxlen > 0) {
int position = 0;
int maxvalue = a[0];
// Loop through array from 0 to current end value looking for maximum value and its position
for (int i = 0; i < maxlen; i++) {
if (a[i] > maxvalue) {
maxvalue = a[i];
position = i;
}
}
// Swap
int temp = a[maxlen - 1];
a[maxlen - 1] = a[position];
a[position] = temp;
maxlen--;
}
}
// Minimum selection sort variant using while loop and for loop
public static void selectionSort2(int a[], int maxlen) {
int start = 0;
while (start < maxlen) {
int minvalue = a[start];
int position = start;
// Loop through array from start to end, looking for minimum value and its position
for (int i = start; i < maxlen; i++) {
if (a[i] < minvalue) {
minvalue = a[i];
position = i;
}
}
// Swap
int temp = a[start];
a[start] = a[position];
a[position] = temp;
start++;
}
}
}
Java syntax is very similar to the C# version. Since both C# and Java have roots back in C++, it is no wonder that they are so close. The main difference here is how Java declares a main class and sets up the main function. Pay special attention to the idea of functions being called as “static” from static main.
How does VB.NET accomplish this?
Module Module1
Sub Main()
' Create first array and sort it using selection sort 1
Dim arr() As Integer = New Integer() {4, 6, 5, 7, 8, 9, 1, 2, 3, 0}
selectionSort1(arr, 10)
' Print out the sorted array
Console.WriteLine("After selection sort 1...")
For i As Integer = 0 To 9
Console.WriteLine(arr(i))
Next
Console.WriteLine()
' Create second array and sort it using seleciton sort 2
Dim arr2() As Integer = New Integer() {4, 6, 5, 7, 8, 9, 1, 2, 3, 0}
selectionSort2(arr2, 10)
' Print it out after sorting
Console.WriteLine("After selection sort 2...")
For i As Integer = 0 To 9
Console.WriteLine(arr2(i))
Next
End Sub
'Selection sort in reverse, placing highest values at the end of the array
Public Sub selectionSort1(ByRef a() As Integer, ByVal maxlen As Integer)
Do While maxlen > 0
Dim position As Integer = 0
Dim maxvalue As Integer = a(0)
'Loop through array from 0 to current end value looking for maximum value and its position
For i As Integer = 0 To maxlen - 1
If a(i) > maxvalue Then
maxvalue = a(i)
position = i
End If
Next
'Swap
Dim temp As Integer = a(maxlen - 1)
a(maxlen - 1) = a(position)
a(position) = temp
maxlen -= 1
Loop
End Sub
'Minimum selection sort variant using while loop and for loop
Public Sub selectionSort2(ByRef a() As Integer, ByVal maxlen As Integer)
Dim start As Integer = 0
Do While start < maxlen
Dim minvalue As Integer = a(start)
Dim position As Integer = start
'Loop through array from start to end, looking for minimum value and its position
For i As Integer = start To maxlen - 1
If a(i) < minvalue Then
minvalue = a(i)
position = i
End If
Next
'Swap
Dim temp As Integer = a(start)
a(start) = a(position)
a(position) = temp
start += 1
Loop
End Sub
End Module
As always with VB.NET the language is very verbose. The advantage of this is that it makes it a bit more readable. The trick to watch for on this version is the definition of your for loops and their range. Remember to go to maxlen – 1. Otherwise VB will make the end value inclusive. If you had just put maxlen alone without the subtraction of 1 you would overrun the array. Also the arrays are using parenthesis instead of square brackets.
Last but not least, a server-side web language for all you web programmers out there. Here it is in PHP…
<?php
// Create first array and sort it using selection sort 1
$arr = array(4, 6, 5, 7, 8, 9, 1, 2, 3, 0);
selectionSort1($arr);
// Print out the sorted array
echo "After selection sort 1...<br/>";
for ($i = 0; $i < count($arr); $i++) {
echo $arr[$i] . "<br/>";
}
echo "<br/>";
$arr2 = array(4, 6, 5, 7, 8, 9, 1, 2, 3, 0);
selectionSort2($arr2);
echo "After selection sort 2...<br/>";
for ($i = 0; $i < count($arr2); $i++) {
echo $arr2[$i] . "<br/>";
}
// Selection sort in reverse, placing highest values at the end of the array
// Notice how we take in the array by reference
function selectionSort1(&$a) {
$maxlen = count($a);
while ($maxlen > 0) {
$position = 0;
$maxvalue = $a[0];
// Loop through array from 0 to current end value looking for maximum value and its position
for ($i = 0; $i < $maxlen; $i++) {
if ($a[$i] > $maxvalue) {
$maxvalue = $a[$i];
$position = $i;
}
}
// Swap
$temp = $a[$maxlen - 1];
$a[$maxlen - 1] = $a[$position];
$a[$position] = $temp;
$maxlen--;
}
}
// Minimum selection sort variant using while loop and for loop
// We also take in the array by reference here as well.
function selectionSort2(&$a) {
$maxlen = count($a);
$start = 0;
while ($start < $maxlen) {
$minvalue = $a[$start];
$position = $start;
// Loop through array from start to end, looking for minimum value and its position
for ($i = $start; $i < $maxlen; $i++) {
if ($a[$i] < $minvalue) {
$minvalue = $a[$i];
$position = $i;
}
}
// Swap
$temp = $a[$start];
$a[$start] = $a[$position];
$a[$position] = $temp;
$start++;
}
}
?>
With PHP we have to remember to change over the array initialization to use array(value1, value2, …) and to drop any data types. That and throw in a bunch of dollar signs for our variables and you have something that looks like C++ but with lots of money (get it? Dollar signs… yeah lame joke I know).
Take a minute to look through each language and compare them with the others. The subtleties in syntax is what we are after here on the definitive series blog entries. By comparing them directly like this, you can easily see how an algorithm you know in one language would translate over to another language… with little problem. In addition, it can help you learn another language if you are looking to do that or show you things you will need to change to port over code in the future.
I hope you found this entry entertaining and enlightening and feel free to use any of the code I have thrown out here on the blog. The second reason I like the definitive series is to allow beginners the opportunity to take and try code in various languages and find out which they like best.
So enjoy and thanks for reading! 🙂
