Saturday, October 31, 2015

Dancing Sort Algorithms

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

(Graphic from )
(Videos from: )
(Pseudocode: )
(Pseudocode Shell: )
(Main Links (titles): Wikipedia:

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:

  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[] 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)