Saturday, October 31, 2015

Dancing Sort Algorithms

Post, only to illustrate the most common types of sorting algorithms:
Graphically, Dance, and Code:

(Graphic from http://www.sorting-algorithms.com/ )
(Videos from: https://www.youtube.com/user/AlgoRythmics )
(Pseudocode: http://visualgo.net/ )
(Pseudocode Shell: https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect14.pdf )
(Main Links (titles): Wikipedia: https://en.wikipedia.org/wiki/Sorting_algorithm

Sorting Algorithms general animated image:
(Algorithms race)



1.-  Insert:

mark first element as sorted
for each unsorted element
  'extract' the element
  for i = lastSortedIndex to 0
    if currentSortedElement > extractedElement
      move sorted element to the right by 1
    else: insert extracted element



2.- Select:

repeat (numOfElements - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position



3.- Bubble:

do
  swapped = false
  for i = 1 to indexOfLastUnsortedElement
    if leftElement > rightElement
      swap(leftElement, rightElement)
      swapped = true
while swapped


4.- Shell:

                                # Start with the largest gap and work down to a gap of 1
                                     foreach (gap in gaps){
                                # Do a gapped insertion sort for this gap size.
                                                     # The first gap elements a[0..gap-1] are already in gapped order
                                                     # keep adding one more element until the entire array is gap sorted  
                                     for (i = gap; i < n; i += 1){
                                            temp = a[i]
                                            for (j = i; j >= gap and a[j - gap] > temp; j -= gap){
                                                  a[j] = a[j - gap]
                                            }
                                            a[j] = temp
                                      }
                                }


5.- Merge:

split each element into partitions of size 1
recursively merge adjancent partitions
  for i = leftPartStartIndex to rightPartLastIndex inclusive
    if leftPartHeadValue <= rightPartHeadValue
      copy leftPartHeadValue
    else: copy rightPartHeadValue
copy elements back to original array


7.- Quick:

for each (unsorted) partition
  set first element as pivot
  storeIndex = pivotIndex + 1
  for i = pivotIndex + 1 to rightmostIndex
    if element[i] < element[pivot]
      swap(i, storeIndex); storeIndex++
  swap(pivot, storeIndex - 1)