Solution du TD d'informatique No. 7 : heapsort

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 8 janvier 2001

1   Tri par tas

public class heapsort {
    public static void ajouter(int [] tableau, int nb, int x) {
 // On suppose nb < tableau.length a l'appel
 tableau[++nb] = x ;
 int i = nb ;
 while (i > 1 && tableau[i] < tableau[i / 2]) {
     int t = tableau[i] ;
     tableau[i] = tableau[i / 2] ;
     tableau[i / 2] = t ;
     i /= 2 ;
 }
    }

    public static int supprimer(int [] tableau,  int nb) {
 int min = tableau[1] ;

 tableau[1] = tableau[nb--] ;
 int j, i = 1 ;
 while (i <= nb / 2) {
     if (2 * i == nb || tableau[2 * i] < tableau[2 * i + 1])
  j = 2 * i ;
     else
  j = 2 * i + 1 ;
     if (tableau[i] > tableau[j]) {
  int t = tableau[i] ;
  tableau[i] = tableau[j] ;
  tableau[j] = t ;
  i = j ;
     }
     else
  return min ;
 }
 return min ; 
    } 

    public static void main(String [] arg) {
 int [] tableau = new int[arg.length + 1] ;
 for (int i = 0 ; i < arg.length ; ++i)
     ajouter(tableau, i, Integer.parseInt(arg[i])) ;
 for (int i = 1 ; i <= arg.length ; ++i)
     System.out.print(tableau[i] + " ") ;
 System.out.println() ;
 for (int i = arg.length ; i > 1 ; --i)
     tableau[i] = supprimer(tableau, i) ;
 for (int i = 1 ; i <= arg.length ; ++i)
     System.out.print(tableau[i] + " ") ;
 System.out.println() ;
    }
}

This document was translated from L^AT_EX by H^EV^EA.