Add to Favorites    Make Home Page 3355 Online  
 Language Categories  
 Our Services  

Java Data Structures - Contents


Optimizing Quicksort...

A D V E R T I S E M E N T

Search Projects & Source Codes:

    Optimizing Quicksort written in Java is not such a great task. Whatever tricks we use, we will still be restrained by the speed of the Java Virtual Machine (JVM). In this section, we will talk about algorithmic improvements, rather than quirky tricks.

    The first thing what we should do is look at the above code of the un-optimized sort, and see what can be improved. One thing that should be obvious is that it's way too much work if the array is very small. There are a LOT simpler sorts available for small arrays. For example, simple insertion sort has almost no overhead, and on small arrays, is actually faster than quicksort! This can be fixed rather easily, by including an if statement to see if the size of the array is smaller than some particular value, and doing a simple insertion sort if it is. This threshold value can only be determined from doing actual experiments with sample data. However, usually any value less than 15 is pretty good; and that is why we will choose 7 for our upcoming example.

    What makes quicksort so fast is the simplicity of it's inner loops. In our previous example, we were doing extra work in those inner loops! We were checking for the array bounds; we should have made some swaps beforehand to make sure that the inner loops are as simple as possible. Basically, the idea is to make sure that the first element in the array is less than or equal to the second, and that the second is less than or equal to the last. Knowing that, we can remove those array bounds checking from the inner loops (in some cases speeding up the algorithm by about two times).

    Another thing that should be obvious is recursion. Because sort methods are usually very performance hungry, we would like to remove as much function calls as possible. This includes getting rid of recursion. The way we can get rid of recursion is using a stack to store the upper and lower bounds of arrays to be sorted, and using a loop to control the sort.

    A question automatically arises: How big should that stack be? A simple answer is: It should be big enough. (you'll be surprised how many books avoid this topic!) We cannot just use java.util.Vector object for it's dynamic growing ability, since that would be way too much overhead for simple stack operations that should be as quick as possible. Now, what would be a big enough stack? Well, a formula below calculates the size:

size = 2 * ln N / ln 2

    Where ln is natural logarithm, and N is the number of elements in the array. Which all translates to:

size = (int)(Math.ceil(2.0*Math.log(array.length)/Math.log(2.0));

    Believe it or not, but it's actually not worth using this equation. If you think about it, you will notice that the size of the stack grows VERY slowly. For example, if the array.length is 0xFFFFFFFF in length (highest 32 bit integer value), then size will be 64! We will make it 128 just in case we will ever need it for 64 bit integers. (If you don't like magic values inside your program, then by all means, use the equation.)

    Having gotten to this point, we are almost ready to implement our optimized version of quicksort. I say almost because it is still not optimized to it's fullest. If we were using native types instead of Comparable objects, then the whole thing would be faster. If we implementing it as native code, it would be even faster. Basically, most other speed-ups are left up to these system or program specific quirky optimizations. And now, here's our optimized version:

import java.lang.*;
import java.io.*;

public class pQuicksort{

    public static void sort(Comparable[] c){
        int i,j,left = 0,right = c.length - 1,stack_pointer = -1;
        int[] stack = new int[128];
        Comparable swap,temp;
        while(true){
            if(right - left <= 7){
                for(j=left+1;j<=right;j++){
                    swap = c[j];
                    i = j-1;
                    while(i>=left && c[i].compareTo(swap) > 0)
                        c[i+1] = c[i--];
                    c[i+1] = swap;
                }
                if(stack_pointer == -1)
                    break;
                right = stack[stack_pointer--];
                left = stack[stack_pointer--];
            }else{
                int median = (left + right) >> 1;
                i = left + 1;
                j = right;
                swap = c[median]; c[median] = c[i]; c[i] = swap;
                /* make sure: c[left] <= c[left+1] <= c[right] */
                if(c[left].compareTo(c[right]) > 0){
                    swap = c[left]; c[left] = c[right]; c[right] = swap;
                }if(c[i].compareTo(c[right]) > 0){
                    swap = c[i]; c[i] = c[right]; c[right] = swap;
                }if(c[left].compareTo(c[i]) > 0){
                    swap = c[left]; c[left] = c[i]; c[i] = swap;
                }
                temp = c[i];
                while(true){
                    do i++; while(c[i].compareTo(temp) < 0);
                    do j--; while(c[j].compareTo(temp) > 0);
                    if(j < i)
                        break;
                    swap = c[i]; c[i] = c[j]; c[j] = swap;
                }
                c[left + 1] = c[j];
                c[j] = temp;
                if(right-i+1 >= j-left){
                    stack[++stack_pointer] = i;
                    stack[++stack_pointer] = right;
                    right = j-1;
                }else{
                    stack[++stack_pointer] = left;
                    stack[++stack_pointer] = j-1;
                    left = i;
                }
            }
        }
    }

    public static void main(String[] args){
        int i;
        Integer[] arr = new Integer[20];
        System.out.println("inserting: ");
        for(i=0;i<arr.length;i++){
            arr[i] = new Integer((int)(Math.random()*99));
            System.out.print(arr[i]+" ");
        }
        pQuicksort.sort(arr);
        System.out.println("\nsorted: ");
        for(i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
        System.out.println("\nDone ;-)");
    }
}

    The output closely follows:

inserting:
17 52 88 79 91 41 31 57 0 29 87 66 94 22 19 30 76 85 61 16
sorted:
0 16 17 19 22 29 30 31 41 52 57 61 66 76 79 85 87 88 91 94
Done ;-)

    This new sort function is a bit larger than most other sorts. It starts out by setting left and right pointers, and the stack. Stack allocation could be moved outside the function, but making it static is not a good choice since that introduces all kinds of multithreading problems.

    We then fall into an infinite loop in which we have an if() and an else statement. The if() statement finds out if we should do a simple insertion sort, else, it will do quicksort. I will not explain insertion sort here (since you should already be familiar with it). So, after insertion sort, we see if the stack is not empty, if it is, we break out of the infinite loop, and return from the function. If we don't return, we pop the stack, set new left and right pointers (from the stack), and continue on with the next iteration of the loop.

    Now, if threshold value passed, and we ended up doing quicksort we first find the median. This median is used here to make the case with bad performance less likely to occur. It is useless against random data, but does help if the data is in somewhat sorted order.

    We swap this median with the second value in the array, and make sure that the first value is less than or equal than the second, and the second is less than or equal than the last. After that, we pick our partition element (or pivot), and fall into an infinite loop of finding that pivot's correct place.

    Notice that the most inner loops are fairly simple. Only one increment or decrement operation, and a compare. The compare could be improved quite a bit by using native types; instead of calling a function. The rest of this part of the sort is almost exactly like in the un-optimized version.

    After we find the correct position of the pivot variable, we are ready to continue the sort on the right sub-array, and on the left sub-array. What we do next is check to see which one of these sub-arrays is bigger. We then insert the bigger sub-array bounds on to the stack, and setup new left and right pointers so that the smaller sub-array gets processed next.

    I guess that's it for quicksort. If you still don't understand it, I doubt any other reference would be of any help. Basically go through the algorithm; tracing it a few times, and eventually, it will seem like second nature to you. The above function is good enough for most purposes. I've sorted HUGE arrays (~100k) of random data, and it performed quite well.


Back to Table of Contents


A D V E R T I S E M E N T




Google Groups Subscribe to SourceCodesWorld - Techies Talk
Email:

Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.

 Advertisements  

Google Search

Google

Source Codes World.com is a part of Vyom Network.

Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Interview Questions | Jobs, Discussions | Placement Papers | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | Arabic, French, German | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Software Testing | Google Logo Maker | Freshers Jobs

Sitemap | Privacy Policy | Terms and Conditions
Copyright ©2003-2018 SourceCodesWorld.com, All Rights Reserved.
Page URL: http://www.sourcecodesworld.com/articles/java/java-data-structures/Optimizing_Quicksort.asp


Download Yahoo Messenger | Placement Papers | Free SMS | C Interview Questions | C++ Interview Questions | Quick2Host Review