Selection Sort

Selection sort is a sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list. 

The smallest element is selected from the unsorted array and swapped with the leftmost element and it becomes part of sorted array. This process continues until all the elements are sorted.

This algorithm is not suitable for large data sets as its average and worst case complexities are of O(n²).

Ex:

14        33        27        10        35        19        42        44

Find the lowest value which is 10 and swap it with 14 which is left most value

10        33        27        14        35        19        42        44

For second position we find 14 is second lowest so it is swapped into second position

10        14        27        33        35        19        42        44

The same process is applied

10        14        19        33        35        27        42        44

 

10        14        19        27        35        33        42        44

 

10        14        19        27        33        35        42        44

Now the list is in sorted order.

Function Code:

void SelectionSort(int A[ ], int n)

{

int i, j;

int minpos, temp;

for(i = 0; i < n − 1; i++)

{

minpos = i;

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

//find the position of min element as minpos from i + 1 to n − 1

{

if(A[j] < A[minpos])

minpos = j;

}

if(minpos != i)

{

temp = A[i];

// swap the i^th element and minpos element

A[i] = A[minpos];

A[minpos] = temp;

}

}

}

Insertion Sort

Insertion sort maintains a sub-list which is always sorted. The array is searched sequentially and unsorted items are moved and inserted into the sorted sub list.

The lower part of an array is maintained to be sorted. An element which is to be inserted in this sorted sub list has to find its appropriate place and then it has to be inserted there.

This algorithm is not suitable for large data sets as its average and worst case complexity are of O(n²).

Ex:

14        33        27        10        35        19        42        44

Insertion sort compares first two elements. Here both are already in ascending order. now 14 is in sorted sub list.

14        33        27        10        35        19        42        44

Insertion sort now compares 33 with 27 and finds 33 is not in correct position. It swaps 33 with 27.

14        27        33        10        35        19        42        44

It also checks all elements in sub list of sorted order. Here sub list is sorted.

Similarly 10 compared with 33

14        27        10        33        35        19        42        44

14        10        27        33        35        19        42        44

10        14        27        33        35        19        42        44

 

comparing 33 and 35, they are in order

10        14        27        33        35        19        42        44

compare 35 with 19, they are not in order, a swap is performed

10        14        27        33        19        35        42        44

Now sublist is sorted

10        14        19        27        33        35        42        44

This process is continued until all unsorted values are placed in the sorted sub list.

 

Insertion sort function code:

void InsertionSort(int A[], int n)

{

int i, j, element;

for(i = 1; i < n; i++)

{

element = A[i];

// insert ith element in 0 to i − 1 array

j = i;

while((j > 0) && (A[j − 1] > element))

//compare if A[j − 1] > element

{

A[j] = A[j − 1]; // shift elements

j = j − 1;

}

A[j] = element; // place element at jth position

}

}

Bubble Sort

Bubble sort is a comparison based algorithm. The bubble sort works by comparing each item in the list with the item next to it and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items

Example:

consider list : 2,9,5,4,1,3

The number of comparisons made at each of the iterations is as follows:

(n - 1) comparisons in the first iteration, (n - 2) comparisons in the second iteration, ... , one comparison in the last iteration. Thus, the total number of comparisons is n(n - 1)/2, which is O(n²).

Hence, the time complexity for each of the cases is given by the following:

1. Average case complexity = O(n²)

2. Best case complexity = O(n²)

3. Worst case complexity = O(n²)

Sorting

Sorting is the operation of arranging the records of a table according to the key value of each record, or it can be defined as the process of converting an unordered set of elements to an ordered set.

Sorting algorithms are divided into two categories: internal and external sorts.

Any sort algorithm that uses main memory exclusively during the sorting is called as an internal sort algorithm.

Any sort algorithm that uses external memory, such as tape or disk, during the sorting is called as an external sort algorithm.

Internal sorting is faster than external sorting.