Thursday, February 9, 2012

Which sorting algorithm would you choose for guaranteed optimal time performance?

Which sorting algorithm would you choose for guaranteed optimal time performance?
Consider you have a huge array of n elements and you want to sort it in considering time performance, not only in the average case, but also in the worst case. Which sorting algorithm would I choose?

R: I won't go through all sort algorithms, so here my "quick answer": merge sort. Why? Because merge sort is O(n . lg n) not only for the average case, but also in the worst case. In addiction to that, merge sort doesn't replace the same array elements: it is stable.

Here is my Java code snippet. I removed unnecessary code from the picture, but it is shown bellow. Of course I just used a small array, feel free to used with a huge array!


[Java code snippet] Merge sort


package ric.interviewqa4java;

/** © 2012 interviewqa4java.blogspot.com */
public class MyMergeSort {
    static int array[]= {10,6,2,3,11,8,7,10,4,1};
   
    public static void main(String[] args) {       
        printlnArray("Original array = ");
        mergeSort(0, array.length-1);
        printlnArray("Sorted array   = ");
    }
   
    private static void mergeSort(int low, int high) {
        if(low<high){
            int middle = (low+high)/2;
            mergeSort(low, middle);
            mergeSort(middle+1, high);
            merge(low, middle, high);
        }// if i==j, the sub-list has 1 element, then it's considered sorted
    }
   
    private static void merge(int low, int middle, int high) {
       
        int tempArray[] = new int[high-low+1];
       
        //Compare members in each sublists in the the extreme left;
            //the smaller element is "removed" and
            //stored in a temporary list that will be an ordered list after the loop
        for(int i=low, j=middle+1, k=0; (i <= middle) || (j <= high); k++){
            if(i > middle){//all members in the left list were used
                tempArray[k] = array[j++];
            }
            else if (j > high){ //all member in the right list were used
                tempArray[k] = array[i++];
            }
            else if(array[i] <= array[j]){
                tempArray[k] = array[i++];
            }else{
                tempArray[k] = array[j++];
            }
        }
        //apply changes
        int index=low;
        for (Integer value : tempArray) {
            array[index++] = value;
        }
    }
   
    //Auxiliary method to print the array
    private static void printlnArray(String message) {
        StringBuffer arrayStr =  new StringBuffer(message+"[");
        for (int i = 0; i < array.length; i++) {
            arrayStr.append(array[i]);
            if(i < array.length-1){ arrayStr.append(", "); }
        }
        arrayStr.append("]");
        System.out.println(arrayStr);
    }
}

No comments:

Post a Comment

Please, before starting to comment, evaluate if what you want to write is useful, respectful and positive. A kid may read this also.

Give a good example!