0

With the Introduction to algorithm .The Professor intro that the random quick sort can decrease the percentage of bad situation and improve the performance of time cost.But I wonder if there any problem with my code that cause the result in contrast. Here are my java code

public class quickSort {
    public final int size = 200000;
    public final int times = 10;

    @Test
    public void quick_sort() {
        int test1[] = new int[size];
        int test2[];
        int k = 0;

        long t1 = 0;
        long t2 = 0;

        for (int i = 0; i < size; i++) {
            test1[i] = i;
        }
        test2 = test1.clone();
        while (k < times) {

            shuffle(test1);
            shuffle(test2);
             long start1 = System.currentTimeMillis();
             split1(test1, 0, test1.length -1);
             t1 += System.currentTimeMillis() - start1;

            long start2 = System.currentTimeMillis();
            split2(test2, 0, test2.length -1);
            t2 += System.currentTimeMillis() - start2;
            k++;
        }

        System.out.println("normal quick sort time is" + t1 + "ms");
        System.out.println("random quick sort time is " + t2 + "ms");
    }

    public void split1(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        } else {
            int middle = sort(arr, start, end);
            split1(arr, start, middle - 1);
            split1(arr, middle + 1, end);
        }
    }

    public void split2(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        } else {
            int middle = random_sort(arr, start, end);
            split2(arr, start, middle - 1);
            split2(arr, middle + 1, end);
        }
    }

    // random quick sort
    public int random_sort(int[] arr, int start, int end) {

        int random = start + new Random().nextInt(end - start + 1);
        int key = arr[random];
        int loop = start;
        int front = random == start ? start + 1 : start;

        while (loop <= end) {
            if (loop == random) {
                loop++;
                continue;
            }
            if (arr[loop] < key) {
                int temp = arr[loop];
                arr[loop] = arr[front];
                arr[front] = temp;
                front = front + 1 == random ? front += 2 : front + 1;
            }
            loop++;
        }
        if (front < end) {

            int temp = arr[random];
            arr[random] = arr[front];
            arr[front] = temp;
        } else {
            front = end;
        }

        return front;
    }

    // normal quick sort
    public int sort(int[] arr, int start, int end) {
        int loop = start;

        int key = arr[start];
        int front = start + 1;
        while (loop <= end) {

            if (key > arr[loop]) {
                int temp = arr[loop];
                arr[loop] = arr[front];
                arr[front++] = temp;
            }

            loop++;
        }
        if (front != 1) {
            int temp = arr[front - 1];
            arr[front - 1] = arr[start];
            arr[start] = temp;
        }
        return front - 1;
    }

    // shuffle the Array
    public void shuffle(int[] arr) {
        int length = arr.length;
        int random_num = 0;
        for (int i = 0; i < length; i++) {
             random_num = new Random().nextInt(length);
            int temp = arr[i];
            arr[i] = arr[random_num];
            arr[random_num] = temp;
        }
    }

}
Jason Long
  • 79
  • 1
  • 12
  • 1
    [Obligatory link](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). – Andy Turner May 25 '16 at 12:18
  • What happens if you don't shuffle `test1`? – Clark Kent May 25 '16 at 12:27
  • @ClarkKent stack overflow....Why?But if i decrease the length of the Array ,The random quick sort is really quick than the normal sort!! It's really three times performance!But how does the stack overflow if does't excute the shuffle??? – Jason Long May 25 '16 at 12:32
  • I haven't done quicksort in years, but IIRC, quicksort's worst case is `O(n^2)` because of what it chooses for its pivot in the event that the data is sorted in either forward or reverse order. When you randomize the pivot location or shuffle the array before running quicksort, it becomes an amortized `O(n lg n)`. – Clark Kent May 25 '16 at 12:35
  • @ClarkKent I am know that.But why does the jvm stackoverflow without shuffle Array?There is a new question appear... Only the wrose situation the random quick win...I confused than before....; – Jason Long May 25 '16 at 12:37
  • Because the data is already sorted, I'm guessing that in your sort, the value of `middle` is incrementing sequentially, causing up to 200,000 frames of activation to be added to the stack. – Clark Kent May 25 '16 at 12:38
  • @ClarkKent yeah,Stack overflow because the to many frame,but Once shuffle , the problem dismiss! It's to strange! – Jason Long May 25 '16 at 12:47
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/112917/discussion-between-clark-kent-and-jason-long). – Clark Kent May 25 '16 at 12:48

0 Answers0