Tri rapide sur un tableau d'entiers
Bonjour,
J'ai besoin d'un algo de tri extrêmement rapide en bash, du genre qui mettrait moins d'une seconde à trier un tableau de 100 000 entiers compris entre 0 et 1 million.
Actuellement, j'ai ça :
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
| sortnumbers() {
local array=( `echo "$@"` )
local -a l
local -a g
local -a e
local x=
if [ ${#array[@]} -lt 2 ]; then
echo -n ${array[@]}
else
local pivot=${array[0]}
for x in ${array[@]}
do
if [ $x -lt $pivot ]
then
l=( ${l[@]} $x )
elif [ $x -gt $pivot ]
then
g=( ${g[@]} $x )
else
e=(${e[@]} $x)
fi
done
echo "`sortnumbers "${l[@]}"` ${e[@]} `sortnumbers "${g[@]}"`"
fi
}
read N
for (( i=0; i<N; i++ )); do
read tab[i]
done
sorted=($(sortnumbers "${tab[@]}"))
min=$(( sorted[1]-sorted[0] ))
for (( i=1; i<N-1; i++ )); do
diff=$(( sorted[i+1] - sorted[i] ))
if [ "$diff" -lt "$min" ]; then
min=$diff
fi
done
echo $min |
J'ai pris la fonction sortnumbers sur le net bien sûr. :D
Cet algo met plus de cinq secondes à s'exécuter chez moi, ce qui est beaucoup trop lent !
Alors vous allez me dire, "Pourquoi tu le fais en bash alors ? Il existe plein d'autres langages pour lesquels ce que tu veux faire sera bien plus rapide !"
Héhé oui mais si seulement c'était aussi simple...
Le défi qu'on m'a posé est justement de résoudre ceci en bash. :oops:
On m'a parlé du bucket sort, ça m'a l'air bien, mais étant une nouille en bash je n'ai aucune idée de la syntaxe pour l'implémenter.
P.S : Après la ligne 40, je parcours mon tableau et je fais le calcul du minimum de la distance entre deux entiers consécutifs; Cette étape est indispensable à la résolution du problème, mais je ne pense pas que la lenteur de l'algo vienne de là puisque cette étape ne peut pas être plus simple, je pense (complexité en O(n)).
Merci d'avance de vos réponses ! :)
