Bubble Sort is the most simple form of sorting algorithm that works by repeatedly stepping through the list of items (array) and swapping the adjacent elements if they are in incorrect order. This algorithm has no such real life uses due to it’s poor performance and is used primarily as an educational tool.

Worst and Average Case Time Complexity: O(n2)
Best Case Time Complexity: O(n)

Heap Sort

Heap sort is a in-place comparison based sorting algorithm based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

Best, Worst and Average Case Time Complexity: n*log(n)

Selection Sort

Selection sort is a simple in-place comparison sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. This is an inefficient sorting technique on large lists (array), and generally performs worse than the similar sorting algorithms.

Best, Worst and Average Case Time Complexity: n^2

Insertion Sort

Insertion sort is a simple in-place comparison-based sorting algorithm. It builds the final sorted array one item at a time. This is an inefficient sorting technique on large lists (arrays), and generally performs worse than the similar sorting algorithms. Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

Average and Worst Case Time Complexity: n^2
Best Case Time Complexity: n

Quick Sort

Quick sort is an highly efficient divide and conquer sorting algorithm. It is based on partitioning of array of data into smaller arrays. Developed in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heap sort. The name comes from the fact that, quick sort is capable of sorting a list of data elements significantly faster than any of the common sorting algorithms.

Average and Best Case Time Complexity: n*log(n)
Worst Case Time Complexity: n^2

Merge Sort

Merge sort is an efficient comparison based divide and conquer algorithm. It is a general purpose algorithm based on the idea of breaking down a list (array) into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list.

Average, Worst and Best Case Time Complexity: n*log(n)

Shell Sort

Shell Sort Algorithm is an in place comparison sort. It can be seen as either a generalization of sorting by exchange or sorting by insertion. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.

Average complexity: n*log(n)^2 or n^(3/2)
Best Complexity: n

C++ Implementation of different Sorting Algorithms

# include <iostream.h>
# include <conio.h>
# include <iomanip.h>
#include <stdlib.h>
#include <graphics.h>
#include <stdio.h>
#include <dos.h>

// Function related to sorting in class sorting
class  sorting
{
		int  array[50],array1[50],final[100],i,n,m,j;
	public:
		// Function to read an array
		void read();

		// Function to read arrays for merge sort
		void read_mer();

		// Function to display an array
		void display();

		// Function to perform bubble sort
		void bub_sort();

		// Function to perform selection sort
		void Sel_sort();

		// Function to perform insertion sort
		void Ins_sort();

		// Function to perform quick sort
		void Qui_sort();

		// Function to perform heap sort
		void Heap_sort();

		// Function to build a heap
		void heap(int array[], int n);

		// Function to interchange the value of root node with a
		// child node in heap sort
		void below_heap(int array[], int first, int last);

		// Function to perform merges sort
		void Mer_sort();

		// Function to perform shell sort
		void Shell_sort();

		// Function to split the array into two halves during quick sort
		void partition(int array[], int  beg, int end, int *loc);

		// Function to called recursively partition itself
		void quick_sort(int array[], int n, int l, int u);

		// Function to draw a box at front screen
		void box(int x1, int y1, int x2, int y2);
};

// Function to draw box at the time of menu display

void sorting::box(int x1, int y1, int x2, int y2)
{
	for (int col = x1; col < x2; col++)
	{
		gotoxy(col, y1);
		cprintf("%c", 196);
		gotoxy(col, y2);
		cprintf("%c", 196);
	}

	for (int row = y1; row < y2; row++)
	{
		gotoxy(x1, row);
		cprintf("%c", 179);
		gotoxy(x2, row);
		cprintf("%c", 179);
	}

	gotoxy(x1, y1);
	cprintf("%c", 218);
	gotoxy(x1, y2);
	cprintf("%c", 192);
	gotoxy(x2, y1);
	cprintf("%c", 191);
	gotoxy(x2, y2);
	cprintf("%c", 217);
}

// This function is used to read the values in an array having n elements

void sorting::read()
{
	int row = 7;
	box(2, 1, 75, 24);
	gotoxy(24, 2);
	cout << "Enter how many elemnets =  ";
	cin >> n;
	gotoxy(13, 4);
	cout << " Input array ";
	gotoxy(12, 5);
	cout<<"****************";
	for (i = 0; i < n; i++)
	{
		gotoxy(10, row);
		cout << " Enter " << (i+1) << " element = ";
		gotoxy(30, row);
		cin >> array[i];
		row++;
	}
}

