dimanche 23 février 2020

if v/s while: for this code if I'm using while loop it's continuing for infinite, but when used "if(low

Array: 4,1,5,8,2,6,9,7,11,3

public static void quickSort(int arr[], int low, int high) {
    System.out.println(low + " " + high);
    while(low < high) {
        int mid = quickPart(arr, low, high);            
        quickSort(arr, low, mid - 1);          
        quickSort(arr, mid + 1, high);
    }
}

it's printing: 0 0 then 2 1, then again 0 0 and 2 1 and so on for S.o.pl(low + " " + high)

but for..

public static void quickSort(int arr[], int low, int high) {
    System.out.println(low + " " + high);
    if(low < high) {
        int mid = quickPart(arr, low, high);            
        quickSort(arr, low, mid - 1);          
        quickSort(arr, mid + 1, high);
    }
}

it's printing: 0 9, 0 1, 0 0, 2 1, 3 9, 3 3, 5 9... it's working fine.

partitioning code, if it helps..

public static int quickPart(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for(int j = low; j < high; j++) {
        if(pivot > arr[j]) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    System.out.println(i++);
    return i+1;
}

For if statement, code will terminate as soon as low >= high and for that it is reaching till 9, i.e., 9 > 9 terminate But for while + partitioning algorithm its printing 1 in repetition. Why is it behaving as such?

Aucun commentaire:

Enregistrer un commentaire