Showing posts with label Data Structure and Algorithm. Show all posts
Showing posts with label Data Structure and Algorithm. Show all posts

Wednesday, October 18, 2017

Data Structure and algorithm links


  1. https://www.youtube.com/watch?v=Pn874kEc3IA
  2. http://cs.fit.edu/~ryan/java/programs/graph/Prim-java.html
  3. http://theoryofprogramming.com/2015/03/27/prims-algorithm/
  4. https://stackoverflow.com/questions/18009158/i-want-to-write-a-prims-algorithm-in-java
  5. https://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/graph/Prim.java
  6. http://sourcecodesforfree.blogspot.in/2013/05/10-prims-algorithm.html
  7. http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
  8. http://www.geeksforgeeks.org/?p=26604
  9. http://www.geeksforgeeks.org/?p=11110
  10. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/mst.pdf
  11. http://www.ics.uci.edu/~eppstein/161/960206.html
  12. http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/prim2.html
  13. http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Levitin/Contents.htm
  14. http://ind.ntou.edu.tw/~litsnow/al98/pdf/Algorithm-Ch6-Heapsort.pdf
  15. http://ind.ntou.edu.tw/~litsnow/al98/
  16. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-1-algorithmic-thinking-peak-finding/
  17. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/
  18. http://theoryapp.com/selection-insertion-and-bubble-sort/
  19. http://farenda.com/algorithms-and-data-structures/

Best tutorial (for C programmer):

Monday, July 17, 2017

Selection Sort Algorithm with Pictorial View

how the Selection Sort works, let's see how the computer would perform this sort with numbers. Below is our modified algorithm for sorting a list of numbers.

Selection Sort Algorithm
  1. Get a list of unsorted numbers
  2. Set a marker for the unsorted section at the front of the list
  3. Repeat steps 4 - 6 until one number remains in the unsorted section
  4.    Compare all unsorted numbers in order to select the smallest one
  5.    Swap this number with the first number in the unsorted section
  6.    Advance the marker to the right one position
  7. Stop
Again our modified algorithm is almost identical to our card sorting algorithm. We only needed to substitute numbers for playing cards and a list of numbers for a hand of cards. One other slight change is that steps 4 and 5 of the Selection Card Sort have been combined. This is typical since a computer will usually keep track of the smallest number while it compares all the numbers. The steps below illustrate how the Selection Sort algorithm works on a computer.

  1. First, we give the computer a list of unsorted numbers and store them in an array of memory cells.


  2. To begin the sort, the computer divides the sorted and unsorted sections of the list by placing a marker before the first number. To sort the numbers, the computer will repeatedly search the unsorted section for the smallest number, swap this number with the first number in the unsorted section, and update the sort marker.


  3. To find the smallest number in the unsorted section, the computer must make six comparisons: (7 < 8), (7 > 5), (5 > 2), (2 < 4), (2 < 6), and (2 > 3). After these comparisons, the computer knows that 2 is the smallest number, so it swaps this number with 7, the first number in the unsorted section, and advances the sort marker.


  4. Now five more comparisons are needed to find the smallest number in the unsorted section: (8 > 5), (5 < 7), (5 > 4), (4 < 6), and (4 > 3). After these comparisons, the computer swaps 3, the smallest number in the unsorted section, with 8, the first number in the unsorted section, and advances the sort marker.


  5. This time four comparisons are needed to determine that 4 is the smallest number in the unsorted section: (5 < 7), (5 > 4), (4 < 6), and (4 < 8). After these comparisons, the computer swaps 4 with 5 and then advances the sort marker.


  6. After three more comparisons, the computer identifies 5 as the smallest unsorted number: (7 > 5), (5 < 6), and (5 < 8). Then the computer swaps 5 with 7 and advances the sort marker.


  7. This time only two comparisons are needed to determine that 6 is the smallest number: (7 > 6) and (6 < 8). After these two comparisons, the computer swaps 6 with 7 and then advances the sort marker.


  8. Now we only need a single comparison to find the right position for 7: (7 < 8). Since 7 is the smallest number and it is also the first number in the unsorted section, the computer does not need to swap this number. It only needs to advance the sort marker. Now there is only one number in the unsorted section, so the list of numbers is sorted and the Selection Sort algorithm is complete.

     Resource Link: https://courses.cs.vt.edu/csonline/Algorithms/Lessons/SelectionSort/index.html