jeudi 26 octobre 2017

Random Sort does not terminate

Assuming isAscSorted functions as expected (tested) I am doing something silly here which is why random swap never sorts the array - because it is only ever doing 1 swap each time on different arrays?

My test case is int[] values1 = new int[] { 50, 10, 20, 4, 5, 1, 5 };

Hints?

public static boolean isAscSorted (int[] arr){

    for (int i=0; i<arr.length-1; i++){
        if (arr[i]> arr[i+1]){
            return false;
        }
    }
    return true;
}


public static boolean swap(int[]a,int i,int j)
{
    if (i == j){
        return false;
    }
    int temp=a[i];
    a[i]= a[j];
    a[j]=temp;
    return true;

 }


static int randomSort(int[] values) {

    //Ok Array is empty or null
    if( values == null || values.length==0){
        return 0;
    }

    boolean isSorted = false;
    int steps = 0;
    Random r = new Random();
    int limit = values.length-1;


    while (!isAscSorted(values)){
        //choose 2 random positions
        int r1 = r.nextInt(limit);
        int r2 = r.nextInt(limit);

        //swap returns true if successful
        boolean swapRes = swap(values, r1,r2);

        //increment steps counter
        if (swapRes)
            steps++;

    }

    return steps;
}




Aucun commentaire:

Enregistrer un commentaire