###### Sequential-Circuits

October 15, 2023###### NIC-NIELIT STA 2020

October 15, 2023# Algorithms

Question 2 |

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

Quicksort using the last element as pivot | |

Insertion sort | |

Selection sort | |

Mergesort |

Quick sort(with last element as pivot) → will give the worst case time complexity as O(n^2).

Merge Sort → The merge sort will not depend upon the input order and will give O(nlogn) time complexity.

Insertion Sort → Insertion sort will perform best case time complexity when the input array is in sorted order. If the array is already sorted then the inversion count is 0 and If the array is sorted in reverse order that inversion count is the maximum.

Note: Inversion formal definition is two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j.

The number of comparisons will not take more than “n” for the given input array.

Selection Sort → Selection sort will not depend upon the input order and will give O(n^2) time complexity.

Quick sort(with last element as pivot) → will give the worst case time complexity as O(n^2).

Merge Sort → The merge sort will not depend upon the input order and will give O(nlogn) time complexity.

Insertion Sort → Insertion sort will perform best case time complexity when the input array is in sorted order. If the array is already sorted then the inversion count is 0 and If the array is sorted in reverse order that inversion count is the maximum.

Note: Inversion formal definition is two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j.

The number of comparisons will not take more than “n” for the given input array.

Selection Sort → Selection sort will not depend upon the input order and will give O(n^2) time complexity.