For more information CLICK

Bubble Selection Merge Insertion Quick Heap

LEGEND

LEGEND

unsorted element Selection and comparision selection of elements intermediate sorted element

Bubble sort Bubble Sort is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they exist in the wrong order.Large values are always sorted first. It only takes one iteration to detect that a collection is already sorted. The best time complexity for Bubble Sort is Big O of n .The average and worst time complexity is Big O of n square. The space complexity for Bubble Sort is Big O of 1, because only single additional memory space is required. Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration, and places that element at the beginning of the unsorted list.The time complexity of the selection sort is the same in all cases.It is Big O of n square. At every step, you have to find the minimum element and put it in the right place. The minimum element is not known until the end of the array is not reached. Space complexity is Big O of 1 . Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer. Merge sort repeatedly breaks down a list into several sublists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list. merge sort has an average and worst-case performance of Big O of n log n. Space complexity of merge sort is Big O of n. In insertion sort, the array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part. Always the first element in the array is assumed to be sorted. Take the second element and store it separately in key. Compare key with the first element. If the first element is greater than key, then key is placed in front of the first element.This continues until we get a complete sorted list. Worst Case and average case time Complexity is Big O of n square. Best case time complexity is Big O of n. Space complexity is Big O of 1. Quick sort is a divide and conquer algorithm. It divides the list into smaller sub lists and follows the path of recursion to sort them individually. The basic principle in quick sort is the concept of a mean value or middle value in the whole of list. This middle value is known as a Pivot. The idea is to select a middle value or a pivot from the list. Move smaller values than the pivot to its left and larger values to its right. So there would be two lists. One consists of all the values smaller than the pivot. Second consists of all the values equal to and greater to the pivot. Pivot serves as the boundary between these two parts. The running time of Quick Sort is Big O of n logn. The space complexity is calculated based on the space used in the recursion stack. The worst case space used will be O(n) . The average case space used will be of the order O(log n).  Heap sort In heap sort the largest item is stored at the root node. We need to remove the root element and put at the end of the array (n th position) Put the last item of the tree (heap) at the vacant place.  Reduce the size of the heap by 1.  Heapify the root element again so that we have the highest element at root. The process is repeated until all the items of the list are sorted. Time complexity is Big O of n log n. Space complexity is Big O of 1. 

Efficiency