Selection Sort Algorithm is one of the simplest sorting algorithm like BubbleSort. However this is not efficient when it comes to TimeCompexity.

Overview

In this algorithm we try to divide the array into two halves – sorted half and unsorted half. In the first pass, the sorted half contains the first element of the array. In the first pass, we compare the first element (from the sorted half) against the first element in the unsorted half. If first element (in sorted half) is greater than the first element in the unsorted half, we do a swapping of these two items. We continue this process until we finish comparing all elements in the unsorted half. At the end of the first pass, we make sure that first element in the array is the lowest one.This is one pass.

In the second pass, we consider 2nd element in the array and compare against each and every element in the unsorted half. We continue with passing for n-1 iterations (covering up to n-2 th item in the sorted half).

Advantages

1. Easy to implement the algorithm
2. In-place sort requires no additional memory for storage

Pseudocode

//Outer loop for passes

for (int i=0 ; i<num.Lenth-1 ; i++)

{

// Inner loop for check and pass

for (int j = i+1; i<num.length;i++)

{

//Check and Swap

if(num[i] > num[j])

{

//Do a swap

temp = a[[i];

a[i] = a[j];

a[j] = temp;

}

}

}

Implementation in C#

using System;

namespace SelectionSort
{
    class Program
    {
        static int [] num = {8,6,5,7,1,2,3};
        static int swapcount = 0;
        static int swapcheck = 0;
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            SelectionSort();
            PrintSortedItems();
        }

        static void SelectionSort()
        {
         
           //Outer loop for number of passes till n-2 th item in the array
            for (int i = 0; i < num.Length-1; i++)
            {
                   int minIndex = i;
                   int passcount = i+1;
                
                Console.WriteLine("This is pass number ----->"+passcount);

                //Inner loop for checking to perform a swap
                for (int j = i+1; j < num.Length; j++)
                {
                    swapcheck = swapcheck+1;
                    Console.WriteLine("  This check for swap -->"+swapcheck);
                    if (num[i]>num[j])
                    {
                        swapcount=swapcount+1;
                        int temp;
                        temp = num[i];
                        num[i] = num[j];
                        num[j] = temp;

                        Console.WriteLine("         This is swap count------->"+swapcount);

                        //minIndex = j;

                    }

                }
                
            }
        }

        static void PrintSortedItems()
        {
            for (int i = 0; i < num.Length; i++)
            {
                Console.WriteLine(num[i]);
            }
        }
    }
}

The complete .NET core project is available in this Github repository https://github.com/sundarnarasiman/SortingAlgorithms

Execution and Results

This is pass number —–>1
This check for swap –>1
This is swap count——->1
This check for swap –>2
This is swap count——->2
This check for swap –>3
This check for swap –>4
This is swap count——->3
This check for swap –>5
This check for swap –>6

This is pass number —–>2
This check for swap –>7
This is swap count——->4
This check for swap –>8
This check for swap –>9
This is swap count——->5
This check for swap –>10
This is swap count——->6
This check for swap –>11

This is pass number —–>3
This check for swap –>12
This is swap count——->7
This check for swap –>13
This is swap count——->8
This check for swap –>14
This is swap count——->9
This check for swap –>15
This is swap count——->10

‘
This is pass number —–>4
This check for swap –>16
This is swap count——->11
This check for swap –>17
This is swap count——->12
This check for swap –>18
This is swap count——->13

This is pass number —–>5
This check for swap –>19
This is swap count——->14
This check for swap –>20
This is swap count——->15

This is pass number —–>6
This check for swap –>21
This is swap count——->16

Printing sorted array
1
2
3
5
6
7
8

Summary

For sorting 7 items, it took 6 passes, 21 checks for swaps and 16 actual swaps. Again, the number of swaps and swap checks are completely dependent on how the elements are arranged in the array. This is not the best performing sorting algorithm. This has the worst case complexity of O(n^2).

Bubble Sort is one of the simplest Sort Algorithms to implement, at the same time it’s not the most efficient.

Overview

We try to compare ‘i’ the element and ‘i+1’ the element in the array of numbers to be sorted. If ‘i’ th element is greater than ‘i+1″, we swap the position of these two numbers in the array. We keep on going next in the array and complete the check and swapping unitil ‘n-1’ and ‘n’ the element. This complete round is called a pass. We try do up to n-1 passes (check and swap) until all the numbers are sorted. This is for sorting in ascending order.

Pseudocode

// Outer loop for n-1 passes

static int [] num = {numbers to be sorted}

For (int k=0;k<n-1);k++)

{

for (int i=0;i<n-k-1;i)

{

if (num[i] > num [i+1])

{

Do a swap

}

}

}

n – size of the array (num.length)

Implementation in C#

The complete code is C# is below.

using System;

