triRapide.c

#include "triRapide.h"

void sousTriRapide(long* A, size_t p, size_t r) {
    size_t max = 0; max--;
    if(r-1 != max){
        if (p<(r-1)) {
            size_t q = partition(A, p, r);
            sousTriRapide(A, p, q);
            sousTriRapide(A, q+1, r);
        }
    }
    
}

size_t partition(long* A, size_t p, size_t r) {
    long pivot = A[r-1];
    
    size_t i = p;
    for (size_t j = p; j <= r-2; j++) {
        if (A[j] <= pivot) {
            long temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++;
        }
    }
    long temp = A[i];
    A[i] = A[r-1];
    A[r-1] = temp;
    return i;
}

void triRapide(long* A, size_t n) {
    sousTriRapide(A, 0, n);
}

// --------------------------------------------------------

void sousTriRapideVerbose(long* A, size_t p, size_t r, struct data* d) {
    size_t max = 0; max--;
    d->write++;
    if(r-1 != max){
        d->comparison++;
        if (p<(r-1)) {
            d->comparison++;
            size_t q = partitionVerbose(A, p, r, d);
            d->write++;
            sousTriRapideVerbose(A, p, q, d);
            sousTriRapideVerbose(A, q+1, r, d);
        }
    }
    
}

size_t partitionVerbose(long* A, size_t p, size_t r, struct data* d) {
    long pivot = A[r-1];
    d->write++;
    
    size_t i = p;
    d->write++;
    for (size_t j = p; j <= r-2; j++) {
        if (A[j] <= pivot) {
            d->comparison++;
            long temp = A[i];
            d->write++;
            A[i] = A[j];
            d->write++;
            A[j] = temp;
            d->write++;
            i++;
            d->write++;
        }
    }
    long temp = A[i];
    d->write++;
    A[i] = A[r-1];
    d->write++;
    A[r-1] = temp;
    d->write++;
    return i;
}

void triRapideVerbose(long* A, size_t n, struct data* d) {
    sousTriRapideVerbose(A, 0, n, d);
}