From Free Knowledge Base- The DUCK Project: information for everyone
6,188 bytes added,
17:25, 29 January 2008 The following lines were added (+) and removed (-):
== Sorting Algorithms =={| border=2 cellspacing=0 cellpadding=4|-|# Bogosort|-|# Bubble sort|# Very fast for lists that are almost sorted, slow sorting anything else.|-|# Cocktail sort|-|# Comb sort|-|# Selection sort|# Simple and fast on small lists, slow on big lists|-|# Insertion sort|# Also known as a Counting sort, ''see below''.|-|# Bucket sort|-|# Counting sort|# Extremely fast when the data is distributed over a small number range. Number only. Requires more memory.|-|# Heapsort|-|# Smoothsort|-|# Merge sort|-|# Quicksort|-|# Binary tree sort|-|# Pigeonhole sort|-|# Radix sort|-|# Selectionsort|# simple to understand and fast on small (dozen items) list. not fast algorithm for large lists.|-|# Shell sort|}=== quicksort ====== bubblesort === <nowiki>' min and max are the minimum and maximum indexes</nowiki> <nowiki>' of the items that might still be out of order.</nowiki> <nowiki>Sub BubbleSort (List() As Long, ByVal min As Integer, _</nowiki> <nowiki> ByVal max As Integer)</nowiki> <nowiki>Dim last_swap As Integer</nowiki> <nowiki>Dim i As Integer</nowiki> <nowiki>Dim j As Integer</nowiki> <nowiki>Dim tmp As Long</nowiki> <nowiki></nowiki> <nowiki> ' Repeat until we are done.</nowiki> <nowiki> Do While min < max</nowiki> <nowiki> ' Bubble up.</nowiki> <nowiki> last_swap = min - 1</nowiki> <nowiki> ' For i = min + 1 To max</nowiki> <nowiki> i = min + 1</nowiki> <nowiki> Do While i <= max</nowiki> <nowiki> ' Find a bubble.</nowiki> <nowiki> If List(i - 1) > List(i) Then</nowiki> <nowiki> ' See where to drop the bubble.</nowiki> <nowiki> tmp = List(i - 1)</nowiki> <nowiki> j = i</nowiki> <nowiki> Do</nowiki> <nowiki> List(j - 1) = List(j)</nowiki> <nowiki> j = j + 1</nowiki> <nowiki> If j > max Then Exit Do</nowiki> <nowiki> Loop While List(j) < tmp</nowiki> <nowiki> List(j - 1) = tmp</nowiki> <nowiki> last_swap = j - 1</nowiki> <nowiki> i = j + 1</nowiki> <nowiki> Else</nowiki> <nowiki> i = i + 1</nowiki> <nowiki> End If</nowiki> <nowiki> Loop</nowiki> <nowiki> ' Update max.</nowiki> <nowiki> max = last_swap - 1</nowiki> <nowiki></nowiki> <nowiki> ' Bubble down.</nowiki> <nowiki> last_swap = max + 1</nowiki> <nowiki> ' For i = max - 1 To min Step -1</nowiki> <nowiki> i = max - 1</nowiki> <nowiki> Do While i >= min</nowiki> <nowiki> ' Find a bubble.</nowiki> <nowiki> If List(i + 1) < List(i) Then</nowiki> <nowiki> ' See where to drop the bubble.</nowiki> <nowiki> tmp = List(i + 1)</nowiki> <nowiki> j = i</nowiki> <nowiki> Do</nowiki> <nowiki> List(j + 1) = List(j)</nowiki> <nowiki> j = j - 1</nowiki> <nowiki> If j < min Then Exit Do</nowiki> <nowiki> Loop While List(j) > tmp</nowiki> <nowiki> List(j + 1) = tmp</nowiki> <nowiki> last_swap = j + 1</nowiki> <nowiki> i = j - 1</nowiki> <nowiki> Else</nowiki> <nowiki> i = i - 1</nowiki> <nowiki> End If</nowiki> <nowiki> Loop</nowiki> <nowiki> ' Update min.</nowiki> <nowiki> min = last_swap + 1</nowiki> <nowiki> Loop</nowiki> <nowiki>End Sub</nowiki> === quicksort (and remove duplicates) ===Countingsort does not use comparisons. The items to sort must be integers, and this sort works best with a limited or defined range. A range across 1000 will work well, a range across 100,000 will not. <nowiki>Sub Countingsort (List() As Long, sorted_list() As Long, _</nowiki> <nowiki> min As Integer, max As Integer, min_value As Long, _</nowiki> <nowiki> max_value As Long)</nowiki> <nowiki>Dim counts() As Integer</nowiki> <nowiki>Dim i As Integer</nowiki> <nowiki>Dim this_count As Integer</nowiki> <nowiki>Dim next_offset As Integer</nowiki> <nowiki></nowiki> <nowiki> ' Create the Counts array.</nowiki> <nowiki> ReDim counts(min_value To max_value)</nowiki> <nowiki></nowiki> <nowiki> ' Count the items.</nowiki> <nowiki> For i = min To max</nowiki> <nowiki> counts(List(i)) = counts(List(i)) + 1</nowiki> <nowiki> Next i</nowiki> <nowiki></nowiki> <nowiki> ' Convert the counts into offsets.</nowiki> <nowiki> next_offset = min</nowiki> <nowiki> For i = min_value To max_value</nowiki> <nowiki> this_count = counts(i)</nowiki> <nowiki> counts(i) = next_offset</nowiki> <nowiki> next_offset = next_offset + this_count</nowiki> <nowiki> Next i</nowiki> <nowiki></nowiki> <nowiki> ' Place the items in the sorted array.</nowiki> <nowiki> For i = min To max</nowiki> <nowiki> sorted_list(counts(List(i))) = List(i)</nowiki> <nowiki> counts(List(i)) = counts(List(i)) + 1</nowiki> <nowiki> Next i</nowiki> <nowiki>End Sub</nowiki>=== selectionsort === <nowiki>Sub Selectionsort (List() As Long, min As Integer, _</nowiki> <nowiki> max As Integer)</nowiki> <nowiki>Dim i As Integer</nowiki> <nowiki>Dim j As Integer</nowiki> <nowiki>Dim best_value As Long</nowiki> <nowiki>Dim best_j As Integer</nowiki> <nowiki></nowiki> <nowiki> For i = min To max - 1</nowiki> <nowiki> best_value = List(i)</nowiki> <nowiki> best_j = i</nowiki> <nowiki> For j = i + 1 To max</nowiki> <nowiki> If List(j) < best_value Then</nowiki> <nowiki> best_value = List(j)</nowiki> <nowiki> best_j = j</nowiki> <nowiki> End If</nowiki> <nowiki> Next j</nowiki> <nowiki> List(best_j) = List(i)</nowiki> <nowiki> List(i) = best_value</nowiki> <nowiki> Next i</nowiki> <nowiki>End Sub</nowiki>
