Pourquoi mon code est plus lent que Arrays.sort
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:
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:
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 ?
