Question

If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many different sorting algorithms? Your task is to investigate these and other questions in relation to the algorithms selection sort, insertion sort, merge sort, and quicksort.

Write a set of guidelines for each algorithm to help someone decide which one would be most appropriate for a particular situation. Include in your guidelines a description of the advantages and disadvantages, together with an indication as to why those characteristics apply, and an explanation of the running cost (in Big-O notation). Your goal is to provide enough information so that someone unfamiliar with the inner workings of each algorithm would be able to decide which one is right for them.

For example, if someone was considering using counting sort to sort a collection of values then the following brief information could help them decide if it was appropriate or not.

Algorithm	Counting Sort
Description	Count the number of times each different value appears, then overwrite the values in lowest-to-highest order, with each value repeated according to the counts.
Advantages	Usually faster than any of the comparison-based sorts. • Algorithmic complexity is O(n + k), irrespective of the data order, where n is the list length and k is the number of distinct values that might occur. Typical case is where k is much less than n, in which case the cost is O(n). • Simple to code
Disadvantages	• Only usable where the values to be sorted can be used to index an array of value counts, which usually means the values are integers over a small range. In other words, the algorithm cannot be used to sort common non-integral values such as strings and floats, and it is inappropriate even for integers if the range of values is large. • Requires an auxiliary array (to store the counts) of size equal to the number of different possible sort values. If the range of values is large, the cost of allocating and maintaining this array could be significant.
When to use…	If your circumstances allow, it is hard to beat this algorithm, but because it places very tight restrictions on the nature of the data to sort, you will often have to choose another approach.

           

Answer 1

Algorithm: Selection Sort

Description: Comparison-based sorting techniques which maintains two arrays – a sorted list and unsorted list. In every iteration the smallest element from the unsorted list is selected and placed in sorted array rightmost corner ( in ascending order soring ). Time complexity = O(n^2)

Advantages:

• Less number of Writes than Reads(comparison)
• Simple and easy implementaion
• Initial arrangement of elements does not matter.
• Works well on small list
• No additional storage required

Disadvantages:

• Not efficient with large sorting list
• O(n^2) time complexity makes it worse sorting technique compared to another sorting algorithms

When to use: selection sort is used If the sorting list is small, when the memory space is limited or when the array is almost sorted already

Algorithm: Insertion Sort

Description: Sorting List is virtually divided into a sorted and unsorted array. Each value from unsorted list is picked and compare with all the elements in the sorted part and placed on the right position in the unsorted part. Time Complexity – O(n)

Advantages:

• Complete sorting will be completed in one iteration.
• Simple
• Minimum space requirement
• Less space required as it is a in-place sorting algorithm
• More efficient than selection sort with O(n) time complexity

Disadvantages:

• Less performance/advance compared to other sorting algorithms
• Cannot handle big list of elements

When to use : This algorithm can be used when array of elements is less or when the list is already almost sorted.

Algorithm: Merge Sort

Description: Its a divide and conquer sorting technique. It divides the array into two halves, again those gets divided to halves and repeat till the subarray size is 1. Later when the divided smaller halves are sorted, they are merged together to form the complete sorted list.

Time Complexity – O(n log(n))

Eg: 68435972

Divided in to : 6843    5972

Further divided in to halves :    68 43 59 72

Now sort the subarray of size 1 :   68 34 59 27

Now merge the first halves : 3468   2579

Merging the complete array : 23456789

Advantages:

• Is applicable to any file size.
• It does not go through the list again and again
• Stable sort
• Guarenteed to run in O(n(log(n))

Disadvantages:

• Slower compared to other algorithms
• Extra memory space is required as the it need to store the subarrays too.

When to use:

• Merge sort is used when we have a large date list to sort.
• When we need a more efficient sorting and have a larger memory space.
• When we need a guaranteed running time of O(n Log(n))

Algorithm: Quick Sort :

Description:: It is a divide and conquer algorithm where it picks an pivot element first. Pivot element can be selected in different methods – Always the first element, Always the last element of array, a random element or the median of the array list. The other elements of the array are divided accordingly to whether they are smaller or greater than the pivot element, these greater the pivot element and smaller than pivot element list becomes a new subarray. The subarrays are been sorted recursively, and then merged to form the complete Sorted list. Time complexity = O(n log(n))

Advantages:

• Considered the best sorting algorithm
• Works well with large list
• High efficient
• Time complexity is O(n log(n))
• In-place sorting – No extra memory is required

Disadvantages :

• Works slow with already sorted list
• Worse case performance is equal to bubble sort algorithm with worst case time complexity of O(n^2)
• Not stable sorting

When to use :

• Besy used when the sorting list is large
• When the memory space is less available
• When the work need to be done faster and efficent