Qfyilyi

I am following the following pseudocode:

function quicksort(array)

    if length(array) > 1

        pivot := select any element of array

        left := first index of array

        right := last index of array

        while left ≤ right

            while array[left] < pivot

                left := left + 1

            while array[right] > pivot

                right := right - 1

            if left ≤ right

                swap array[left] with array[right]

                left := left + 1

                right := right - 1

        quicksort(array from first index to right)

        quicksort(array from left to last index)

but when I try to implement it in java, I insert code:

import java.util.Arrays;



public class ALGQuickSort {



public static void main(String args) {

    int array = {6, 3, 4, 8, 9, 10, 1};

    quickSort(array);

    System.out.println(Arrays.toString(array));

}



public static void quickSort(int array) {

    int pivot = array[array.length - 1];

    if (array.length > 1) {

        int left = 0;

        int right = array.length - 1;

        while (left <= right) {

            while (array[left] < pivot) {

                left++;

            }

            while (array[right] > pivot) {

                right--;

            }

            if (left <= right) {

                swap(array[left], array[right]);

                right--;

                left++;

            }

            int array1 = Arrays.copyOfRange(array, 0, right);

            int array2 = Arrays.copyOfRange(array, left, array.length - 1);

            quickSort(array1);

            quickSort(array2);



        }

    }



}



public static void swap(int a, int b) {

    int aux = a;

    a = b;

    b = aux;

}



}

the system shows me the following error on the screen:

Exception in thread "main" java.lang.IllegalArgumentException: 5 > 4
at java.util.Arrays.copyOfRange(Arrays.java:3591) at
alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:43) at
alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:44) at
alg.quicksort.ALGQuickSort.main(ALGQuickSort.java:21)
C:UsersAlexAppDataLocalNetBeansCache8.2executor-snippetsrun.xml:53:
Java returned: 1

the error is in the line:

int array2 = Arrays.copyOfRange(array, left, array.length - 1);

someone can help me pls?

Improvements/corrections to your quick-sort algorithm:

1. 
   Correct your swap method: The swap method that you are using will not work.


2. 
   The recursive call should be outside the for loop: Your pseudo-code is correct, but in your implementation it is not the case.


3. 
   Place the Pivot at its correct position and then have a recursive call on sub-arrays that now (for-sure) should not contain the pivot element. After the while loop, you are sure that right+1 == left (think on it a bit and you will understand why this is true). Now swap the array[left] with pivot element and give a recursive call on 2 different sub-arrays (left sub-array to the pivot is beginIndex..right and right sub-array to the pivot is left+1..endIndex where I assume that you need to sort array[beginIndex..endIndex])


4. 
   Avoid copying: Its better to avoid copying a part of the array (instead you can pass the startIndex and the endIndex to denote the sub-array you want to sort)


5. 
   Use Randomized Quick sort: It would also be better if you don't always select the last element as your pivot (what you can do here is just before starting to sort select any random element and then swap it with the last element of your array. Using this strategy you don't have to make much changes in your existing code) This selection of random element as pivot is much better. See this link for more details.


6. 
   Make swap method private: Not relevant to the algorithm, but it is good if you make the swap method private as you might not intend to call it from outside of this class.

If you intend to swap the elements of array with index say index1 and index2, then the following code will work:

public static void swap(int array, int index1, int index2) {

    int aux = array[index1];

    array[index1] = array[index2];

    array[index2] = aux;

}

The following is the final code with all the above suggested changes:

public static void main(String args) {

    int array = {6, 30, 7, 23, 4, 8, 9, 10, 1, 90};

    quickSort(array, 0, array.length - 1);

    System.out.println(Arrays.toString(array));

}



public static void quickSort(int array, int beginIndex, int endIndex) {

    // System.out.println("called quick sort on the following : " + beginIndex + " " + endIndex);

    int arrayLength = endIndex - beginIndex + 1;

    int pivot = array[endIndex];

    if (arrayLength > 1) {

        int left = beginIndex;

        int right = endIndex - 1;

        while (left <= right) {

            // System.out.println(left + " " + right);

            while (left <= endIndex && array[left] < pivot) {

                left++;

            }

            while (right >= beginIndex && array[right] > pivot) {

                right--;

            }

            if (left <= right) {

                swap(array, left, right);

                right--;

                left++;

            }



        }

        swap(array, left, endIndex); // this is crucial, and you missed it

        if (beginIndex < right) {

            quickSort(array, beginIndex, right);

        }

        if (left + 1 < endIndex) {

            quickSort(array, left + 1, endIndex);

        }

    }



}



private static void swap(int array, int index1, int index2) {

    int aux = array[index1];

    array[index1] = array[index2];

    array[index2] = aux;

}

Firstly, the two lines

int array1 = Arrays.copyOfRange(array, 0, right);

int array2 = Arrays.copyOfRange(array, left, array.length - 1);

are wrong. You must not copy the arrays. This will prevent the Quicksort algorithm from working since you sort the temporary copies in your recursive calls. The sorted sub arrays will be discarded afterwards.

Another bug in your program raises the exception: the third parameter of Arrays.copyOfRange is exclusive. I.e. it will not copy elements from to to but from to to - 1. But you already subtracted one from the upper bound, and in Quicksort it might happen that one of the sub arrays has zero size. In this case the range to copy becomes negative. That's the exception.

There is a third bug: you swapped the first two lines of the pseudo code. This will crash on empty arrays.

Finally, you cannot implement the Quicksort algorithm in this way as shown in the pseudo code because Java (unlike e.g. C) does not support array slices.

You need to modify the algorithm in a way that you split it into two methods:

• 
  

  One method to recursively sort an array slice:
  
  Note that I replaced the array start and end by from and to.

  
  
  

  public static void quickSort(int array, int from, int to) {
  
    if (array.length <= 1)
  
      return;
  
    int pivot = array[to];
  
    int left = from;
  
    int right = to;
  
    while (left <= right) {
  
      while (array[left] < pivot)
  
        left++;
  
      while (array[right] > pivot)
  
        right--;
  
      if (left <= right) {
  
        swap(array[left], array[right]);
  
        right--;
  
        left++;
  
      }
  
      quickSort(array, from, right);
  
      quickSort(array, left, to);
  
    }
  
  }
  
  

  
  


• 
  

  And a second method to sort an entire array that calls the above one for the entire array.

  
  
  

  public static void quickSort(int array) {
  
    return quickSort(array, 0, array.length - 1);
  
  }