Bubble Sort is the most simple form of sorting algorithm that works by repeatedly stepping through the list of items (array) and swapping the adjacent elements if they are in incorrect order. This algorithm has no such real life uses due to it’s poor performance and is used primarily as an educational tool.

Worst and Average Case Time Complexity: O(n2)
Best Case Time Complexity: O(n)

Heap Sort

Heap sort is a in-place comparison based sorting algorithm based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

Best, Worst and Average Case Time Complexity: n*log(n)

Selection Sort

Selection sort is a simple in-place comparison sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. This is an inefficient sorting technique on large lists (array), and generally performs worse than the similar sorting algorithms.

Best, Worst and Average Case Time Complexity: n^2

Insertion Sort

Insertion sort is a simple in-place comparison-based sorting algorithm. It builds the final sorted array one item at a time. This is an inefficient sorting technique on large lists (arrays), and generally performs worse than the similar sorting algorithms. Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

Average and Worst Case Time Complexity: n^2
Best Case Time Complexity: n

Quick Sort

Quick sort is an highly efficient divide and conquer sorting algorithm. It is based on partitioning of array of data into smaller arrays. Developed in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heap sort. The name comes from the fact that, quick sort is capable of sorting a list of data elements significantly faster than any of the common sorting algorithms.

Average and Best Case Time Complexity: n*log(n)
Worst Case Time Complexity: n^2

Merge Sort

Merge sort is an efficient comparison based divide and conquer algorithm. It is a general purpose algorithm based on the idea of breaking down a list (array) into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list.

Average, Worst and Best Case Time Complexity: n*log(n)

Shell Sort

Shell sort is an in place comparison sort. It can be seen as either a generalization of sorting by exchange or sorting by insertion. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.

Average complexity: n*log(n)^2 or n^(3/2)
Best Complexity: n

C++ Implementation of different Sorting Algorithms

Comments