/* Function to read arrays for merge sort. */
void sorting::read_mer()
{
	int row = 8;

	box(2, 1, 75, 24);


	gotoxy(20, 2);
	cout << "Enter elements in First Array  =  ";
	cin >> n;
	gotoxy(20, 3);
	cout << "Enter elemnets in second Array =  ";
	cin >> m;
	gotoxy(24, 22);
	cout << "Note:- Please enter sorted data \n";

	gotoxy(17, 5);
	cout<<"---------------------------------------";
	gotoxy(6, 6);
	cout << " IST Array";
	gotoxy(5, 7);
	cout << "************";
	for (i = 0; i < n; i++)
	{
		gotoxy(6, row);
		cout << (i+1) << " element = ";
		gotoxy(18, row);
		cin >> array[i];
		row++;
	}

	row = 8;

	gotoxy(25, 6);
	cout << " IIND Array";
	gotoxy(24, 7);
	cout << "*************";
	for (i = 0; i < m; i++)
	{
		gotoxy(25, row);
		cout <<  (i+1) << " element = ";
		gotoxy(39, row);
		cin >> array1[i];
		row++;
	}
}

// This function is used to display the sorted elements
// from every sorting technique.
void sorting::display()
{
	int row =7;

//	box(2, 1, 75, 24);

	gotoxy(50, 4);
	cout << "  Sorted array  \n";

	gotoxy(49, 5);
	cout << "******************";

	for (i = 0; i < n; i++)
	{
		gotoxy(50, row);
		cout << (i+1) << " Element is = ";
		gotoxy(65, row);
		cout << array[i];
		row++;
	}
}

// This is the method of sorting by which the array element
// are interchanged within its relative values
void sorting::bub_sort()
{
	int temp, j;
	// Reads the array elements
	read();

	for (i = 0; i < n - 1; i++)
	{
		for (j = i+1; j < n; j++)
		{
			if (array[i] > array[j])
			{

				temp = array[i];
				array[i] = array[j];
				array[j] = temp;

			}
		}
	}

	gotoxy(25, 18);
	textbackground(MAGENTA);
	textcolor(5+143);
	cprintf(" RESULT OF BUBBLE SORT ");
	textbackground(BLACK);
	textcolor(2);

	// Displays the arrays elements
	display();
	getch();
}

// This function is used to perform the quick sort
void sorting::Qui_sort()
{
	// Inputs the array elements for quick sort
	read();

	// For quick sort
	quick_sort(array, n, 0, n-1);

	gotoxy(25, 18);
	textbackground(MAGENTA);
	textcolor(5+143);
	cprintf(" RESULT OF QUICK SORT ");
	textbackground(BLACK);
	textcolor(2);

	// Displays the sorted elements using the display() function
	display();

	getch();
}

// This function performs the partition changing in the array
// by the quick sort method
void sorting::quick_sort(int array[], int n, int l, int u)
{
	int loc;

	if (l < u)
	{

		partition(array, l, u, &loc);
		quick_sort(array, n, l, loc-1);
		quick_sort(array, n, loc+1, u);

	}
}

// Function to perfrom the partition in the array for quick sort

void sorting::partition(int array[], int  beg, int end, int *loc)
{
	int first, last, flag, temp;

	*loc = first = beg;

	last = end;
	flag = 0;

	while (!flag)
	{
		while (array[last] >= array[*loc] && (*loc != last))
			last --;

		if (*loc == last)
			flag = 1;
		else
		{

			if (array[*loc] > array[last])
			{

				temp = array[*loc];
				array[*loc] = array[last];
				array[last] = temp;
				*loc = last;

			}
		}

		if (!flag)
		{

			while ((array[first] <= array[*loc]) && (*loc != first))
				first++;

			if (*loc == first)
				flag = 1;
			else
			{
				if (array[*loc] <array[first])
				{

					temp = array[*loc];
					array[*loc] = array[first];
					array[first] = temp;
					*loc = first;

				}
			}
		}
	}
}

// Function is used to perform the heap sort technique
void sorting::Heap_sort()
{
	// Reads the elements in array
	read();

	int temp;

	heap(array, n);

	for (i = n-1; i > 0; i--)
	{
		temp = array[0];
		array[0] = array[i];
		array[i] = temp;
		below_heap(array, 0, i-1);
	}

	gotoxy(28, 18);
	textbackground(MAGENTA);
	textcolor(5+143);
	cprintf(" RESULT OF HEAP SORT ");
	textbackground(BLACK);
	textcolor(2);

	// Displays the elemnts
	display();
	getch();
}

