Bucket Sort

The following uses the divide-and-conquer method of resolution, by dividing the problem into smaller arrays, sorting each smaller array, then reinserting the subarrays back into the original array.  This is not a pure solution, in that it uses the .NET List, rather than a linked list struct.

using System;
using System.Collections;
using System.Collections.Generic;

namespace Algorithms
{
    class BucketSort
    {
        public int[] Sort()
        {   
            //creates arbitrary array
            int[] arrayToSort = { 11, 7, 22, 2, 33, 3, 17, 44, 4, 55, 5, 66, 6, 1, 77 };
            //create bucket using hash, x/10
            List<int>[] bucketList = CreateHashedArray(arrayToSort, 10);
            //sort the bucket list back into the original array
            ReorderList(bucketList, arrayToSort);
            return arrayToSort;
        }

        private int hashFunction(int num, int buckets)
        {
            return num / buckets;
        }

        private List<int>[] CreateHashedArray(int[] arrayToSort, int buckets)
        {
            List<int>[] bucketList;

            //get min and max of array
            int min = arrayToSort[0];
            int max = arrayToSort[0];
            foreach (int num in arrayToSort)
            {
                if (num < min) min = num;
                if (num > max) max = num;
            }

            //create linkedlist of buckets
            int bucketSize = (max - min) / buckets + 1;
            bucketList = new List<int>[bucketSize];
            foreach (int num in arrayToSort)
            {
                int hash = hashFunction(num, buckets);
                if (bucketList[hash] == null)
                {
                    bucketList[hash] = new List<int>();
                }
                bucketList[hash].Add(num);
            }
            return bucketList;
        }

        int reorderPosition = 0;
        private int[] ReorderList(List<int>[] buckets, int[] originalArray)
        {
            foreach (List<int> lst in buckets)
            {
                if (lst != null && lst.Count > 0)
                {
                    List<int> innerList = InsertionSort.Sort(lst);

                    for (int innerCounter = 0; innerCounter < lst.Count; innerCounter++)
                    {
                        originalArray[reorderPosition] = innerList[innerCounter];
                        reorderPosition++;
                    }
                }
            }
            return originalArray;
        }
    }
}

Popular posts from this blog

Heap Sort

Binary Search