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

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.

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.

Structs!

Go home.

☆Powered by *Azure Blob*☆