Friday, July 15, 2011

Sort algorithm implementations and comparison

I implemented several sorting algorithms: bubble, insertion, selection, bucket, quick, and merge. I generated a random int[] and passed it to each sort. The sorts first created a local copy of the array, and then performed sort. I used NetBeans profiler on various input sizes to compare the speeds.


Comparison from NetBeans profiler
1. Elements =  1,000, Variation = 100,000,000

2. Elements = 10,000, Variation = 100,000,000







3. Elements = 100,000 Variation = 100,000,000, I left out Selection() and Bubble() because they were so much worse than the others that they made it hard to see the results





4. Elements = 100,000 Variation = 10,000




Conclusion
Timewise, with large variation in the data Quicksort is the fastest, while with small variation Bucketsort is the fastest. Spacewise, Insertion/Selection/Bubble are all better, whereas Quick/Merge recurse, therefore creating a tree in memory, meanwhile Bucket sort creates an extra array for the buckets, whose size depends on the variation in the data. So when choosing which sort algorithm to use you should compare time and space complexity based on your expected # elements and variation in data values.


Implementation

In Main
       int[] arr = getRandomArray(1000);
       Sorts s = new Sorts(arr);
          s.Merge();
          s.Quick();
          s.Selection();
          s.Insertion();
          s.Bubble();
          s.Bucket();
In Sorts.java
public class Sorts {
    private int[] arr;
    public Sorts(int[] arr)
    {
        this.arr = arr;
    }
  
    public int[] Insertion()
    {
        int[] a = copy();
      
        for(int i = 1; i < a.length; i++)
        {
            int tmp = a[i];
            int j = i - 1;
            while(j >= 0 && a[j] > tmp)
                a[j + 1] = a[j--];
            a[j + 1] = tmp;
        }
        return a;
      
    }
    public int[] Selection()
    {
        int[] a = copy();
        for(int i = 0; i < a.length; i++)
        {
            int minIdx = i;
            for(int j = i + 1; j < a.length; j++)
            {
                if(a[j] < a[minIdx])
                    minIdx = j;
            }
            int tmp = a[i];
            a[i] = a[minIdx];
            a[minIdx] = tmp;
        }
        return a;
    }
    public int[] Bubble()
    {
        int[] a = copy();
        for(int i = 0; i < a.length; i++)
        {
            for(int j = 0; j < a.length - 1; j++)
            {
                if(a[j] > a[j + 1])
                {
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                }
            }
        }
        return a;
    }
    public int[] Bucket()
    {
        /*
         * Create a bucket array with minimized number of
         * buckets, which is Minimum Value to Maximum Value
         * use the minimum value as an offset
         *
         * For example,
         * [8][5][3][4][7][3][6][4][5][6]
         * min = 3, max = 8
         * So at most we need 6 buckets (8 - 3 + 1 = 6)
         * and 3 is the offset, so every value is stored in Value - 3
         *
         */
        int[] a = copy();
      
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int m = 0; m < a.length; m++)
        {
            max = Math.max(max, a[m]);
            min = Math.min(min, a[m]);
        }
        //Create bucket with minimized number of buckets
        int[] buckets = new int[max - min + 1];
      
        //Put integers into buckets
        for(int i = 0; i < a.length; i++)
            buckets[a[i] - min]++;
      
        //output the buckets
        int index = 0;
        for(int b = 0; b < buckets.length; b++)
        {
            for(int k = 0; k < buckets[b]; k++)
            {
                a[index++] = b + min;
            }
        }
        return a;
    }
    public int[] Merge()
    {
        int[] a = copy();
        mergesort(a, new int[a.length], 0, a.length - 1);
        return a;
    }
    private void mergesort(int[] a, int[] helper, int left, int right)
    {
        if(left >= right)
            return;
        int mid = (left + right)/2;
        mergesort(a, helper, left, mid);
        mergesort(a, helper, mid + 1, right);
      
        //merge results
        int leftPos = left,
                leftEnd = mid,
                rightPos = leftEnd + 1,
                rightEnd = right,
                tmpPos = left;
        while(leftPos <= leftEnd || rightPos <= rightEnd)
        {
            if(leftPos <= leftEnd && rightPos <= rightEnd)
            {
                if(a[leftPos] < a[rightPos])
                    helper[tmpPos++] = a[leftPos++];
                else
                    helper[tmpPos++] = a[rightPos++];
            }
            else if (leftPos <= leftEnd)
                helper[tmpPos++] = a[leftPos++];
            else
                helper[tmpPos++] = a[rightPos++];
        }
        //copy back into a
        for(int i = left; i <= right; i++)
            a[i] = helper[i];
      
    }
    public int[] Quick()
    {
        int[] a = copy();
        quick(a, 0, a.length - 1);
        return a;
    }
    private void quick(int[] a, int left, int right)
    {
        int pivot = (left + right)/2;
        int pivotVal = a[pivot];
        int i = left;
        int j = right;
        while(i <= j)
        {
            while(a[i] < pivotVal)
                i++;
            while(a[j] > pivotVal)
                j--;
            if(i > j)
                break;
            int tmp = a[j];
            a[j] = a[i];
            a[i] = tmp;
            i++;
            j--;
          
        }
        if(left < i - 1)
            quick(a, left, i - 1);
        if(right > i)
            quick(a, i, right);
      
    }
    private int[] copy()
    {
        int[] copyarr = new int[arr.length];
        System.arraycopy(arr, 0, copyarr , 0, arr.length);
        return copyarr;
    }
    public boolean same(int[] a, int[] b)
    {
        if(a.length != b.length)
            return false;
        for(int i = 0; i < a.length; i++)
        {
            if(a[i] != b[i])
                return false;
        }
        return true;
    }
}

No comments:

Post a Comment

There was an error in this gadget