tri_rapide.c

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include "tri_rapide.h"


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

void sousTriRapide(long* A, size_t first, size_t size, int version){
    if(first+1 < size){
        size_t middle = partition(A,first,size, version);
        sousTriRapide(A,first,middle, version);
        sousTriRapide(A,middle+1,size, version);
    }
}

size_t partition(long* A, size_t first, size_t size, int version) {
    //long middle = (size-1) / 2;
    //long pivot = A[middle];

    long pivot = A[size-1];

    size_t i = first;
    for(int j = first; j+2 <= size; j++){
        if(A[j] <= pivot) {
            // Version 1: optimisation sur les tableaux ranges
            if(version == 1) {
              // Si i = j, pas besoin de permuter
              if(i != j ) {
                permuter(A,i,j);
              }
            }
            // Version 0: celle de base
            else {
              permuter(A,i,j);
            }

            i++;
        }
    }
    permuter(A,i,size-1);
    return i;
}

void permuter(long* A,size_t i,size_t j) {
    long inter = A[i];
    A[i] = A[j];
    A[j] = inter;
}