Category Archives: Algorithm

Merge Sort

Algorithm Video:

https://youtu.be/TzeBrDU-JaY

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:
https://youtu.be/0nlPxaC2lTw
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:

https://youtu.be/TzeBrDU-JaY

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:
https://youtu.be/0nlPxaC2lTw
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:

https://youtu.be/TzeBrDU-JaY

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:
https://youtu.be/0nlPxaC2lTw
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:
https://www.youtube.com/watch?v=TL2_3sqvogo

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:

https://www.youtube.com/watch?v=Jdtq5uKz-w4&list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U&index=3

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

https://youtu.be/GUDLRan2DWM?list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U

PSeudoCode:

Implemented Code:

output:

 

Selection Sort

https://youtu.be/GUDLRan2DWM?list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U

PSeudoCode:

Implemented Code:

output:

 

Selection Sort

https://youtu.be/GUDLRan2DWM?list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U

PSeudoCode:

Implemented Code:

output:

 

QuickSort

Youtube Video:
https://www.youtube.com/watch?v=COk73cpQbFQ

Analaysis though it seems little bit tough to me:

https://www.youtube.com/watch?v=3Bbm3Prd5Fo

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):
https://www.youtube.com/watch?v=3DV8GO9g7B4

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:
https://www.youtube.com/watch?v=DpNmUP4wuf8

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&*

Stevie Hackerearth

code:

 

Basics of Implementation – Hackerearth

Vowel count in a string:
code:

Count Digit:

 

C++ Vector push_back()…pop_back()

https://www.youtube.com/watch?v=opAnlfre-Kw

Algo – Linked List

Best Video Explained:
https://www.youtube.com/watch?v=eGnlKPCkAFY

code:

some bugs  here but understood the implementation:

 

Algorithm: Euler’s GCD

https://www.youtube.com/watch?v=WAyPIMme3Yw&index=8&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25
code:

more optimized:

 

Recursive:

 

http://www.progkriya.org/gyan/basic-number-theory.html#section3

Algo: Prime factorization of a number

https://www.youtube.com/watch?v=6PDtgHhpCHo&index=6&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25

code:

I/O:

 

Prime Number: Trial division | Prime check upto N in C

https://www.youtube.com/watch?v=7VPA-HjjUmU

code:

Help can be find:
http://www.studystreet.com/c-program-print-prime-numbers/
http://www.codingalpha.com/prime-number-c-program/
https://en.wikipedia.org/wiki/Primality_test