Discussion :

[movrack]

Bonjour,
je dois réaliser un tri sur une liste presque triée, (les éléments non triés se trouve à la fin de la liste) ainsi qu'une matrice où l'index des colonnes et lignes correspondent à l'index d'un élément dans la liste.

J'aimerais avoir votre avis sur ce que j'ai écrit et les améliorations que je pourrais faire.
Le but étant que comme la liste est presque triée, ne pas devoir re-trier les éléments déjà triés.

J'ai écrit ceci, qu'en pensez vous?

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
 
private List<List<Integer>> matrice; // matrice.enfants.parents
private List<Library> libraries;
 
private int lastSortedLibIndex = 0;
 
 
public void sort() {
        if(size() <= 1 || size() == lastSortedLibIndex) return ;
 
        List<Library> goodList = new ArrayList<Library>(libraries.subList(0, lastSortedLibIndex));        
        List<Library> head = null;
        List<Library> tail = null;
        List<Library> badList = new ArrayList<Library>(libraries.subList(lastSortedLibIndex, size()));
 
        List<List<Integer>> goodChild = new ArrayList<List<Integer>>(matrice.subList(0, lastSortedLibIndex));        
        List<List<Integer>> headChild = null;
        List<List<Integer>> tailChild = null;
 
        List<Integer> headParent = null;
        List<Integer> tailParent = null;
 
        for(Library lib : badList){
            int pos = goodIndexBinarySearch(goodList, lib);
            int indexLib = indexOf(lib);
 
            // Childs
            headChild = new ArrayList<List<Integer>>(goodChild.subList(0, pos));
            tailChild = new ArrayList<List<Integer>>(goodChild.subList(pos, goodChild.size()));
            headChild.add(matrice.get(indexLib));
            headChild.addAll(tailChild);
            goodChild = headChild;
 
            // Parents
            int iChild = 0;
            for(List<Integer> child : goodChild){
                int relation = child.get(indexLib);
 
                child.remove(indexLib);
                headParent = new ArrayList<Integer> (child.subList(0, pos));
                tailParent = new ArrayList<Integer> (child.subList(pos, child.size()));
                headParent.add(relation);
                headParent.addAll(tailParent);
                goodChild.set(iChild, headParent);
                iChild++;
            }
 
            // Lib
            head = new ArrayList<Library>(goodList.subList(0, pos));            
            tail = new ArrayList<Library>(goodList.subList(pos, goodList.size()));
            head.add(lib);
            head.addAll(tail);
            goodList = head;
        }
        libraries = goodList;
        matrice = goodChild;
        lastSortedLibIndex = size()-1;
 
    }
 
public int goodIndexBinarySearch(List<Library> libList, Library lib){
        int index = Collections.binarySearch(libList, lib);
        if (index >= 0) return -1;
        else return ( -index -1 );
}

Je me rend compte que j'utilise peut-être beaucoup de liste, mais celles-ci ne devrait pas être très grandes, 100 voir 200 Library au grand maximum.

edit: Remarque, ici j'ai mit private int lastSortedLibIndex = 0;, mais il vaudra via les autres méthodes de l'objet l'index du dernier élément trié.

[movrack]

Bon, je vien de tester et cela ne fonctionne pas, mais l'idée est là.



Edit : Voilà, j'ai corrigé mon code.
Que pensez vous de l'efficacité ?

J'ai tenté de faire un genre de tri par insertion en déplaçant les éléments triés ensembles et non pas un par un.

[merill]

Le mergesort (utilisé par Collections.sort) est en O(n) sur une liste triée.
Tu ne te complique pas la vie pour pouvoir dégrader tes performances?

[movrack]

Justement, si j'utilise une méthode implémentée par java pour trier la liste, comment je fait pour trier la matrice en gardant la correspondance sur les index de chacun ?

[merill]

Tu doit faire un tri sur "une matrice où l'index des colonnes et lignes correspondent à l'index d'un élément dans la liste"

Pourquoi la trier?

Pourquoi utiliser des indices et pas des références?
genre

Code :

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

1
2
3
4
5
6
7
 
private List<List<Library>> matrice; // matrice.enfants.parents
private List<Library> libraries;
 
...
 
Collections.sort(librairies);

[movrack]

Que représente les librairies dans la matrice?