Question

List the worst case and average case Big O for each algorithm below and describe how the algorithm works. You can diagram or write a short paragraph.

• Bubble Sort
• Modified Bubble Sort
• Insertion Sort
• Merge Sort
• Selection Sort
• Shell
• Heap
• Quick

Answer 1

BUBBLE SORT: is a sorting algorithm that iterates through the list and compares all adjacent elements. If the adjacent element is greater it swaps the element and keeps iterating untill the list is sorted. The Average and worst case is : O(n^{​​​​​​2}​​​).

Modified Bubble Sort: Bubble sort compares all the adjacent elements in a list which increases the time complexity. Hence we use modified bubble sort in which we have a flag that is set when an exchange is made after an entire pass over the list.

Insertion Sort: it sorts a given list of array by comparing one element at a time. It is like how we sort a list of card in our hand. We iterate through the list, leaving the sorted list behind. At every position we check the particular element with the sorted list left behind. If the element is larger it leaves it and moves forward. And if it is smaller than it sorts it in the sorted list and finds the perfect position for it. Average case: O(n^{​​​​​​2}​​​) and worst case: O(n^{​​​​​​2}​​​)

Merge Sort: it follows the divide and conquer method. Where we split the array into two halves and sort them individually. After the sorting is done we merge the two arrays and display the sorted list. Average case: O(nlogn) and worst case: O(nlogn)

Selection Sort: it is an algorithm which assumes the first element as the minimum element and compares it with the adjacent one. If it finds the adjacent is the minimum it assigns it as the minimum and keeps on traversing. After each iteration the minimum is placed in the front of the unsorted list. Average case: O(n^{​​​​​​2}​​​) and worst case: O(n^{​​​​​​2}​​​​​).

Shell sort: it is based on selection sort. This algorithm avoids large shifts as in selection sort. We first calculate a particular interval for which we have to compare by using Knuth's formula ( n= n * 3 +1, where n is the interval) . For example we have to sort : {12,31,44,10,51,1,21,55}. We take an interval of 4 so we will compare {12,51} , {31,1} , {44,21} , {10,55}. After the comparison the list will be, {12,1,21,10,51,31,44,55} after this we will apply insertion sort to sort this. Average case depend on the gap and worst case: O(n^{​​​​​​2}​​​)

Heap Sort: is an improved selection sort and a comparison based algorithm. It is based on binary heap data structures. We find the maximum element and place it in the end of the list. In heap sort we divide the array into the sorted and unsorted part and keeps on putting the largest element in the sorted region. Average and worst case: O(nlogn).

Quick Sort: It uses the divide and conquer method and picks an element as the pivot element partitioning the array around the pivot element. You can pick the first or last or random or median as the pivot element. Average Case: O(nlogn) and worst case: O(n^{​​​​​​2}​​​​​).

​​​​​​

​​

​​