QuickSelect нулевые проблемы - PullRequest
Новая
       21

QuickSelect нулевые проблемы

0 голосов
/ 04 мая 2020 
import java.lang.reflect.Array; 

public class Sorting {

        public static CompareInt quickSelect(int k, CompareInt[] arr) {
        //TODO
        return quickSort(arr,0,arr.length-1,k);

    }

    public static CompareInt quickSort(CompareInt[] arr,int startI,int endI,int k){
        if(startI>=endI)
            return arr[startI];

        int pivLoc = partition(arr,startI,endI);
        if(pivLoc == k)
            return arr[k];
        else if(pivLoc>k)
            return quickSelect(arr,startI,pivLoc-1,k);
        else 
            return quickSelect(arr,pivLoc+1,endI,k-pivLoc+1);

    }

    public static CompareInt quickSelect(CompareInt[] arr,int startI,int endI,int k){

        for(int i=startI;i<endI;i++){
            if(arr[i].val==k)
                return arr[i];
        }
        return null;
    }

    public static int partition(CompareInt[] arr,int low,int high){
        int pivotIndex = (int)(Math.random()*(high-low)) + low;
        //int pivotIndex = (int)(Math.random()*high-1);
        //pivotIndex = pivotIndex.nextInt(high-1);
        //System.out.println("pivotIndex"+pivotIndex);
        //nextInt num.nextInt( 10 );
        // int rand = (int)(Math.random() * range) + min;
        CompareInt var1 = arr[pivotIndex];
        arr[pivotIndex] = arr[arr.length-1];
        arr[arr.length-1] = var1;

        pivotIndex = arr[high].val;

        int i=low,j=high;
        CompareInt[] newArr = new CompareInt[arr.length];

        for(int k=low;k<high-1;k++){
            if(arr[k].val <= pivotIndex){
                newArr[i++] = arr[k];
            }else{
                newArr[j--] = arr[k];
            }
        }

        newArr[i]=arr[high];

         for(int z=low;z<high-1;z++){
            arr[z]=newArr[z];
    }

        return i;
    }    

} 
}

Программа работает, но я не получаю желаемого результата, поскольку получаю каждый раз, когда возвращается ноль.

Код реализован так, как в Псевдокоде:

Я думаю, что Al go является верной ссылкой псевдокода:

Псевдокод

QuickSelect возвращает ноль, если не найдено, что я могу вернуть и как я могу улучшить метод QuickSelect.

...