Best,Worst and average case comparisions for Sorting algorithms

Below table gives a quick idea of running times, number of comparisions and swaps in various sorting algorithms. For insertion sort rather than swaps they can be considered as moves. Will update the table with linked list, stack and queue operation details.

Algorithm	Best	Worst	Average	Comparisons		Swaps
				Min	Max	Min	Max
Bubble	Ω(n2)	Θ(n2)	Ο(n2)	n(n-)/2	n(n-)/2	0	n(n-)/2
Selection	Ω(n2)	Θ(n2)	Ο(n2)	n(n-)/2	n(n-)/2	0	(n-1)
Insertion	Ω(n)	Θ(n2)	Ο(n2)	n(n-)/2	(n-1)	0	n(n-)/2
Quick	Θ(nlogn)	Θ(nlogn)	Ο(n2)
Merge		Θ(nlogn)

Selection sort

Selection sort is one of the simple sorting techniques. The basic idea behind this technique is, in each iteration the smallest element in the list is picked up and placed in its exact position. This works as follows,

For a list of n items, we have to iterate through the list for n times.

In first iteration consider the n items, scan the list and find the smallest item. Place this item in the first position. (This will be its exact position)

Now in the second iteration, scan the list except the first item  and find the smallest

Item in the list. Place this item in the second position of the list. (This will be its exact position)

Similarly continue for n iterations.

Given below is an example c code that sorts the input list of 5 items in ascending order using selection sort technique.

#include<stdio.h>

void main()

{

int i,a[5],j,small,loc,k;

clrscr();

printf("\nEnter 5 numbers to sort ::\n");

for(i=0;i<5;i++)

scanf("%d",&a[i]);

printf("\nElements before sort : ");

for(i=0;i<5;i++)

printf("%d\t",a[i]);

for(i=0;i<4;i++)

{

small=a[i];

loc=i;

                for(j=i+1;j<5;j++)

                {

                                if(a[j]<small)

                                {

                                small=a[j];

                                loc=j;

                                }

                }

a[loc]=a[i];

a[i]=small;

}

printf("\n\nElements after sort : ");

for(i=0;i<5;i++)

printf("\t%d",a[i]);

getch();

}

Selection sort reduces the total number of swaps when compared to bubble sort. The  worst case running time will be O(n2).

• Minimum number of swaps 0 ( if the list is already sorted)
• Maximum swaps n-1
• Minimum comparisions n(n-1)/2
• Maximum comparisions n(n-1)/2

For comparison of various sorting algorithms click here