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/ )
(Pseudocode: http://visualgo.net/ )
(Pseudocode Shell: https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect14.pdf )

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
for i = leftPartStartIndex to rightPartLastIndex inclusive