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

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

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