In this article I will describe some sorting algorithms. All algorithms presented here have been written in C# and a lot of ideas are based on algorithms you can find on Wikipedia
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. The equally simple insertion sort has better performance than bubble sort, so some have suggested no longer teaching the bubble sort.
public IList BubbleSort(IList arrayToSort)
{
int n = arrayToSort.Count - 1;
for (int i = 0; i < n; i++)
{
for (int j = n; j > i; j--)
{
if (((IComparable)arrayToSort[j - 1]).CompareTo(arrayToSort[j]) > 0)
{
object temp = arrayToSort[j - 1];
arrayToSort[j - 1] = arrayToSort[j];
arrayToSort[j] = temp;
RedrawItem(j);
RedrawItem(j - 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
}
return arrayToSort;
}BiDirectional Bubble Sort
public IList CombSort(IList arrayToSort)
public IList BiDerectionalBubleSort(IList arrayToSort)
Bucket Sort
Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the O(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.Bucket sort works as follows:
- Set up an array of initially empty "buckets."
- Scatter: Go over the original array, putting each object in its bucket.
- Sort each non-empty bucket.
- Gather: Visit the buckets in order and put all elements back into the original array.
public IList BucketSort(IList arrayToSort)
{
if (arrayToSort == null || arrayToSort.Count == 0) return arrayToSort;
object max = arrayToSort[0];
object min = arrayToSort[0];
for (int i = 0; i < arrayToSort.Count; i++)
{
if (((IComparable)arrayToSort[i]).CompareTo(max) > 0)
{
max = arrayToSort[i];
}
if (((IComparable)arrayToSort[i]).CompareTo(min) < 0)
{
min = arrayToSort[i];
}
}
ArrayList[] holder = new ArrayList[(int)max - (int)min + 1];
for (int i = 0; i < holder.Length; i++)
{
holder[i] = new ArrayList();
}
for (int i = 0; i < arrayToSort.Count; i++)
{
holder[(int)arrayToSort[i] - (int)min].Add(arrayToSort[i]);
}
int k = 0;
for (int i = 0; i < holder.Length; i++)
{
if (holder[i].Count > 0)
{
for (int j = 0; j < holder[i].Count; j++)
{
arrayToSort[k] = holder[i][j];
RedrawItem(k);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
k++;
}
}
}
return arrayToSort;
}
Comb Sort
Comb sort is a relatively simplistic sorting algorithm originally designed by Wlodzimierz Dobosiewicz in 1980. Later it was rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine article published in April 1991. Comb sort improves on bubble sort, and rivals algorithms like Quicksort. The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. (Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.).In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than one.The gap starts out as the length of the list being sorted divided by the shrink factor (generally 1.3), and the list is sorted with that value (rounded down to an integer if needed) for the gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.public IList CombSort(IList arrayToSort)
{
int gap = arrayToSort.Count;
int swaps = 0;
do
{
gap = (int)(gap / 1.247330950103979);
if (gap < 1)
{
gap = 1;
}
int i = 0;
swaps = 0;
do
{
if (((IComparable)arrayToSort[i]).CompareTo(arrayToSort[i + gap]) > 0)
{
object temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[i + gap];
arrayToSort[i + gap] = temp;
RedrawItem(i);
RedrawItem(i + gap);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
swaps = 1;
}
i++;
} while (!(i + gap >= arrayToSort.Count));
} while (!(gap == 1 && swaps == 0));
return arrayToSort;
}
Cycle Sort
Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.Unlike nearly every other sort, items are never written elsewhere in the array simply to push them out of the way of the action. Each value is either written zero times, if it's already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.public IList CycleSort(IList arrayToSort)
{
int writes = 0;
for (int cycleStart = 0; cycleStart < arrayToSort.Count; cycleStart++)
{
object item = arrayToSort[cycleStart];
int pos = cycleStart;
do
{
int to = 0;
for (int i = 0; i < arrayToSort.Count; i++)
{
if (i != cycleStart && ((IComparable)arrayToSort[i]).CompareTo(item) < 0)
{
to++;
}
}
if (pos != to)
{
while (pos != to && ((IComparable)item).CompareTo(arrayToSort[to]) == 0)
{
to++;
}
object temp = arrayToSort[to];
arrayToSort[to] = item;
RedrawItem(to);
item = temp;
RedrawItem(cycleStart);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
writes++;
pos = to;
}
} while (cycleStart != pos);
}
return arrayToSort;
}
Gnome Sort
Gnome sort, originally proposed by Hamid Sarbazi-Azad in 2000 and called Stupid sort, and then later on described by Dick Grune and named "Gnome sort", is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort.It is conceptually simple, requiring no nested loops. The running time is O(n2), but tends towards O(n) if the list is initially almost sorted. In practice the algorithm can run as fast as Insertion sort. The average runtime is O(n2)The algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. It takes advantage of the fact that performing a swap can introduce a new out-of-order adjacent pair only right before or after the two swapped elements. It does not assume that elements forward of the current position are sorted, so it only needs to check the position directly before the swapped elements.public IList GnomeSort(IList arrayToSort)
{
int pos = 1;
while (pos < arrayToSort.Count)
{
if (((IComparable)arrayToSort[pos]).CompareTo(arrayToSort[pos - 1]) >= 0)
{
pos++;
}
else
{
object temp = arrayToSort[pos];
arrayToSort[pos] = arrayToSort[pos - 1];
RedrawItem(pos);
arrayToSort[pos - 1] = temp;
RedrawItem(pos - 1);
RefreshPanel(pnlSamples);
if (savePicture)
SavePicture();
if (pos > 1)
{
pos--;
}
}
}
return arrayToSort;
}
Heap Sort
Heapsort begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.Heapsort inserts the input list elements into a binary heap data structure. The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order. The heap's invariant is preserved after each extraction, so the only cost is that of extraction.During extraction, the only space required is that needed to store the heap. To achieve constant space overhead, the heap is stored in the part of the input array not yet sorted.Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.public IList HeapSort(IList list)
{
for (int i = (list.Count - 1) / 2; i >= 0; i--)
Adjust(list, i, list.Count - 1);
for (int i = list.Count - 1; i >= 1; i--)
{
object Temp = list[0];
list[0] = list[i];
list[i] = Temp;
RedrawItem(0);
RedrawItem(i);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
Adjust(list, 0, i - 1);
}
return list;
}
public void Adjust(IList list, int i, int m)
{
object Temp = list[i];
int j = i * 2 + 1;
while (j <= m)
{
if (j < m)
if (((IComparable)list[j]).CompareTo(list[j + 1]) < 0)
j = j + 1;
if (((IComparable)Temp).CompareTo(list[j]) < 0)
{
list[i] = list[j];
RedrawItem(i);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
i = j;
j = 2 * i + 1;
}
else
{
j = m + 1;
}
}
list[i] = Temp;
RedrawItem(i);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
Insertion Sort
If the first few objects are already sorted, an unsorted object can be inserted in the sorted set in proper place. This is called insertion sort. An algorithm consider the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted). Insertion sort is an example of an incremental algorithm. It builds the sorted sequence one number at a time. This is perhaps the simplest example of the incremental insertion technique, where we build up a complicated structure on n items by first building it on n − 1 items and then making the necessary changes to fix things in adding the last item. The given sequences are typically stored in arrays. We also refer the numbers as keys. Along with each key may be additional information, known as satellite data.public IList InsertionSort(IList arrayToSort)
{
for (int i = 1; i < arrayToSort.Count; i++)
{
object val = arrayToSort[i];
int j = i - 1;
bool done = false;
do
{
if (((IComparable)arrayToSort[j]).CompareTo(val) > 0)
{
arrayToSort[j + 1] = arrayToSort[j];
RedrawItem(j + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
j--;
if (j < 0)
{
done = true;
}
}
else
{
done = true;
}
} while (!done);
arrayToSort[j + 1] = val;
RedrawItem(j + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
return arrayToSort;
}
Merge Sort
Conceptually, a merge sort works as follows- If the list is of length 0 or 1, then it is already sorted. Otherwise:
- Divide the unsorted list into two sublists of about half the size.
- Sort each sublist recursively by re-applying merge sort.
- Merge the two sublists back into one sorted list.
Merge sort incorporates two main ideas to improve its runtime:- A small list will take fewer steps to sort than a large list.
- Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted (see the merge function below for an example implementation).
public IList MergeSort(IList a, int low, int height)
{
int l = low;
int h = height;
if (l >= h)
{
return a;
}
int mid = (l + h) / 2;
MergeSort(a, l, mid);
MergeSort(a, mid + 1, h);
int end_lo = mid;
int start_hi = mid + 1;
while ((l <= end_lo) && (start_hi <= h))
{
if (((IComparable)a[l]).CompareTo(a[start_hi]) < 0)
{
l++;
}
else
{
object temp = a[start_hi];
for (int k = start_hi - 1; k >= l; k--)
{
a[k + 1] = a[k];
RedrawItem(k + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
a[l] = temp;
RedrawItem(l);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
l++;
end_lo++;
start_hi++;
}
}
return a;
}
Odd-Even Sort
Odd-even sort is a relatively simple sorting algorithm. It is a comparison sort based on bubble sort with which it shares many characteristics. It functions by comparing all (odd, even)-indexed pairs of adjacent elements in the list and, if a pair is in the wrong order (the first is larger than the second) the elements are switched. The next step repeats this for (even, odd)-indexed pairs (of adjacent elements). Then it alternates between (odd, even) and (even, odd) steps until the list is sorted. It can be thought of as using parallel processors, each using bubblesort but starting at different points in the list (all odd indices for the first step). This sorting algorithm is only marginally more difficult than bubble sort to implement.public IList OddEvenSort(IList arrayToSort)
{
bool sorted = false;
while (!sorted)
{
sorted = true;
for (var i = 1; i < arrayToSort.Count - 1; i += 2)
{
if (((IComparable)arrayToSort[i]).CompareTo(arrayToSort[i + 1]) > 0)
{
object temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[i + 1];
RedrawItem(i);
arrayToSort[i + 1] = temp;
RedrawItem(i+1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
sorted = false;
}
}
for (var i = 0; i < arrayToSort.Count - 1; i += 2)
{
if (((IComparable)arrayToSort[i]).CompareTo(arrayToSort[i + 1]) > 0)
{
object temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[i + 1];
arrayToSort[i + 1] = temp;
RedrawItem(i);
RedrawItem(i+1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
sorted = false;
}
}
}
return arrayToSort;
}
Pigeonhole Sort
Pigeonhole sorting, also known as count sort (not to be confused with counting sort), is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same. It requires O(n + N) time.The pigeonhole algorithm works as follows:- Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes," one pigeonhole for each key through the range of the original array.
- Going over the original array, put each value into the pigeonhole corresponding to its key, such that each pigeonhole eventually contains a list of all values with that key.
- Iterate over the pigeonhole array in order, and put elements from non-empty pigeonholes back into the original array.
public IList PigeonHoleSort(IList list)
{
object min = list[0], max = list[0];
foreach (object x in list)
{
if (((IComparable)min).CompareTo(x) > 0)
{
min = x;
}
if (((IComparable)max).CompareTo(x) < 0)
{
max = x;
}
Thread.Sleep(speed);
}
int size = (int)max - (int)min + 1;
int[] holes = new int[size];
foreach (int x in list)
holes[x - (int)min]++;
int i = 0;
for (int count = 0; count < size; count++)
while (holes[count]-- > 0)
{
list[i] = count + (int)min;
RedrawItem(i);
i++;
RefreshPanel(pnlSamples);
Thread.Sleep(speed);
}
return list;
}
Quick Sort
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists. The steps are:- Pick an element, called a pivot, from the list.
- Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which never need to be sorted.
public IList QuickSort(IList a, int left, int right)
{
int i = left;
int j = right;
double pivotValue = ((left + right) / 2);
int x = (int)a[int.Parse(pivotValue.ToString())];
while (i <= j)
{
while (((IComparable)a[i]).CompareTo(x) < 0)
{
i++;
}
while (((IComparable)x).CompareTo(a[j]) < 0)
{
j--;
}
if (i <= j)
{
object temp = a[i];
a[i] = a[j];
RedrawItem(i);
i++;
a[j] = temp;
RedrawItem(j);
j--;
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
if (left < j)
{
QuickSort(a, left, j);
}
if (i < right)
{
QuickSort(a, i, right);
}
return a;
}
Selection Sort
The algorithm works as follows:- Find the minimum value in the list
- Swap it with the value in the first position
- Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)
Effectively, the list is divided into two parts: the sublist of items already sorted, which is built up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array.
Collapsepublic IList SelectionSort(IList arrayToSort)
{
int min;
for (int i = 0; i < arrayToSort.Count; i++)
{
min = i;
for (int j = i + 1; j < arrayToSort.Count; j++)
{
if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[min]) < 0)
{
min = j;
}
}
object temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[min];
arrayToSort[min] = temp;
RedrawItem(i);
RedrawItem(min);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
return arrayToSort;
}
No comments:
Post a Comment