Before a couple of days I have posted new article about sorting algorithms and visualization. More about that you can find here

## Wednesday, December 8, 2010

## Sunday, December 5, 2010

### 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(n

^{2}), 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(n

^{2})

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; }

### 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; }

### 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)

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; }

### 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; }

### 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.

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; }

### 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:

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; }

### 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; }

### 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.

- 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; }

## Saturday, December 4, 2010

### 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; }

### 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(); }

### 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; }

## Thursday, December 2, 2010

### 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; }

### 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; }

### 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; }

### 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; }

## Wednesday, December 1, 2010

### How to convert BMP to GIF in C#

In this post I will show you how to convert bmp file to gif in C#. First step you must do is create Bitmap object. In this example I passed filename to constructor of this object. Next you need to create ImageCodecInfo and chose appropriate mime type of output format. You can set quality and compression of output image. In case you need to do this, you must create EncoderParameters object which represents list of EncoderParameter objects. This objects represent set of parameters which encoder uses for image encoding.

static void Main(string[] args) { Bitmap myBitmap=new Bitmap(@"test.bmp"); ImageCodecInfo myImageCodecInfo = GetEncoderInfo("image/gif"); ; EncoderParameter encCompressionrParameter = new EncoderParameter(System.Drawing.Imaging.Encoder.Compression, (long)EncoderValue.CompressionLZW); ; EncoderParameter encQualityParameter = new EncoderParameter(System.Drawing.Imaging.Encoder.Quality, 0L); EncoderParameters myEncoderParameters = new EncoderParameters(2); myEncoderParameters.Param[0] = encCompressionrParameter; myEncoderParameters.Param[1] = encQualityParameter; myBitmap.Save("Output.gif", myImageCodecInfo, myEncoderParameters); } private static ImageCodecInfo GetEncoderInfo(String mimeType) { int j; ImageCodecInfo[] encoders; encoders = ImageCodecInfo.GetImageEncoders(); for (j = 0; j < encoders.Length; ++j) { if (encoders[j].MimeType == mimeType) return encoders[j]; } return null; }

Subscribe to:
Posts (Atom)