Introduction
The first thing I consider to be the most important to understand is what sorting algorithms are. According to Wikipedia, the sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output.
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.
Algorithms presented here:
I have decided to create GUI visualization for sorting algorithms. This project also allows users to save outputs into the animated GIF picture and set speed of sorting.
Using the code
This solution consists of 2 projects. First project called Components provides classes for creation of animated GIF images. This project is based on the NGIF project. More information about this project can be found there.
The second project called SortComparison is the main part of the solution. In includes a form called frmMain where you can choose sorting algorithms, set the number of samples you want to sort, sorting speed, and select whether you want to create an animated GIF file. On the form are placed two panels called pnlSort1 and pnlSort2 where the sorting visualizations are rendered.
Every algorithm has its own method named by the name of the sorting algorithm and accepts an IList parameter and returns an IList object.
The method DrawSamples draws all the samples on the panel. This method is called after the random samples are generated. The samples are generated by clicking on the Shuffle button. The samples are stored in the array variable.
private void DrawSamples()
{
g.Clear(Color.White);
for (int i = 0; i < array.Count; i++)
{
int x = (int)(((double)pnlSamples.Width / array.Count) * i);
Pen pen = new Pen(Color.Black);
g.DrawLine(pen, new Point(x, pnlSamples.Height),
new Point(x, (int)(pnlSamples.Height - (int)array[i])));
}
}
The method Randomize orders all the samples in the array variable randomly.
public void Randomize(IList list)
{
for (int i = list.Count - 1; i > 0; i--)
{
int swapIndex = rng.Next(i + 1);
if (swapIndex != i)
{
object tmp = list[swapIndex];
list[swapIndex] = list[i];
list[i] = tmp;
}
}
}
During sorting, when the check box Create animation is checked, images are generated after each swapping of two items of the samples array. This images are indexed from 0 to n where n represents the current number of swaps.
private void SavePicture()
{
ImageCodecInfo myImageCodecInfo = this.getEncoderInfo("image/gif");
EncoderParameter myEncoderParameter = new EncoderParameter(
System.Drawing.Imaging.Encoder.Compression, (long)EncoderValue.CompressionLZW);
EncoderParameter qualityParam =
new EncoderParameter(System.Drawing.Imaging.Encoder.Quality, 0L);
EncoderParameters myEncoderParameters = new EncoderParameters(1);
EncoderParameters encoderParams = new EncoderParameters(2);
encoderParams.Param[0] = qualityParam;
encoderParams.Param[1] = myEncoderParameter;
string destPath =
System.IO.Path.Combine(txtOutputFolder.Text, imgCount + ".gif");
bmpsave.Save(destPath, myImageCodecInfo, encoderParams);
imgCount++;
}
Sorting algorithms
Bubble Sort
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;
}
| Worst case performance: | O(n2) |
| Best case performance: | O(n) |
| Average case performance: | O(n2) |
| Worst case space complexity: | O(1) auxiliary |
Bidirectional Bubble Sort
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuttle sort, or happy hour sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than bubble sort, and solves the problem with so-called turtles in bubble sort.
The first rightward pass will shift the largest element to its correct place at the end, and the following leftward pass will shift the smallest element to its correct place at the beginning. The second complete pass will shift the second largest and second smallest elements to their correct places, and so on. After i passes, the first i and the last i elements in the list are in their correct positions, and do not need to be checked. By shortening the part of the list that is sorted each time, the number of operations can be halved.
public IList BiDerectionalBubleSort(IList arrayToSort)
{
int limit = arrayToSort.Count;
int st = -1;
bool swapped = false;
do
{
swapped = false;
st++;
limit--;
for (int j = st; j < limit; j++)
{
if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
{
object temp = arrayToSort[j];
arrayToSort[j] = arrayToSort[j + 1];
arrayToSort[j + 1] = temp;
swapped = true;
RedrawItem(j);
RedrawItem(j + 1);
pnlSamples.Refresh();
if(chkCreateAnimation.Checked)
SavePicture();
}
}
for (int j = limit - 1; j >= st; j--)
{
if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
{
object temp = arrayToSort[j];
arrayToSort[j] = arrayToSort[j + 1];
arrayToSort[j + 1] = temp;
swapped = true;
RedrawItem(j);
RedrawItem(j + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
} while (st < limit && swapped);
return arrayToSort;
}
| Worst case performance: | O(n2) |
| Best case performance: | O(n) |
| Average case performance: | O(n2) |
| Worst case space complexity: | O(1) auxiliary |
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;
}
| Worst case performance: | O(n2.k) |
| Best case performance: | - |
| Average case performance: | O(n.k) |
| Worst case space complexity: | O(n.k) |
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 Quick sort. 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;
}
| Worst case performance: | - |
| Best case performance: | - |
| Average case performance: | - |
| Worst case space complexity: | O(1) |
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;
}
| Worst case performance: | O(n2) |
| Best case performance: | - |
| Average case performance: | O(n2) |
| Worst case space complexity: | O(1) |
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;
}
| Worst case performance: | O(n2) |
| Best case performance: | - |
| Average case performance: | - |
| Worst case space complexity: | O(1) |
Heap Sort
Heap sort 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.
Heap sort 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.
Heap sort 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();
}
| Worst case performance: | O(n log n) |
| Best case performance: | O(n log n) |
| Average case performance: | O(n log n) |
| Worst case space complexity: | O(1) |
Insertion Sort
If the first few objects are already sorted, an unsorted object can be inserted in the sorted set in the proper place. This is called insertion sort. The algorithm considers 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 to 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;
}
| Worst case performance: | O(n2) |
| Best case performance: | O(n) |
| Average case performance: | O(n2) |
| Worst case space complexity: | O(1) |
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;
}
| Worst case performance: | O(n log n) |
| Best case performance: | O(n log n) |
| Average case performance: | O(n log n) |
| Worst case space complexity: | |
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 bubble sort 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;
}
| Worst case performance: | O(n+2k) |
| Best case performance: | - |
| Average case performance: | O(n+2k) |
| Worst case space complexity: | O(2k) |
Quick Sort
Quick sort 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 cases 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;
}
| Worst case performance: | O(n2) |
| Best case performance: | O(n log n) |
| Average case performance: | O(n log n) |
| Worst case space complexity: | O(log n) |
Quick Sort with Bubble Sort
public IList BubbleSort(IList arrayToSort, int left, int right)
{
for (int i = left; i < right; i++)
{
for (int j = right; j > i; j--)
{
if (((IComparable)arrayToSort[j - 1]).CompareTo(arrayToSort[j]) > 0)
{
object temp = arrayToSort[j - 1];
arrayToSort[j - 1] = arrayToSort[j];
RedrawItem(j-1);
arrayToSort[j] = temp;
RedrawItem(j);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
}
return arrayToSort;
}
public IList QuickSortWithBubbleSort(IList a, int left, int right)
{
int i = left;
int j = right;
if (right - left <= 6)
{
BubbleSort(a, left, right);
return a;
}
double pivotValue = ((left + right) / 2);
int x = (int)a[int.Parse(pivotValue.ToString())];
a[(left + right) / 2] = a[right];
a[right] = x;
RedrawItem(right);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
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 - 1);
a[j--] = temp;
RedrawItem(j + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
if (left < j)
{
QuickSortWithBubbleSort(a, left, j);
}
if (i < right)
{
QuickSortWithBubbleSort(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.
public 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;
}
| Worst case performance: | O(n2) |
| Best case performance: | O(n2) |
| Average case performance: | O(n2) |
| Worst case space complexity: | O(1) |
Shell Sort
The principle of shell sort is to rearrange the file so that looking at every hth element yields a sorted file. We call such a file h-sorted. If the file is then k-sorted for some other integer k, then the file remains h-sorted. For instance, if a list was 5-sorted and then 3-sorted, the list is now not only 3-sorted, but both 5- and 3-sorted. If this were not true, the algorithm would undo work that it had done in previous iterations, and would not achieve such a low running time.
The algorithm draws upon a sequence of positive integers known as the increment sequence. Any sequence will do, as long as it ends with 1, but some sequences perform better than others. The algorithm begins by performing a gap insertion sort, with the gap being the first number in the increment sequence. It continues to perform a gap insertion sort for each number in the sequence, until it finishes with a gap of 1. When the increment reaches 1, the gap insertion sort is simply an ordinary insertion sort, guaranteeing that the final list is sorted. Beginning with large increments allows elements in the file to move quickly towards their final positions, and makes it easier to subsequently sort for smaller increments.
public IList ShellSort(IList arrayToSort)
{
int i, j, increment;
object temp;
increment = arrayToSort.Count / 2;
while (increment > 0)
{
for (i = 0; i < arrayToSort.Count; i++)
{
j = i;
temp = arrayToSort[i];
while ((j >= increment) &&
(((IComparable)arrayToSort[j - increment]).CompareTo(temp) > 0))
{
arrayToSort[j] = arrayToSort[j - increment];
RedrawItem(j);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
j = j - increment;
}
arrayToSort[j] = temp;
RedrawItem(j);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
if (increment == 2)
increment = 1;
else
increment = increment * 5 / 11;
}
return arrayToSort;
}
| Worst case performance: | - |
| Best case performance: | n |
| Average case performance: | O(n log2 n) |
| Worst case space complexity: | O(1) |
In the end, I would like to thank everyone who gave me brilliant ideas on how to improve this article. Thank you!
History
- 01 Dec 2010 - Original version posted.
- 05 Dec 2010 - Gnome Sort, Pigeonhole Sort added; Sort comparison and comparison speed features added.
- 09 Dec 2010 - Performance information tables added.
