Discussion :

[alexis779]

On veut par exemple trier un tableau de String par ordre alphabétique.
On peut utiliser directement java.util.Arrays.sort avec le tableau de String en paramètre et éventuellement un deuxième paramètre pour définir l'ordre (croissant, décroissant ...)
Sur le site de Sun, il est dit que la méthode sort utilise un MergeSort modifié.

Moi je voudrais optimiser mon implémentation de QuickSort pour essayer de rivaliser avec la méthode sort, mais mon code semble beaucoup plus lent.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//import java.util.Arrays ;
public class QuickSort4 extends QuickSort
{
	String[] mots ;
	int N ;
	QuickSort4(String[] mots)
	{
		super( mots.length ) ;
		this.mots = mots ;
		N = mots.length ;
	}
 
	boolean inferieur(int i, int j)
	{
		return mots[indices[i]].compareTo( mots[indices[j]] ) <= 0 ;
	}
 
	void afficher()
	{
 
		for (int i = 0 ; i < N ; i++)
		{
			int j = indices[i] ;
			System.out.println(mots[j]) ;
		}
		System.out.println() ;
	}
 
	public static void main(String[] args)
	{
		String[] mots = { "papier", "carton", "verre", "plastique", "fer" } ;
 
		int N = mots.length ;
		QuickSort4 quickSort = new QuickSort4( mots ) ;
		quickSort.afficher() ;
 
		quickSort.sort(0, N - 1) ;
 
//		Arrays.sort( mots ) ; est beaucoup plus rapide
 
		quickSort.afficher() ;
 
	}
}

avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
abstract class QuickSort
{
	abstract boolean inferieur(int i, int j) ;
	protected int[] indices ;
 
	QuickSort(int N)
	{
		indices = new int[N] ;
		for (int i = 0 ; i < N ; i++)
		{
			indices[i] = i ;
		}		
	}
 
	void sort(int lo0, int hi0)
	{
		int lo = lo0;
		int hi = hi0;
 
		if (lo >= hi)
		{
			return;
		}
		else if( lo == hi - 1 )
		{
            /*
             *  sort a two element list by swapping if necessary 
             */
			if (! inferieur(lo, hi))
			{
				swap(lo, hi) ;
			}
			return;
		}
 
        /*
         *  Pick a pivot and move it out of the way
         */
		int indiceDuPivot = (lo + hi) / 2 ;
		swap( indiceDuPivot, hi) ;
		indiceDuPivot = hi ;
 
		while( lo < hi )
		{
            /*
             *  Search forward from a[lo] until an element is found that
             *  is greater than the pivot or lo >= hi 
             */
			while (inferieur(lo, indiceDuPivot ) && lo < hi)
			{
				lo++;
			}
 
            /*
             *  Search backward from a[hi] until element is found that
             *  is less than the pivot, or lo >= hi
             */
			while (inferieur( indiceDuPivot, hi) && lo < hi )
			{
				hi--;
			}
 
            /*
             *  Swap elements a[lo] and a[hi]
             */
			if ( lo < hi )
			{
				swap(lo, hi) ;
			}
		}
 
        /*
         *  Put the median in the "center" of the list
         */
		int tmp = indices[indiceDuPivot] ;
		indices[hi0] = indices[hi] ;
		indices[hi] = tmp ;
 
        /*
         *  Recursive calls, elements a[lo0] to a[lo-1] are less than or
         *  equal to pivot, elements a[hi+1] to a[hi0] are greater than
         *  pivot.
         */
		sort(lo0, lo-1);
		sort(hi+1, hi0);
	}
 
	private void swap(int i, int j)
	{
		permuter(indices, i, j) ;
	}
 
	void permuter(int[] a, int i, int j)
	{
		int T = a[i];
		a[i] = a[j];
		a[j] = T;
	}
 
}

Le but initial était d'utiliser une même classe QuickSort et de simplement implémenter, dans une classe qui étend QuickSort, la fonction de comparaison : si c'est dans l'odre croissant, décroissant, alphabétique ...

Enfin la question du message : Qu'est-ce qui ralentit le tri dans mon implémentation ?

[professeur shadoko]

avant toute chose: il ne vaut mieux pas faire un tri alphabétique comme ça en Java!
(tu connais l'ordre alphabétique entre l'accent aigu et l'accent grave?)
voir Collator.

[jowo]

Bonjour,

Un tri sur cinq éléments n'est pas un bon test pour QuickSort. QuickSort n'est intéressant qu'à partir d'un certain nombre d'éléments. Pour un petit nombre d'éléments à trier (moins de 10), des algorithmes "simples" sont plus rapides.

[benratti]

De plus, le quicksort n'est pas le tri qui a la meilleur compléxité. Dans le pire des cas, il reste tout de même quadratique !

Regarde plutot du coté du tri fusion qui est en o(n log n) et non en o(n^2)