Sorting algorithms are one kind of algorithm whose performan

Sorting algorithms are one kind of algorithm whose performance may depend upon the data. Choose one of the sorting algorithms or any other algorithm and explain whether the there are any differences in the best, average and worst cases. If there are no differences, explain why not. If there are differences, describe the data in the different cases and explain how the performance differs in each case.

Solution

Quick Sort: It is the highly efficient sorting algorithm among all other sortings like merge sort, heap sort,etc. It is based on partitioning of data arrays into sub arrays or smaller arrays. It follows the divide and conquer approach. It performs the partitioning of array calling recursive functions for partitiong into individual sub arrays.

Partitioning in Quick sort:In the data arrays, a pivot element is selected randomly and following steps are performed:

1. Take an array of n elements.

2. Choose the leftmost element of the array as the pivot element.

3. Take two variables i and j to point to the left end and right end respectively.

4.Now while the values of left of pivot is less than pivot, move to the right.

5. While the values of right of pivot is greater than pivot, move to the left.

6. If the steps 4 and 5 don not occur, then swap the particular element with pivot element.

7.This step is repeated recursively untill left<right, i.e. the elements to the left of the pivot are smaller than it and the elements to the right are greater than it. After this the array will be divided into two sub arrays.

The analysis of quick sort in all the three cases:

Worst Case: Time complexity of quick sort partitioning in worst case is O(n²).The recursive call is done for 0 to n-1 times. The worst case happens to occur when the pivot element comes up to be the largest or the smallest element in the array of datas. Thus this is the most unbalaced situation and it takes a lot of time for performing the sorting.

Best Case: Time complexity of quick sort partitioning in best case is O(nlogn) completely and O(n) individualy. The recursive call is done for half the size of array i.e. n/2 times. It is categorized as the best case when the array list is divided into two equal lists, having equal number of elements in both the sub arrays.It is the most balanced situation in the quick sort partitioning.

Average Case: The time complexity of quick sort partitioning in average case is O(nlogn) and the recursive call occurs n times, that is permutation of n elements with equal probability.