I'm trying implementing a pseudocode of quicksort that chooses the different elements as pivot, such as first element as pivot, last element as pivot, random element as pivot, and median element as pivot. First i'm working on the first element as pivot, but if the pivot is the greatest number in the array the index will grow to be greater than the length of the array causing an index out of bounds for length. The quicksort implementation works for when the pivot is the first element of the array and the first element of the array is the smallest. The error happens at line 27 when the pivot (in this case) is 8, it will stay at the while([i] < pivot) adding 1 to i.

How can i avoid this?

This is the pseudocode i'm using:

Partition(A, p, r):
pivot ← A[p]`
i ← p   1
j ← r
 while i ≤ j
   while A[i] < pivot
     i ← i   1
   while A[j] > pivot
     j ← j - 1
 if i < j
 swap A[i] with A[j]
swap A[p] with A[j]
return j

And this is my code:

public class QuickSort {
    //this global variable counts the comparisons
    static long countComp = 0;
    
    static void quickSort(int []array, int ft, int lt) {
            
        if(ft < lt) {
                    
            int q = partitionFtE(array, ft, lt);
            quickSort(array, ft, q - 1);
            quickSort(array, q   1, lt);    
        }   
    }   
    //this method does quicksort with first element as pivot, ft = first element, lt = last element
    static int partitionFtE(int []array, int ft, int lt) {          

        int pivot = array[ft];      
        
        int i = ft   1;
        
        int j = lt;
        
        while(i <= j){
            while(array[i] < pivot) {               
                i = i   1;
            }           
            while(array[j] > pivot) {
                j = j - 1;              
            }
            //here we swap elements if i is lower than j
            countComp  ;
            if(i < j) {
                int temp = 0;
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }       
        }
        //here we change the pivot where it suppose to be in the array
        int temp2 = array[i];
        temp2 = array[ft];
        array[ft] = array[j];
        array[j] = temp2;   
        
        return j;   
    }       
    static void printArray(int []array) {
        
        for(int i = 0; i < array.length; i  ) {
            
            System.out.print(array[i]   " ");           
        }
        
        System.out.println("\n"   countComp);
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
    //    int choice = menuData();
       int[] intArray = {8, 7, 6, 5, 4, 3, 2, 1};
       int n = intArray.length;    
        
        quickSort(intArray, 0, n - 1);
        System.out.println("Sorted array: ");
        printArray(intArray);    
    }
}

CodePudding user response：

I used another pseudocode from class to fix this. This is the pseudocode:

//ft is first element, lt is last element
pivot := array[ft]
i := ft   1;

for j:= ft   1 to array length do
  if array[j] < pivot
  swap array[j] and array[i]
swap array[ft] and array[i - 1]
return i -1

And this is the partition method:

static int partition(int []array, int ft, int lt) {
        
        int pivot = array[ft];
        int i = ft   1;
        
        for(int j = ft   1; j < array.length; j   ) {
            if(array[j] < pivot) {
                int temp = 0;
                temp = array[j];
                array[j] = array[i];
                array[i] = temp;
                i = i   1;
            }
        }
        int temp2 = array[ft];
        array[ft] = array[i-1];
        array[i-1] = temp2;
        
        return i - 1;
    }

CodePudding user response：

Example of a post decrementing | incrementing Hoare partition scheme:

void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
    if(lo >= hi)
        return;
    p = a[lo   (hi-lo)/2];
    i = lo;
    j = hi;
    while (i <= j){
        while (a[i] < p)i  ;
        while (a[j] > p)j--;
            if (i > j)
                break;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i  ;
            j--;
    }
    QuickSort(a, lo, j);
    QuickSort(a, i, hi);
}