Hello C# 008

"Young man, in mathematics you don't understand things. You just get used to them." – Von Neumann (maybe)

Computer sorting

Computer sorting is about ordering data. Generally it is required as an intermediate step while solving another problem, but is also useful by itself.

Unlike us, computers can sort thousands and thousands of items in a few seconds but they do not come with an universal sorting technique built in that is going to solve all scenarios as fast as possible. This is why sorting algorithms can be a good entry point to understand algorithms in general. They are not perfect, range from easy to get to very hard and even the most basic one can be really good sometimes.

Bubble sort   

And Bubble sort is a really interesting one to start the conversation. The idea here is that you are going to push the bigger values to the top, just like bubbles in soda.
If the value you're pushing up encounters a bigger one in the way, you start bubbling up the bigger one instead. On each pass you are sure you've sorted another element in the array and after the number of passes is equal to the size of the array, you're sure the array is sorted.

So here is an console application that implements the description above:

// Program.cs
// required to enable magic
using System.Linq;

// sort algorithm
void Bubble(int[] array)
{
// for(A; B; C) {...} is somewhat equals to
// A; while(B) { ...; C; }
for(int i = 0; i < array.Length; i++)
{ // do bubble pass here
for(int j = 0; j < array.Length-1; j++)
// do swap if needed
if (array[j] > array[j+1])
{
// bubble up if larger
(array[j], array[j + 1]) = (array[j + 1], array[j]);
}
}
}

// read an array from the user using spaces as separators
// using `magic`
var array = Console.ReadLine()!
.Split(' ')
.Select(x => int.Parse(x))
.ToArray();

// sort with bubble
Bubble(array);

// show the sorted array to the user
// using more magic
Console.Write("Sorted array:");
Console.WriteLine(array.AsEnumerable()
.Aggregate("", (x, y) => $"{x} {y}"));
// the user would type '3 4 1 4 <press enter/return key>'
// and get Sorted array: 3 4 1 4

[Try by yourself] The presented bubble description is 'bad'. But first we need ways to measure how bad is it. Add code to count the number of swaps and number of j > j+1 comparisons and print those values.

[Try by yourself] After you've added the changes to measure the performance, do a set of experiments with a few arrays (use at least one with more than 6 elements).

[Try by yourself] Because after each pass we know that the end of the array is sorted, couldn't we reduce the pass size each time up to `array.Length - 1 - i`? Do the necessary code changes to apply this optimization and repeat the set of experiments. Does it reduce the numbers of swaps or comparisons?

[Try by yourself] If there are no swaps during as pass can you be sure the array is sorted? If so, implement another optimization to exploit this detail and repeat the experiments.

Up Next

Structs!


Go home.

☆Powered by Azure Blob