# Implementation of various Sorting Algorithms in C++

This is a C++ implementation of various sorting algorithms. The list of algorithms include Bubble Sort, Heap Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort and Shell Sort. A brief description of each sorting algorithm is listed below along with their complexity.

## Bubble Sort

Bubble Sort is the most simple form of sorting algorithm that works by repeatedly stepping through the list of items (array of items) 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>
#include <iomanip>
#include <cstdlib>
#include <conio.h>

using namespace std;
// 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

// Function to read arrays for merge sort

// 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

// Function for console graphics
void gotoxy(int x, int y) {
std::cout << "\033[" << y << ";" << x << "H";
}

// Function to draw box at the time of menu display
void drawBox(int x1, int y1, int x2, int y2) {
for (int col = x1; col < x2; col++) {
gotoxy(col, y1);
std::cout << "-";
gotoxy(col, y2);
std::cout << "-";
}

for (int row = y1; row < y2; row++) {
gotoxy(x1, row);
std::cout << "|";
gotoxy(x2, row);
std::cout << "|";
}

gotoxy(x1, y1);
std::cout << "+";
gotoxy(x1, y2);
std::cout << "+";
gotoxy(x2, y1);
std::cout << "+";
gotoxy(x2, y2);
std::cout << "+";
}

// Function to clear the screen
void clrscr() {
#ifdef _WIN32
system("cls");
#else
system("clear");
#endif
}

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

{
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++;
}
}

{
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;

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);
cprintf(" RESULT OF BUBBLE SORT ");

// 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

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

gotoxy(25, 18);
cprintf(" RESULT OF QUICK SORT ");

// 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

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);
cprintf(" RESULT OF HEAP SORT ");

// 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

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

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);
cprintf(" RESULT OF SHELL SORT");

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

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

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);
cprintf(" RESULT OF INSERTION SORT ");

// 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

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);
cprintf(" RESULT OF MERGE SORT");
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[30];

void grap_screen();
void end();

// MAIN PROGRAM
void main()
{

char choice;
sorting  sort;

do
{

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)
{
gotoxy(x, y);
cprintf("%s", str);
}

// Function to display the main menu
{
clrscr();
int i, done;

sorting sort;

option a[] =
{
" Bubble-Sort - Press 1",
"  Heap-sort - Press 2",
"Selection-Sort - Press 3",
"Insertion-Sort - Press 4",
"  Quick-sort - Press 5",
"  Merge-sort - Press 6",
"  Shell_sort - Press 7",
"     Quit   - Press 0"
};

clrscr();
sort.box(20, 6, 65, 20);
sort.box(18, 4, 67, 22);

gotoxy(30, 5);
cprintf("S O R T I N G  -  M E N U");

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;

do
{
int key = getch();

switch (key)
{
case '1':
done = 1;
i = 1;
break;

case '2':
done = 1;
i = 2;
break;

case '3':
done = 1;
i = 3;
break;

case '4':
done = 1;
i = 4;
break;

case '5':
done = 1;
i = 5;
break;

case '6':
done = 1;
i = 6;
break;

case '7':
done = 1;
i = 7;
break;

case '0':
done = 1;
i = 8;
break;
}
} while (!done);

return (i + 48); // Adjusted to return ASCII values
}

//FUNCTION FOR ANIMATED END.
void end()
{
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);
cout << "   Thanks   ";

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

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

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

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

gotoxy(9, 17);
cout << " **********************";
gotoxy(12, 21);
cout << " ***************";
}
M. Saqib: Saqib is Master-level Senior Software Engineer with over 14 years of experience in designing and developing large-scale software and web applications. He has more than eight years experience of leading software development teams. Saqib provides consultancy to develop software systems and web services for Fortune 500 companies. He has hands-on experience in C/C++ Java, JavaScript, PHP and .NET Technologies. Saqib owns and write contents on mycplus.com since 2004.
Related Post