My Project - Video Waker Alarm
Get Video alarm on Google Play

Classification and Time Complexity of various Sorting Algorithm


Classification and Time Complexity of various Sorting Algorithm. Sorting means arranging something in a particular defined order. For instance Sorting, either increasing or decreasing order of integers. For example :

Sort these number : 5, 84, 36, 6 , 21 will be written in sorted as 5, 6, 21, 36, 84, in increasing order.  C programs for different sorting Algorithm can be referred, for how to make sort.

Classification and Time Complexity of various Sorting Algorithm :

Sorting Algorithms complexity, is the one of the important topic in algorithms, to be read, as it provides us a way to find the complexity of different algorithms.

Classification and Time Complexity of various Sorting Algorithm
Classification and Time Complexity of various Sorting Algorithm

Algorithms are classified as follows :

1. Comparison based Sorting technique and Counting based Sorting technique.

-> Types of Comparison based sorting technique:
a. Bubble Sort.
b. Selection Sort.
c. Insertion Sort.
d. Heap Sort.
e. Quick Sort.
f. Merge Sort.

-> Types of Counting based sorting technique:
a. Radix Sort.
b. Bucket Sort.

2. In-Place and Not-In-Place algorithm.

In-place : In In-Place algorithm, no additional data structure or array is required for sorting.

-> Types of In-place Algorithms :
a.. Bubble Sort.
b. Selection Sort.
c.. Insertion Sort.
d. Heap Sort.
e. Quick Sort.

Not-In-Place : In Not-In-Place algorithm additional ,data structure or array is required for sorting.

->Types of  Not-In-Place Algorithm :
a. Radix Sort.
b. Bucket Sort.
c. Merge Sort.

Time Complexities of various comparison based Algorithms are described in table:

Best case     Average case     Worst case

Bubble sort                   O(n^2)           O(n^2)                  O(n^2)

Selection sort               O(n^2)             O(n^2)                O(n^2)

Insertion sort                O(n)                 O(n^2)                O(n^2)

Heap sort                     O(n log n)        O(n log n)            O(n log n)

Quick sort                    O(n log n)        O(n log n)            O(n^2)

Merge sort                   O(n log n)        O(n log n)             O(n log n)

Do comment below with your queries. I would love to discuss with you.