Category Archives: Sorting

Bucket Sort

Pseudocode:

Implemented Code:

output:

 

Tuts:

Reference:
CLRS: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm

Bucket Sort

Harumanchi Book implementation:

output:

 

Time and Space complexity: O(n)

Radix Sort

best video:

pseudocode:

implementation: (I need to clear the radix sort part later..took help to implement)

Reference:

Radix Sort – Explanation, Pseudocode and Implementation

Time complexity: O(d*n)==O(n)
Where d is the digit of the number

Counting Sort

Algo:

Implemented Code:

 

Reference:
http://scanftree.com/Data_Structure/Counting-sort

Counting Sort in C

CLRS:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/countingSort.htm

Tuts:

Complexity:
Time: O(k)+O(n)+O(k)+O(n)=O(n) if K=O(n)
Space: O(n)

Heap Sort

Steps:
If we want to sort in ascending then we create a min heap
If we want to create in descending then we create in max heap

Once the heap is created we delete the root node from heap and put the last node in the root position and repeat the steps till we have covered all the elements.
For ascending order:
1. Build Heap
2. Transform the heap into min heap
3. Delete the root node

pseudocode:

source:
http://www.algorithmist.com/index.php/Heap_sort

Implemented code:

output:

Took help from these two links:
http://www.codingeek.com/algorithms/heap-sort-algorithm-explanation-and-implementation/
http://www.geeksforgeeks.org/heap-sort/

Complexity Analysis:
Time Complexity for MaxHeapify: O(logn)
Complexity for BuildHeap: O(n)
Complexity of heapSort:
Worst, Avergae, Base case: O(n*logn)
It is inplace algorithm.
Space Complexity: O(1)

Merge Sort

Algorithm Video:

Merge Sort Combines Two Sorted file in a large bigger sorted files:
This Merge sort happens in a two steps:

This sorting is a example of divide and conquer approach:
1. Selection: Splits a list into two lists (This process is recursive approach)
2. Merging: It joins two list in a one list (It follows the pesudocode in itertive manner)

Pseudocode:

 

Implementation:
code with extra malloc declaration:

code by me without  extra malloc:

output:

Analysis of Running Time Complexity:

Worst case, Best case, Avergae case: Theta(nlogn)
Space Complexity: Theta(n)

 

This link can help to solve problems:
https://gist.github.com/mycodeschool/9678029
https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/

http://www.sanfoundry.com/cpp-program-implement-merge-sort/

Merge Sort

Algorithm Video:

Merge Sort Combines Two Sorted file in a large bigger sorted files:
This Merge sort happens in a two steps:

This sorting is a example of divide and conquer approach:
1. Selection: Splits a list into two lists (This process is recursive approach)
2. Merging: It joins two list in a one list (It follows the pesudocode in itertive manner)

Pseudocode:

 

Implementation:
code with extra malloc declaration:

code by me without  extra malloc:

output:

Analysis of Running Time Complexity:

Worst case, Best case, Avergae case: Theta(nlogn)
Space Complexity: Theta(n)

 

This link can help to solve problems:
https://gist.github.com/mycodeschool/9678029
https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/

http://www.sanfoundry.com/cpp-program-implement-merge-sort/

Bubble Sort

This video is good to help:

I have also taken help from DS Made Easy by Karumanchi book to find the algo pesudocode.

Pseudocode:

Implementation:

I need to improve this algorithm as it is not passing all the sizes of array so there will be some vacant position in array which increases the complexity in the running time so we need to out of the loop when it has nothing to swap, so our improvised algorithm will be:

Pseudocode:

 

Implementation:

This below video can help for better optimization that implemented in the above code:

Time Complexity in Running Time:

Worst Case: O(n^2)
BEst Case without improve: O(n^2)
Best Case(Improvised): O(n)
Average Case: O(n^2)
Space Complexity: O(1)
Simulation Tried to be drawn by me:

 

Selection Sort

PSeudoCode:

Implemented Code:

output:

 

Selection Sort

PSeudoCode:

Implemented Code:

output:

 

QuickSort

Youtube Video:

Analaysis though it seems little bit tough to me:

HackerRank video:

MIT video:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-4-quicksort-randomized-algorithms/

Pseudo Code from upper Youtube vid:

 

Implementation:

Slightly edited in *A to A[]:

Some change with before and after show:

Complete Quicksort Implementation and taking user input:

Output from the above code:

Geeks for geeks:
http://quiz.geeksforgeeks.org/quick-sort/
http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

From geeks for geeks but may be there might be some problems there

Another good one for understanding(I think it’s the best one):

Pseudocode available in the above video:

implemented code:

 

 


Quick Sorting in Process

Time and Space complexity: Best Case : omega(nlogn)
Worst case: O(n^2)

See this video to clear up the skills:

ideone example: http://ideone.com/oWbONR
Others Code:
http://www.cc.gatech.edu/classes/cs3158_98_fall/quicksort.html
Recursive:
http://www.algolist.net/Algorithms/Sorting/Quicksort
CLRS:
http://www.bowdoin.edu/~ltoma/teaching/cs231/fall09/Lectures/5-quicksort/quicksort.pdf

Google Search Terms:
https://www.google.com/webhp?sourceid=chrome-instant&rlz=1C1PRFC_enBD706BD706&ion=1&espv=2&ie=UTF-8#q=quick+sort+pseudocode&*

Sorting Algorithm : Insertion Sort

From this two video I tried to re learn and implement the algorithm with pseudo code.

Pseudocode:

Implemented Code in C:

Output:
2015-08-07 13_30_30-C__Users_User_Desktop_insertionsort.exe

Here ary[] means array 🙂

Simulation:(Wikipedia)

Harvard CS50 course:
http://cs50.tv/2016/fall/

GeeksForGeeks Algo Implement(Not Worked Yet):

http://quiz.geeksforgeeks.org/insertion-sort/
Practice Problem:
http://www.practice.geeksforgeeks.org/problem-page.php?pid=700148
https://www.hackerearth.com/practice/algorithms/sorting/insertion-sort/practice-problems/
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A

CLRS Theory:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/insertionSort.htm

Simple Implementation of Insertion Sorting(Idea Sanfoundry):

It is helpful: http://www.sanfoundry.com/cpp-program-sort-array/

Time complexity of Insertion Sort:

  • Worst case complexity : O(n^2)
  • Best case complexity :    O(n)
  • Average case complextiy:  O(n^2)Reference:
    http://bigocheatsheet.com/

How to calculate complexity there is a example available at the upper video “Lecture 7”

and there are some links
http://stackoverflow.com/questions/19827193/time-complexity-of-insertion-sort

Here a good presentation about this sorting

http://www.cs.mcgill.ca/~cs203/lectures/lecture7/sld006.htm

Reference: http://www.cquestions.com/2009/09/insertion-sort-algorithm.html

For descending order I took help from:
http://cboard.cprogramming.com/c-programming/73433-sorting-descending-order.html
Here they change the comparison value for descending at while loop condition

Another good website:

Time complexity of insertion sort when there are O(n) inversions?


For some theory revise this video is good: