Algorithmes de tri

Tri par sélection

Complexité : \( C_n = \mathcal{O}(n^2) \) où \( n \) désigne la taille de l

let rec extrait_minimum l = match l with
  | [] -> failwith "Pas de minimum"
  | [a] -> (a, [])
  | p::q -> let (min_q, reste_q) = extrait_minimum q in
    if p < min_q then (p, min_q::reste_q) else (min_q, p::reste_q)

let rec tri_selection l = match l with
  | [] -> []
  | [a] -> [a]
  | _ -> let min, reste = extrait_minimum l in
    min::(tri_selection reste)

void tri_selection(int tab[], int taille_tab) {
  for (int i = 0; i < taille_tab; i += 1) {
    int imin = i;
    for (int j = i; j < taille_tab; j += 1) {
      if (tab[j] < tab[imin]) {
        imin = j;
      }
    }
    int tmp = tab[i];
    tab[i] = tab[imin];
    tab[imin] = tmp;
  }
}

Tri à bulles

Complexité : \( C_n = \mathcal{O}(n^2) \) où \( n \) désigne la taille de l

let rec un_tour l = match l with
  | [] -> []
  | [p] -> [p]
  | p1::p2::q -> if p1 < p2 then p1::(un_tour p2::q) else p2::(un_tour p1::q)

let rec tri_a_bulle l = let apres_un_tour = un_tour l in if l = apres_un_tour then l else tri_bulles apres_un_tour

void tri_a_bulles(int tab[], int taille_tab){
  for (int i = 0; i < taille_tab; i += 1){
    for (int j = 0; j < taille_tab - i - 1; j += 1){
      if (tab[j + 1] < tab[j]){
        int tmp = tab[j];
        tab[j] = tab[j + 1];
        tab[j + 1] = tmp;
      }
    }
  }
}

Tri par insertion

Complexité : \( C_n = \mathcal{O}(n^2) \) où \( n \) désigne la taille de l

let rec insere l e = match l with
  | [] -> [e]
  | p::q -> if e < p then e::p::q else p::(insere q e)

let tri_insertion l = match l with
  | [] -> []
  | p::q -> insere (tri_insertion q) p

void tri_insertion(int tab[], int taille_tab){
    for (int i = 0; i < taille_tab; i += 1){
        int j = i;
        while (j > 0 && tab[j] < tab[j - 1]){
            int temp = tab[j];
            tab[j] = tab[j - 1];
            tab[j - 1] = temp;
            j -= 1;
        }
    }
}

Tri fusion

Complexité : \( C_n = \mathcal{O}(n\log(n)) \) où \( n \) désigne la taille de l

Sur des listes

let diviser l =
  let rec aux l l1 l2 = match l with
    | [] -> (l1, l2)
    | h::[] -> (h::l1, l2)
    | h1::h2::q -> aux q (h1::l1) (h2::l2)
  in
  aux l [] []

let rec fusion l1 l2 = match l1, l2 with
  | [], [] -> failwith "PAS POSSIBLE"
  | [], a | a, [] -> a
  | h1::q1, h2::q2 ->
    if h1 < h2 then h1::(fusion q1 (h2::q2))
    else h2::(fusion (h1::q1) q2)

let rec tri_fusion l = match l with
  | [] | [_] -> l
  | _ ->
    let tri1, tri2 = diviser l in
    fusion (tri_fusion tri1) (tri_fusion tri2)

void divise(liste l, liste* pairs, liste* impairs){
    if (!est_vide(l)){
        ajoute(tete(l), pairs);
        if (!est_vide(queue(l))){
            ajoute(tete(queue(l)), impairs);
            divise(queue(queue(l)), pairs, impairs);
        }
    }
}

liste fusion(liste l1, liste l2){
    if (est_vide(l1)){
        return copie(l2);
    }
    else if (est_vide(l2)){
        return copie(l1);
    }
    else{
        liste res;
        if (tete(l1) < tete(l2)){
            res = fusion(queue(l1), l2);
            ajoute(tete(l1), &res);
        }
        else{
            res = fusion(l1, queue(l2));
            ajoute(tete(l2), &res);
        }
        return res;
    }
}

liste tri_fusion(liste l){
    if (est_vide(l) || est_vide(queue(l))){
        return copie(l);
    }
    else{
        liste temp1 = creer ();
        liste temp2 = creer ();
        divise(l, &temp1, &temp2);
        liste tri1 = tri_fusion(temp1);
        liste tri2 = tri_fusion(temp2);
        liste res = fusion(tri1, tri2);
        detruire(temp1);
        detruire(temp2);
        detruire(tri1);
        detruire(tri2);
        return res;
    }
}

Sur des tableaux

let sous_tableau a i j =
  let res = Array.make (j - i + 1) a.(0) in
  for k = i to j do
    res.(k - i) <- a.(k)
  done;
  res

let fusion_tableaux a1 a2 =
  let s1 = Array.length a1 in
  let s2 = Array.length a2 in
  let res = Array.make (s1 + s2) a1.(0) in
  let i = ref 0 in
  let j = ref 0 in
  for k = 0 to s1 + s2 - 1 do
    if !j >= s2 || (!i < s1 && a1.(!i) < a2.(!j)) then 
      begin 
      res.(k) <- a1.(!i);
      incr i;
      end
    else
      begin
      res.(k) <- a2.(!j);
      incr j
      end
  done;
  res

let rec tri_fusion_tableaux a =
  let s = Array.length a in
  if s = 0 || s = 1 then a
  else
    let tri1 = sous_tableau a 0 (s/2 - 1) in
    let tri2 = sous_tableau a (s/2) (s - 1) in
    fusion_tableaux (tri_fusion_tableaux tri1) (tri_fusion_tableaux tri2)

int* sous_tableau(int a[], int i, int j){
    int* res = malloc((j - i + 1) * sizeof(int));
    for (int k = i; k < j + 1; k += 1){
        res[k - i] = a[k];
    }
    return res;
} 

int* fusion_tableaux(int a1[], int a2[], int s1, int s2){
    int* res = malloc((s1 + s2) * sizeof(int));
    int i = 0;
    int j = 0;
    for (int k = 0; k < s1 + s2; k += 1){
        if (j >= s2 || (i < s1 && a1[i] < a2[j])){
            res[k] = a1[i];
            i += 1;
        }
        else{
            res[k] = a2[j];
            j += 1;
        }
    }
    return res;
}

int* tri_fusion_tableaux(int a[], int s){
    if (s == 0){
        return NULL;
    }
    else if (s == 1){
        int* res = malloc(sizeof(int));
        res[0] = a[0];
        return res;
    }
    else {
        int* temp1 = sous_tableau(a, 0, s/2 - 1);
        int* temp2 = sous_tableau(a, s/2, s - 1);
        int* tri1 = tri_fusion_tableaux(temp1, s/2);
        int* tri2 = tri_fusion_tableaux (temp2, s - s/2);
        int* res = fusion_tableaux(tri1, tri2, s/2, s - s/2);
        free(temp1);
        free(temp2);
        free(tri1);
        free(tri2);
        return res;
    }
}

Tri rapide

Complexité : \( C_n = \mathcal{O}(n^2) \) mais \( \Theta(n\log(n))\) où \( n \) désigne la taille de l

Sur des listes

let partition l p =
  let rec aux l l1 l2 = match l with
    | [] -> (l1, l2)
    | h::t ->
      if h < p then aux t (h::l1) l2
      else aux t l1 (h::l2)
  in
  aux l [] []

let rec tri_rapide l = match l with
  | [] -> []
  | h::t ->
    let tri1, tri2 = partition t h in
    (tri_rapide tri1)@(h::(tri_rapide tri2))

void partition(liste l, int pivot, liste* inf, liste* sup){
    if (!est_vide(l)){
        if (tete(l) < pivot){
            ajoute(tete(l), inf);
        }
        else{
            ajoute(tete(l), sup);
        }
        partition(queue(l), pivot, inf, sup);
    }
}

liste tri_rapide(liste l){
    if (est_vide(l)){
        return creer();
    }
    else{
        liste temp1 = creer ();
        liste temp2 = creer ();
        partition(queue(l), tete(l), &temp1, &temp2);
        liste tri1 = tri_rapide(temp1);
        liste tri2 = tri_rapide(temp2);
        ajoute(tete(l), &tri2);
        liste res = concat(tri1, tri2);
        detruire(temp1);
        detruire(temp2);
        detruire(tri1);
        detruire(tri2);
        return res;
        
    }
}

Sur des tableaux

let partition a deb fin =
  let k = ref deb in
  let pivot = a.(fin) in
  for i = deb to fin - 1 do
    if a.(i) < pivot then
      begin
      let temp = a.(i) in
      a.(i) <- a.(!k);
      a.(!k) <- temp;
      incr k
      end
  done;
  let temp = a.(fin) in
  a.(fin) <- a.(!k);
  a.(!k) <- temp;
  !k

let rec tri_rapide_aux a deb fin = 
  let k = partition a deb fin in
  if k > deb then tri_rapide_aux a deb (k-1);
  if k < fin then tri_rapide_aux a (k+1) fin

let tri_rapide a = tri_rapide_aux a 0 (Array.length a - 1)

int partition_lomuto(int t[], int debut, int fin){
    int k = debut;
    int pivot = t[fin];
    for (int i = debut; i < fin; i += 1){
        if (t[i] < pivot){
            int temp = t[i];
            t[i] = t[k];
            t[k] = temp;
            k += 1;
        }
    }
    int temp = t[fin];
    t[fin] = t[k];
    t[k] = temp;
    return k;
}

void tri_rapide_aux(int tab[], int debut, int fin){
    int k = partition_lomuto(tab, debut, fin);
    if (k > debut){
        tri_rapide_aux(tab, debut, k-1);
    }
    if (k < fin){
        tri_rapide_aux(tab, k+1, fin);
    }
}

void tri_rapide(int tab[], int taille_tab){
    tri_rapide_aux(tab, 0, taille_tab - 1);
}