Sorting Algorithms


#1

Quicksort,mergesort,heapsort,topological sort,bubble sort,Insertion sort.
Questions based on different sorting algorithms and application part of it.


#2

Which sorting algorithm will be faster to find the kth largest element ?
(a)Insertion sort.
(b)Quick sort.
©Heap sort.
(d)Topological sort.


#3

heap sort !! Dont know the approach ?


#4

What about the smooth sort?


#5

Is that even a sorting algorithm?
Haven’t heard of it.


#6

It is. Have read it in a comment posted on worst case scenario


#7

As far I know a variation of quicksort - quickselect can be used, the basic idea is after you find the position of pivot, you dont call quicksort for both partition, say k =6,and I choose last element aa pivot and its true position comes out to be 3,then I know the array on the left of pivot are not greater than 4th element in sorted position, so kth largest that is 6th largest can only occur in the right sub array so we call quicksort again fr the right subarea, the best case is obviously O(n).
What about the average and worst case?
Does heap sort best case is better than this algorithm.


#8

heap sort is better than this.


#9

@sssrocks @geetam

In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(n log n).
Smoothsort builds up an implicit heap data structure in the array to be sorted, then sorts the array by repeatedly extracting the maximum element from that heap. Unlike heapsort, which places the root of the heap and largest element at the beginning (left) of the array before swapping it to the end (right), smoothsort places the root of the heap at the right, already in its final location. This, however, considerably complicates the algorithm for removing the rightmost element. Read more about it https://en.wikipedia.org/wiki/Smoothsort


#10

Among all the above heap sort would the fatest one…


#11

heap sort have least time complexity i.e O(n(log n)) in both best and average case min heap and max heap are used for finding the largest and smallest element