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
| public class TestQuickSortDeListe2 {
public static void main(String[] args) {
List<Integer> list = createList(1000000);
//List<Integer> list = readList();
//System.out.println(list);
//System.out.println(Arrays.toString(array));
long time = System.currentTimeMillis();
try {
list = new TestQuickSortDeListe2().trier(list);
//System.out.println(Arrays.toString(array));
}
finally {
System.out.println(System.currentTimeMillis()-time+" ms");
}
//System.out.println(list);
}
private static List<Integer> createList(int nb) {
List<Integer> list = new ArrayList<>();
Random random = new Random(424242);
for(int i=0;i<1000000; i++) {
list.add(random.nextInt());
}
return list;
}
private static List<Integer> readList() {
return ReadListe.readList();
}
public List<Integer> trier(List<Integer> list) {
if (list == null || list.isEmpty() ) {
return Collections.emptyList();
}
trier(list, 0, list.size()-1);
return list;
}
private int trier(List<Integer> list, int debut, int fin, int pivot) {
echanger(list, pivot, fin);
int j = debut;
for( int i=debut; i<fin; i++) {
if ( list.get(i).compareTo(list.get(fin))<=0 ) {
echanger(list, i, j);
j ++;
}
}
echanger( list, fin, j);
return j;
}
protected int choixPivot(List<Integer> list, int debut, int fin) {
return debut;
}
private void echanger(List<Integer> list, int i1, int i2) {
Integer temp = list.get(i1);
list.set(i1, list.get(i2));
list.set(i2, temp);
}
private void trier(List<Integer> list, int debut, int fin) {
if ( debut<fin ) {
int pivot = choixPivot(list, debut, fin);
pivot = trier(list, debut, fin, pivot);
trier(list, debut, pivot-1);
trier(list, pivot+1, fin);
}
}
} |
Partager