We will often want to sort data in an array. To achieve this, there are several simple algorithms, that are not particularly efficient, but they are easy to program. The lack of efficiency means that most of them are based on two nested "for" loops, so after each pass, one record would be sorted, and there would be as many pass as records, so that for an array with 1,000 data, we might need to make one million comparisons.
We might do slight improvements (for example, changing a "for" command for a "while" command, not to review all the data that were already sorted), and there are more effective methods, but these are more difficult to program.
We will see three of these simple sorting methods of sorting, first looking at each algorithm, and then joining them in one example program:
Bubble method
(Exchange every consecutive pair that is not ordered)
For i = 1 to n-1
For j = i +1 to n
If A[i] > A[j]
Swap (A[i], A[j])
(Note: some authors make the outer loop decrease:)
For i = n down to 2
For j = 2 to i
If A[j-1]> A[j]
Swap (A[j-1], A[j])
Direct Selection
(In each pass, we search for the smallest number, and we exchange it at the end of the pass)
For i = 1 to n-1
smallest = i
For j = i +1 to n
If A[j] < A[smallest]
smallest = j
If smallest <> i
Swap (A[i], A[smallest])
Note: The symbol "<>" is often used in pseudocode to indicate that data is different from another, so it is like the "!=" we use in C#.
Direct Insertion
(Compare each item with the ones above, which are already sorted, and move it to the its correct position).
For i = 2 to n
j = i-1
while (j >= 1) and (A[j] > A[j +1])
Swap (A[j], A[j +1])
j = j - 1
(It can be improved by not swapping values in each move, but only at the end of each pass, but we will not see more details).
A test program might be:
/*---------------------------*/
/* C# Example */
/* sort.cs */
/* */
/* Simple sorting methods */
/* */
/* Intro to C#, */
/* Nacho Cabanes */
/*---------------------------*/
using System;
public class SortExample
{
public static void Main()
{
int[] data = {5, 3, 14, 20, 8, 9, 1};
int i,j,aux;
int n=7; // Number of data
// BUBBLE SORT
// (Exchange every consecutive pair that is not ordered)
// For i = 1 to n-1
// For j = i +1 to n
// If A[i] > A[j]
// Swap (A[i], A[j])
Console.WriteLine("Sorting by bubble sort... ");
for(i=0; i < n-1; i++)
{
foreach (int record in data) // We display data
Console.Write("{0} ",record);
Console.WriteLine();
for(j=i+1; j < n; j++)
{
if (data[i] > data[j])
{
aux = data[i];
data[i] = data[j];
data[j] = aux;
}
}
}
Console.Write("Sorted:");
foreach (int record in data) // We display final data
Console.Write("{0} ",record);
Console.WriteLine();
// DIRECT SELECTION
// (In each pass, we search for the smallest number, and we exchange
// it at the end of the pass)
// For i = 1 to n-1
// smallest = i
// For j = i +1 to n
// If A[j] < A[smallest]
// smallest = j
// If smallest <> i
// Swap (A[i], A[smallest])
Console.WriteLine("\nSorting by direct selection... ");
int[] data2 = {5, 3, 14, 20, 8, 9, 1};
for(i=0; i < n-1; i++)
{
foreach (int record in data2) // We display data
Console.Write("{0} ",record);
Console.WriteLine();
int smallestPos = i;
for(j=i+1; j < n; j++)
if (data2[j] < data2[smallestPos])
smallestPos = j;
if (i != smallestPos)
{
aux = data2[i];
data2[i] = data2[smallestPos];
data2[smallestPos] = aux;
}
}
Console.Write("Sorted:");
foreach (int record in data2) // We display final data
Console.Write("{0} ",record);
Console.WriteLine();
// DIRECT INSERTION
// (Compare each item with the ones above, which are already sorted,
// and move it to the its correct position)
// For i = 2 to n
// j=i-1
// while (j >= 1) and (A[j] > A[j +1])
// Swap (A[j], A[j +1])
// j = j - 1
Console.WriteLine("\nSorting by direct insertion... ");
int[] data3 = {5, 3, 14, 20, 8, 9, 1};
for(i=1; i < n; i++)
{
foreach (int record in data3) // We display data
Console.Write("{0} ",record);
Console.WriteLine();
j = i-1;
while ((j>=0) && (data3[j] > data3[j+1]))
{
aux = data3[j];
data3[j] = data3[j+1];
data3[j+1] = aux;
j--;
}
}
Console.Write("Sorted:");
foreach (int record in data3) // We display final data
Console.Write("{0} ",record);
Console.WriteLine();
}
}
And its result would be:
Sorting by bubble sort...
5 3 14 20 8 9 1
1 5 14 20 8 9 3
1 3 14 20 8 9 5
1 3 5 20 14 9 8
1 3 5 8 20 14 9
1 3 5 8 9 20 14
Sorted:1 3 5 8 9 14 20
Sorting by direct selection...
5 3 14 20 8 9 1
1 3 14 20 8 9 5
1 3 14 20 8 9 5
1 3 5 20 8 9 14
1 3 5 8 20 9 14
1 3 5 8 9 20 14
Sorted:1 3 5 8 9 14 20
Sorting by direct insertion...
5 3 14 20 8 9 1
3 5 14 20 8 9 1
3 5 14 20 8 9 1
3 5 14 20 8 9 1
3 5 8 14 20 9 1
3 5 8 9 14 20 1
Sorted:1 3 5 8 9 14 20
Suggested exercises:
· A program that asks the user for several numbers, adds them to an array, keeps the array sorted and displays the result after adding each new data. It must finish when the user types "end."
· Extending the previous exercise, to add a second phase in which the user can "ask" the system if a value is in the array. As the array is sorted, the search will not be done until the end of the data, but only until the data is equal to the searched value or greater than it.
· Create a variant of the previous exercise, which instead of doing a linear search (from beginning to end), will use "binary search": it will begin comparing with the midpoint of the array; if our data is smaller, it will try again in the midpoint of the lower half of the array, and so on.