// Function which create a heap for heap sort
void sorting::heap(int array[], int n)
{
	int counter;

	// Bitwise right shift
	counter = (n-1) >> 1;

	for (i = counter; i >= 0; i--)
		below_heap(array, i, n-1);
}

// Function is used to create lower heap in array for heap sort
void sorting::below_heap(int array[], int first, int last)
{
	int count, l_child, r_child, max, temp;

	if (first == 0)
		l_child = 1;
	else
		// Bitwise left shift
		l_child = first << 1;

	r_child = l_child + 1;

	if (l_child <= last)
	{
		max = array[l_child];
		count = l_child;
		if (r_child <= last)
		{
			if (array[r_child] > max)
			{
				max = array[r_child];
				count = r_child;
			}
		}

		if (array[first] < array[count])
		{
			temp = array[first];
			array[first] = array[count];
			array[count] = temp;
			below_heap(array, count, last);
		}
	}
}

// Function is used to make selection sort in an array
void sorting::Sel_sort()
{
	// Reads the array elements for selection sort
	read();

	int small;
	int pos;

	for (i = 0; i < n-1; i++)
	{
		small= array[i];
		pos = i;

		for(int j = i+1 ; j < n; j++)
		{

			if (array[j] < small)
			{
				small = array[j];
				pos = j;
			}
		}

		if ( pos != i)
		{
			int temp = array[i];
			array[i] = array[pos];
			array[pos] = temp;
		}
	}

	gotoxy(28, 18);
	textbackground(MAGENTA);
	textcolor(5+143);
	cprintf(" RESULT OF SELECTION SORT ");
	textbackground(BLACK);
	textcolor(2);

	// Displays the sorted elements
	display();
	getch();
}

// Function is used to perform the shell sort in an array
void sorting::Shell_sort()
{
	// Reads the elements for shell sort
	read();

	int temp;
	for (int inc = n/2; inc>0; inc /= 2)

	for (int i = inc; i < n; i++)
	{

		temp = array[i];
		for (int j = i;j >= inc && temp < array[j-inc]; j -= inc)
			array[j] = array[j-inc];
		array[j] = temp;
	}

	gotoxy(20, 18);
	textbackground(MAGENTA);
	textcolor(5+143);
	cprintf(" RESULT OF SHELL SORT");
	textbackground(BLACK);
	textcolor(2);

	// displays the sorted elements
	display();
	getch();
}

// Function is used to perform insertion sort
void sorting::Ins_sort()
{
	int temp;

	read();

	for (int i = 1; i < n; i++)
	{
		temp = array[i];
		for (int j = i; temp < array[j-1]; j--)
			array[j] = array[j-1];
		array[j] = temp;
	}

	gotoxy(28, 18);
	textbackground(MAGENTA);
	textcolor(5+143);
	cprintf(" RESULT OF INSERTION SORT ");
	textbackground(BLACK);
	textcolor(2);

	// Displays the sorted elements
	display();
	getch();
}

// Function is used to perfrom merge sort in two arrays
void sorting::Mer_sort()
{
	int row = 8;
	// Reads the elements in different arrays
	read_mer();

	i = j = 0;
	int k = 0;

	while ((i < n) && (j < m))
	{

		if (array[i] < array1[j])
		{

			final[k] = array[i];
			k = k + 1;
			i = i + 1;

		}
		else
		{

			final[k] = array1[j];
			k = k + 1;
			j = j + 1;

		}
	}

	while (i < n)
	{
		final[k] = array[i];
		k = k + 1;
		i = i + 1;
	}

	while (j < m)
	{
		final[k] = array1[j];
		k = k + 1;
		j = j + 1;
	}

	gotoxy(28, 18);
	textbackground(MAGENTA);
	textcolor(5+143);
	cprintf(" RESULT OF MERGE SORT");
	textbackground(BLACK);
	textcolor(2);
	gotoxy(50, 6);
	cout << " Sorted array  \n";
	gotoxy(49, 7);
	cout << "******************";
	int t = m + n;

	for (i = 0; i < t; i++)
	{
		gotoxy(50, row);
		cout << (i+1) << " Element is = ";
		gotoxy(65, row);
		cout << final[i];
		row++;
	}
	getch();

}

typedef char option[15];

char menu();

void grap_screen();
void end();

