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é.