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