Ankur's Blog: Sorting

Showing posts with label Sorting. Show all posts

Bucket Sort

Ankur's BlogFebruary 19, 2019Algorithm, Code Repository, Sorting No comments

Bucket Sort

geeksforgeeks

hackerearth

visualization

Time Complexity: If we assume that insertion in a bucket takes O(1) time then steps 1 and 2 of the above algorithm clearly take O(n) time. The O(1) is easily possible if we use a linked list to represent a bucket (In the following code, C++ vector is used for simplicity). Step 4 also takes O(n) time as there will be n items in all buckets.

Heap Sort

Ankur's BlogFebruary 19, 2019Algorithm, GeeksForGeeks, Sorting No comments

Heap Sort

Time Complexity: Time complexity of heapify is O(nLogn). Time complexity of createAndBuildHeap() is O(n) and overall time complexity of Heap Sort is O(nLogn).