gsort

Paramètres

A

vecteur ou matrice de nombres réels, entiers ou de chaînes de caractères ou vecteur creux.

option

une chaîne de caractères, définissant le type de tri à réaliser:

• 'r' : trie chaque colonne de la matrice A

• 'c': trie chaque ligne de la matrice A

• 'g': trie tous les éléments de A(:). C'est la valeur par défaut.

• 'lr': tri lexicographique des lignes de A

• 'lc': tri lexicographique des colonnes de A

direction

Une chaîne de caractères définissant si le tri doit se faire dans l'ordre croissant ('i') ou décroissant ('d'). La valeur par défaut est ('d').

B

vecteur ou matrice de même type et même dimensions que A.

k

vecteur ou matrice de nombres entiers de même taille que A contenant les index d'origine.

Description

gsort est basé sur l'algorithme de tri rapide "quick sort" modifié pour maintenir l'ordre relatif des éléments ayant des valeurs égales lorsque l'index de tri est demandé.

• B=gsort(A,'g') et B=gsort(A,'g','d') produisent le même résultat que B=gsort(A). Ces instructions produisent un tri de la matrice A, vue comme le vecteur A(:).

  B=gsort(A,'g','i') fonctionne de la même manière pour l'ordre croissant.

• B=gsort(A,'lr') trie les lignes de la matrice A dans l'ordre lexical décroissant. B est obtenue par une permutation des lignes de la matrice A de telle manière que les lignes de B vérifient B(i,:)>=B(j,:) si i<j.

  B=gsort(A,'lr','i') fonctionne de la même manière pour l'ordre lexical croissant.

• B=gsort(A,'lc') trie les colonnes de la matrice A dans l'ordre lexical décroissant. B est obtenue par une permutation des colonnes de la matrice A de telle manière que les colonnes de B vérifient B(:,i)>=B(:,j) si i<j.

  B=gsort(A,'lc','i') fonctionne de la même manière pour l'ordre lexical croissant.

Si le second argument de retour k est demandé, il contient les indices des valeurs triées dans le tableau d'origine. Si [B,k]=gsort(A,'g') on a B==A(k). L'algorithme préserve l'ordre relatif des éléments ayant des valeurs égales.

Les matrices ou vecteurs complexes sont triés par rapport au module complexe. Seule l'option 'g' est accessible avec des nombres complexes.

Pour les nombres complexes, gsort peut être surchargé.

voir la macro: SCI/modules/elementary_functions/macros/%_gsort.sci

La surcharge pour les types autres que vecteur ou matrice de nombres réels, entiers ou de chaînes de caractères ou vecteur creux est possible.

Si A contient des %nan ou des %inf ceux ci seront placés en début avec l'argument 'd' ou à la fin avec l'argument 'i'.

Exemples

alr=[1,2,2;
1,2,1;
1,1,2;
1,1,1];
[alr1,k]=gsort(alr,'lr','i')
[alr1,k]=gsort(alr,'lc','i')

A=int32(alr)

gsort(A)
gsort(A,'lr','i')
gsort(A,'lc','i')

A=['Scilab' '2.6'
'Scilab' '2.7'
'xcos' '2.7'
'Scilab' '3.1'
'xcos' '3.1'
'xcos' '4.0'
'Scilab' '4.0']

gsort(A,'lr','i')
gsort(A,'lc','i')

Voir aussi

• find — trouve les indices des éléments vrais d'un vecteur ou d'une matrice de booléens
• overloading — display, functions and operators overloading capabilities

Bibliographie

Quick sort algorithm from Bentley & McIlroy's "Engineering a Sort Function". Software---Practice and Experience, 23(11):1249-1265

Historique