Sorting Algorithms:

1-What Is Sorting?

In easy language we can say that sorting algorithms is a method for arranging a large number of objects or we can say items into a specific order, such as line wise, highest to lowest value or shortest to longest distance and as alphabetical wise too.

For example, there is an order of 10 numbers. So sorting algorithms take that numbers as input data, perform specific operations on those order and deliver ordered arrays as output.

2-Why Sorting Data Is Important for Algorithms?

According to me Sorting is one of the most important topics in Data Structure Algorithms (DSA). Sorting information is one of the most common application of computers now a days. Because every people can’t find everything that easily so with the help of sorting algorithms, they can find whatever they want by performing such operations.

Some important points:

• To represent data in more readable form.
• Optimize data searching to high level.
• Sorting can also reduce the complexity of a problem, but how that I’ll will say afterwards.

3-What Does Complexity means in Algorithm and Types of Complexity?

Complexity of an algorithm means how much time or space is required by an algorithm to perform a such function/operation of a given order(n).

There are three types of Complexity.

• Worst case complexity.
• Best case complexity.
• Average case complexity.

Worst case complexity has found to be the best in all cases.

4-Types of Sorting Algorithms

Bubble Sort.

Selection Sort.

Quick Sort.

Insertion Sort.

Merge Sort.

Shell Sort.

Bubble Sort:

*Bubble sort is the simplest sorting algorithm. Bubble sort is based on comparison where each adjacent pair of elements will get compared and will get reciprocated themselves if they are not in order. This process will continue until the last elements got compared.

This algorithm is not good for large data sets. For example, there are six student’s marks [40,50,10,20,90]. And you have to calculate line wise, so the user will apply Bubble sort. And the output you will get is this [10,20,40,50,90]. So, by using bubble sort all the numbers got arranged line wise.

Void BubbleSort(int array[], int z)

{

int i, j, swap;

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

{

for(j = 0; j < z-i-1; j++)

{

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

{

// reciprocate the elements

swap = array[j];

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

array[j+1] = swap;

}

}

}

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

*Selection Sort:

This algorithm is called selection sort because it continuously selects the next smallest element and reciprocate it into place. Selection sort is a simple sorting algorithm. In selection algorithm list are divided into two parts, sorted list at the left end and the unsorted list at the right end. Initially, the sorted list is empty and the unsorted list is the entire list. This algorithm is not suitable for large data sets.

Step 1: Set MIN to location 0

Step 2: Search the minimum element in the list

Step 3: Swap with value at location MIN

Step 4: Increment MIN to point to next element

Step 5: Repeat until list is sorted

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

*Quick Sort:

It is an in-place algorithm. Quick sort creates two empty arrays to hold elements. One arrays will contain the elements whose values are lower than the pivot values. And other arrays contain the elements whose value is greater than the pivot values. Pivot is an element that is used to compare and divide the elements of main array into two subarrays. Quick sort is suitable for large data sets. And main thing is that quick sort is faster that other sorting algorithms.

Let us take an example: an array

Algorithm

• Select the highest index value has pivot.
• Take two variables to define left and right.
• Left/Right list defines to the Low/High index.
• While value at left is less than pivot move right.
• While value at right is greater than pivot move left.
• If both step 5 & 6 does not match swap left and right.
• If left >=right, the point they met is new pivot.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

*Insertion Sort:

Insertion sort is a simple sorting algorithm. which built directly the final sorted array but one item at a time. Insertion sort can’t be used for larger data, it is suitable for smaller data. An element which is to inserted in the list has to find its own appropriate location and then it has to be inserted there.

Algorithm

• If there is only one element in the list, that means it is already sorted, so it will return 1.
• Pick up next element & Compare with another element in the sorted sub list.
• Shift all the elements in the sorted sub list that is greater than the value to be sorted.
• Insert another value & repeat until list is sorted.

Let us take an example: An array Z[6]={20,10,30,15,25,5}. We have to sort this array.

void InsertionSorting(int array[], int a)

{

int I , j , sol ;

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

{

j = i;

while (j > 0 & array[j — 1] > array[j])

{

sol = array[j]; array[j] = array[j — 1]; array[j — 1] = sol; j — ;

}

}

}

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

*Merge Sort:

Merge sort in one of the most efficient sorting algorithms. It works on the divide and conquer method. Which means merge sort continuously breaks down itself into sub list until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list.

Algorithm

Step 1: if it is only one element in the list it is already sorted, return.

Step 2: divide the list recursively into sub lists until it can consist of a single element.

Step 3: Then merge all the sub lists together to make a new list.

//Complexity of the procedure is O(n)

while(i<len(z1)&j<len(z2))

{

if(z1[i]<=z2[j]

{

z[k]=z1[i]

i++

}

else{

z[k]=z2=[j]

j++

}

K+

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

*Shell Sort:

Shell sort is the next version of insertion sort. It improves the insertion by comparing elements of several position. This shell sort algorithm helps to sort widely spread elements, first to sort them and then sorts the less widely spaced elements. This spacing is termed as interval. We calculate the intervals using Knuth’s formula h=h*+1 where, h is interval with initial value 1.

Algorithm

Step 1: Initialize the value of h

Step 2: Divide the arrays into small sub lists of equal interval.

Step 3: Sort these sub-lists using insertion sort

Step 4: Repeat until complete list is sorted

//Algorithm for shellsort

ShellSorting(arr, size)

for interval i = size/2 down to 1

for each interval “i” in arr

sort all the elements at interval “i”

end ShellSorting

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

5-WORST CASE TIME COMPLEXITY OF SORTING ALGORITHM.

• Bubble sort = O(n2)
• Selection sort = O(n2)
• Quick sort = O(n2)
• Merge sort = O(n log n)
• Shell sort = O(n)
• Insertion sort = O(n2)

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

6-ADVANTAGE AND DISADVANTAGE OF SORTING ALGORITHMS.

Bubble sort

• Advantage: Simplicity and ease of implementation.
• Disadvantage: Code inefficient

Insertion sort

• Advantage: Relatively simple and easy to implement. Twice faster than bubble sort.
• Disadvantage: Inefficient for large lists

Selection sort

• Advantage: Simple and easy to implement
• Disadvantage: Inefficient for large lists

Quick Sort

• Advantage: Fast and efficient
• Disadvantage: Show messy result if the list is already sorted.

Merge sort

• Advantage: Well suited for large data set.
• Disadvantage: At least twice the memory requirement than other sorts.