quicksort - liczniki

pytanie zadane 7 czerwca 2018 w C i C++ przez kikosiak Obywatel (1,010 p.)

Cześć mam pytanie. Czy liczniki które mam w kodzie dobrze liczą ilość zamian i porównań?

int counter,changes;

void quicksortMW(int_array_type array, int low, int high)
{
    if(low<high) {
        int partition_index = partitionMW(array,low,high);
        quicksortMW(array, low, partition_index);
        quicksortMW(array, partition_index+1, high);
    }
}

int partitionMW(int_array_type array, int low, int high)
{
    int pivot = array[low];
    int i = low-1, j = high+1;

    while(i<j) {
        while(array[--j]>pivot)
           ;
        while(array[++i]<pivot)
            ;counter++;
        if(i<j){
            swap(&array[i],&array[j]);
            changes++;

        }
    }
    return j;
}

1 odpowiedź

odpowiedź 7 czerwca 2018 przez RafalS VIP (122,820 p.)

if(low<high)

To też jest porównanie.

while(array[--j]>pivot)
           ;
while(array[++i]<pivot)
            ;

To są porównania (wielokrotne).

        while(array[++i]<pivot)
            ;counter++;

mam nadzieje, że wiesz ze ten counter nie jest inkrementowany przez pętlę pod którą się znalazł tylko przez pętlę zewnętrzną, czyli liczy tylko jej porównania.

if(i<j){

To też jest porównanie.

komentarz 7 czerwca 2018 przez kikosiak Obywatel (1,010 p.)

Czyli ma być tak?

void quicksortMW(int_array_type array, int low, int high)
{
    if(low<high) {
            counter++;
        int partition_index = partitionMW(array,low,high);
        quicksortMW(array, low, partition_index);
        quicksortMW(array, partition_index+1, high);
    }
}

int partitionMW(int_array_type array, int low, int high)
{
    int pivot = array[low];
    int i = low-1, j = high+1;

    while(i<j) {
        while(array[--j]>pivot)
           counter++;
        while(array[++i]<pivot)
            counter++; counter++;
        if(i<j){
            swap(&array[i],&array[j]);
            changes++;

        }
    }
    return j;
}