# Sorting Algorithms

# Bubble Sort

**Bubble Sort** — Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements “bubble” to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort.

Get the code on my github below:

`/*`

This program sorts an array of elements using the bubble sort algorithm

By: randerson112358

Output:

Enter total number(s) of elements: 4

Enter the 4 elements: 1 5 4 3

After Sorting: 1 3 4 5

*/

#include <stdio.h>

int BubbleSort(int size, int *array);

int main(void){

int size, i, array[20];

printf("Enter total number(s) of elements: ");

scanf("%d", &size);

printf("Enter the %d elements: ", size);

for(i=0; i<size; i++){

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

}

//Run the Bubble Sort Algorithm to sort the list of elements

BubbleSort(size, array);

printf("After Sorting: ");

for(i=0; i<size; i++){

printf(" %d", array[i]);

}

printf("\n");

system("pause"); // uncomment if you are not using Windows OS

return 0;

}

int BubbleSort(int size, int *array){

int i, j, temp;

//Bubble sorting algorthm

for(i=size-2; i>= 0; i--){

for(j=0; j<=i; j++){

//Swap

if(array[j] > array[j+1]){

temp = array[j];

array[j] = array[j+1];

array[j+1]= temp;

}

}

}

return 1;

}

# Heap Sort

**Heap Sort**- heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime.

The heapsort algorithm involves preparing the list by first turning it into a max heap. The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap. This repeats until the range of considered values is one value in length.

**The steps are:**

1) Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in O(n) operations.

2)Swap the first element of the list with the final element. Decrease the considered range of the list by one.

3)Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap.

4)Go to step (2) unless the considered range of the list is one element

# Insertion Sort

**Insertion Sort**-Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

1) Simple implementation: Bentley shows a three-line C version, and a five-line optimized version.

2) Efficient for (quite) small data sets, much like other quadratic sorting algorithms

3) More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort

4) Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position

5) Stable; i.e., does not change the relative order of elements with equal keys

6) In-place; i.e., only requires a constant amount O(1) of additional memory space

7) Online; i.e., can sort a list as it receives itÂ

When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort.

The most common variant of insertion sort, which operates on arrays, can be described as follows:

1) Suppose there exists a function called Insert designed to insert a value into a sorted sequence at the beginning of an array. It operates by beginning at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. The function has the side effect of overwriting the value stored immediately after the sorted sequence in the array.

2)To perform an insertion sort, begin at the left-most element of the array and invoke Insert to insert each element encountered into its correct position. The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined. Each insertion overwrites a single value: the value being inserted.

/*

This program sorts an array of elements using the insertion sort algorithm

By:randerson112358

Output:

Enter total elements: 3

Enter 3 elements: 9 4 8

After Sorting: 4 8 9

*/#include < stdio.h >int insertionSort(int size, int *array);int main(){

int size, i , array[21];

printf("Enter total number of elements: ");

scanf("%d", &size);

printf("Enter %d elements: ", size);

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

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

//Start sorting the array using the insertion sort algorithm

insertionSort(size, array);

printf("After Sorting: ");

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

printf(" %d", array[i]);

printf("\n");

system("pause"); //Comment this our if you are not using a Windows OS

return 0;

}int insertionSort(int size, int *array){

int i, j;

int temp;

//Insertion Sort

for(i=1; i < size; i++){

temp=array[i];

j= i-1;

while( (temp < array[j]) && (j >= 0)){

//swap

array[j+1] = array[j];

j= j-1;

}

array[j+1] = temp;

}

return 1;

}

# Selection Sort

**Selection Sort** — selection sort is a sorting algorithm, specifically an in-place comparison sort. The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Get the code for selection sort from my github below:

`/*`

This program sorts an array of elements using the selection sort algorithm

By:randerson112358

Output:

Enter the total number of elements: 5

Enter 5 elements: 5 6 1 20 7

The array after sorting is: 1 5 6 7 20

How it works:

5 6 1 20 7

1 6 5 20 7 (min = 1, swapped with 5)

1 5 6 20 7 (min = 5, swapped with 6)

1 5 6 20 7 (min =6, no swapping needed)

1 5 6 7 20 (min = 7, swapped with 20)

1 5 6 7 20 (min=20, we have reached the end of the list)

*/

#include<stdio.h>

int SelectionSort(int size, int *a);

int main(){

int size, i, array[21];

printf("Enter the total number of elements: ");

scanf("%d", &size);

printf("Enter %d elements: ", size);

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

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

//Sort the array using the selection sort algorithm

SelectionSort(size, array);

printf("The array after sorting is: ");

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

printf(" %d", array[i]);

return 0;

}

int SelectionSort(int size, int *a){

/* a[0] to a[n-1] is the array to sort */

int i,j;

int n;

/* advance the position through the entire array */

/* (could do j < n-1 because single element is also min element) */

for (j = 0; j < size-1; j++)

{

/* find the min element in the unsorted a[j .. n-1] */

/* assume the min is the first element */

int iMin = j;

/* test against elements after j to find the smallest */

for (i = j+1; i < size; i++) {

/* if this element is less, then it is the new minimum */

if (a[i] < a[iMin]) {

/* found new minimum; remember its index */

iMin = i;

}

}

if(iMin != j)

{

//swap(a[j], a[iMin]);

int temp = a[j];

a[j] = a[iMin];

a[iMin] = temp;

}

}

return 1;

}

# Merge Sort

**Merge Sort** — Merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Conceptually, a merge sort works as follows:

1)Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

2)Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

# Check Out the following for more content / videos on Algorithms and Algorithm Analysis:

# YouTube Channel:

https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

# Computer Science Website:

http://everythingcomputerscience.com/

# Udemy Videos on Recurrence Relation:

https://www.udemy.com/recurrence-relation-made-easy/

**Video Tutorial on Algorithm Analysis:**

https://www.udemy.com/algorithm-analysis/

**Twitter:**

https://twitter.com/CsEverything