// MAIN PROGRAM
void main()
{

	char choice;
	sorting  sort;
	// To display the first screen of sort techniques
//	grap_screen();

	do
	{
		choice = menu();

		clrscr();
		switch (choice)
		{
			case '1':

				sort.bub_sort();
				break;

			case '2':

				sort.Heap_sort();
				break;

			case '3':

				sort.Sel_sort();
				break;

			case '4':

				sort.Ins_sort();
				break;

			case '5':

				sort.Qui_sort();
				break;

			case '6':

				sort.Mer_sort();
				break;

			case '7':

				sort.Shell_sort();
				break;

			default :
				end();
				exit(0);

		}
	} while (choice != 0);

}

// Function used to do screening
void normalvideo(int x, int y, char *str)
{
   gotoxy(x, y);
   cprintf("%s", str);
}

// Function to reverse the video
void reversevideo(int x, int y, char *str)
{
	 textcolor(RED);
	 textbackground(WHITE);

	 gotoxy(x, y);
	 cprintf("%s", str);
	 textcolor(GREEN);
	 textbackground(BLACK);
}

// Function to display the main menu

char menu()
{
	clrscr();
	int i, done;

	sorting sort;

	option a[]=
			{
				" Bubble-Sort",
				"  Heap-sort ",
				"Selection-Sort",
				"Insertion-Sort",
				"  Quick-sort",
				"  Merge-sort",
				"  Shell_sort",
				"     Quit   "
			};

	clrscr();
	sort.box(20, 6, 65, 20);
	sort.box(18, 4, 67, 22);
	textcolor(5+143);
	gotoxy(30, 5);
	textbackground(WHITE);
	cprintf("S O R T I N G  -  M E N U");
	textbackground(BLACK);
	textcolor(22);

	for (i = 1; i < 8; i++)
		normalvideo(32, i+8, a[i]);

	reversevideo(32, 8, a[0]);
	reversevideo(32, 8, a[0]);

	i = done = 0;
	_setcursortype(_NOCURSOR);

	do
	{
		int key = getch();

		switch (key)
		{
			case 00:

				key = getch();

				switch (key)
				{
					case 72:

						normalvideo(32, i+8, a[i]);
						i--;
						if (i == -1)
							i = 7;

						reversevideo(32, i+8, a[i]);
						break;

					case 80:

						normalvideo(32, i+8, a[i]);
						i++;

						if (i == 8)
							i = 0;

						reversevideo(32, i+8, a[i]);
						break;
				}
				break;

			case 13:
				 done = 1;
		}
	} while (!done);

	_setcursortype(_NOCURSOR);
	return(i+49);
}

// Function to display the front screen of sorting technique
void grap_screen()
{
	int driver,mode;
	driver = DETECT;

	initgraph(&driver, &mode,"c:\tc\big");
	setbkcolor(10);
	setcolor(5); //set the text color

	//set default font,horizontal direction,size of text
	settextstyle(0, 0, 7);
	outtextxy(50, 100, "Sorting");
	outtextxy(50, 300, "Techniques");

	delay(2000);
	closegraph();

	initgraph(&driver, &mode, "c:\tc\big");
	setbkcolor(10);

	setcolor(1); //set background color to blude
	settextstyle(0, 0, 7);

	outtextxy(50, 100, "DEVELOPED");
	outtextxy(50, 300, "   BY ");

	delay(2000);
	closegraph();

	initgraph(&driver, &mode, "c:\tc\bin");
	setbkcolor(10);

	setcolor(4); //set background color to green
	settextstyle(0, 0, 5);

	outtextxy(30, 100, "Author " );
	outtextxy(120, 200, "     & ");
	outtextxy(200, 300, "Her Team");

	delay(2000);
	closegraph();
}
 //FUNCTION FOR ANIMATED END.
void end()
{
	textmode(1);

	for(int ai=0,aj=0, ak=34,al=33;ai<10,aj<17,ak>10,al>17;ai++,aj++,ak--,al--)
	{
		clrscr();

		gotoxy(ai-1, 8);
		textbackground(4);
		textcolor(15);
		cout << "   Thanks   ";

		gotoxy(aj, 16);
		cout << "   This";

		gotoxy(ak-4, 12);
		cout << " For using";

		gotoxy(al-2, 20);
		cout << " Project";
		delay(50);
	  }
										  //end of for loop
	  gotoxy(9, 9);
	  cout << " **********************";

	  gotoxy(9, 13);
	  cout << " **********************";

	  gotoxy(9, 17);
	  cout << " **********************";
	  gotoxy(12, 21);
	  cout << " ***************";
	  delay(2000);

	  textmode(2);
	  textbackground(0);
	  textcolor(5);
}     // end of function