namespace BubbleSort
{
    class Program
    {
         static int [] num = {7,6,5,4,3,2,1};
         static int swapcount = 0;
        static void Main(string[] args)
        {
           
            // Total number of passes for swap it is 0 to arr.length-1
           for (int k=0;k<num.Length-1;k++)
           {
               int passcount = k+1;
                Console.WriteLine("This is "+"pass number-----> "+passcount);
                PassAndSwap(num,k);
            }
          // PrintSortedArray(num);
            Console.WriteLine("Hello World!");
        }



        public static void PassAndSwap(int [] input, int pass)
        {
            // Total number of swaps = 0 to arr.length-swap_iteration-1
            for (int i=0; i<input.Length-pass-1;i++)
            {
                

                if (input[i] > input[i+1])
                {
                    swapcount = swapcount+1;
                Console.WriteLine("     This is "+ "swap number ---> "+ swapcount);
                    int temp;
                    temp = input[i];
                    input[i]=input[i+1];
                    input[i+1]=temp;
                   
                }
            }
            PrintSortedArray(num);

        }

       
           
        

        public static void PrintSortedArray(int [] Sorted)
        {
            
            for (int j = 0 ;j<Sorted.Length;j++)
            {
                Console.Write(Sorted[j]+",");
               
            }
             Console.WriteLine("\n");

        }
    }
}

The link for Github repo is https://github.com/sundarnarasiman/SortingAlgorithms/tree/main/BubbleSort

Execution and Output

When we execute the above code we’ll get this output below. For sorting 7 (n) numbers, we can clearly see that this is doing 6 (n-1 passes.

This is pass number—–> 1
This is swap number —> 1
This is swap number —> 2
This is swap number —> 3
This is swap number —> 4
This is swap number —> 5
This is swap number —> 6
6,5,4,3,2,1,7,

This is pass number—–> 2
This is swap number —> 7
This is swap number —> 8
This is swap number —> 9
This is swap number —> 10
This is swap number —> 11
5,4,3,2,1,6,7,

This is pass number—–> 3
This is swap number —> 12
This is swap number —> 13
This is swap number —> 14
This is swap number —> 15
4,3,2,1,5,6,7,

This is pass number—–> 4
This is swap number —> 16
This is swap number —> 17
This is swap number —> 18
3,2,1,4,5,6,7,

This is pass number—–> 5
This is swap number —> 19
This is swap number —> 20
2,1,3,4,5,6,7,

This is pass number—–> 6
This is swap number —> 21
1,2,3,4,5,6,7,

The number of swaps depends on how these numbers are arranged in the array.

Time Complexity

When it comes to time complexity, this is not the best performing sorting algorithm. The time complexity in worst case is O(n^2). We’ll see another sorting algorithm in another post.

I have recently set up Windows Subsystem for Linux (WSL2) on my Windows 10 laptop and installed Ubuntu 20.04 LTS. When i tried ‘apt update’ on Ubuntu distro, it failed with following error messages.

> sudo apt-get update
Err:1 http://security.ubuntu.com/ubuntu bionic-security InRelease
  Temporary failure resolving 'security.ubuntu.com'
Err:2 http://archive.ubuntu.com/ubuntu bionic InRelease
  Temporary failure resolving 'archive.ubuntu.com'
Err:3 http://archive.ubuntu.com/ubuntu bionic-updates InRelease
  Temporary failure resolving 'archive.ubuntu.com'
Err:4 http://archive.ubuntu.com/ubuntu bionic-backports InRelease
  Temporary failure resolving 'archive.ubuntu.com'

I did the following to get it working.

Step #1.

On the Ubuntu distro, create a file at this location /etc/wsl.conf.

The file should have the following configuration.

[network]
generateResolvConf = false

If we don’t set this file, WSL will automatically load a default /etc/resolv.conf with default namesever configuration.

Shut down and restart the distro.

Step #2

Delete the default /etc/resolv.conf file.

sudo rm /etc/resolv.conf

Create a new /etc/resolv.conf with the following entry.

nameserver 8.8.8.8

Now, restart the WSL2 and open the distro again. The apt update on WSL2 should work like a charm.

Nowadays, Docker is the most widely used container runtime for building and running containerized applications/micro-services. The Docker Desktop for Windows is a compelling package that comes with Docker Engine, Docker CLI client, Docker Compose, Notary, Kubernetes and CredentialHelper. In Windows 10, you can install Docker Desktop for Windows and run containers in two modes – Windows Containers mode and Linux Container mode.

I followed the steps in this article to get going. There are two options for setting up Docker on Windows – one using WSL2 back-end and other using hyper-v backend.

In this post, i’m leveraging WSL2 back-end. For leveraging WSL2 backend, Linux kernel update package needs to be installed. Download and run the Docker Desktop install after meeting all the pre-requisistes in the above mentioned article. For setting up WSL2 on Windows 10, you can refer my other blog post.

After successful installation of Docker Desktop for Windows, Log out and Log in back.

The Docker is started automated.

Now I can pull a container image from Powershell terminal.

I can also run the same image from WSL2 terminal.

Thus WSL2 provides seamless integration with Windows 10.