Re: Lista de exercícios

[Imre Simon <is@ime.usp.br>]

2. Um método de ordenação é estável se ele preserva a ordem relativa de ítens
        com chaves idênticas. (Veja na página 259 do livro)

Dito de outra forma: os ítens que têm chaves idênticas, aparecem na
saída na mesma ordem em que apareceram na entrada.

Exemplo: ordene os ítens

(1,a) (2,b) (3,a) (4,b) (5,a)

usando a segunda coordenada como chave.

Sort estável dá a resposta:

(1,a) (3,a) (5,a) (2,b) (4,b)

Um sort que não é estável poderia dar a resposta:

(1,a) (5,a) (3,a) (2,b) (4,b)

Para entender melhor, suponha que os alunos da USP foram ordenados
segundo os seus nomes. Usando um algoritmo de ordenação estável para
ordenar este vetor por curso, a lista de cada curso estará em ordem
alfabética. Se o algoritmo não for estável nada poderemos afirmar.

Imre Simon


: Date: Fri, 3 Sep 1999 14:40:20 -0300 (EST)
: From: Fabio Silva <fdias@linux.ime.usp.br>
: To: Antonio Joao Ferreira Francisco <ajoaoff@linux.ime.usp.br>
: cc: is-122-99@ime.usp.br
: Subject: =?ISO-8859-1?Q?Lista_de_exerc=EDcios?=
: 
: 
: Numa das listas de exercícios passadas pelo prof. Paulo Feofiloff há uma
: pergunta do tipo "o algoritmo de ordenação por seleção é estável?
: justifique."
: Desculpem minha burrice, mas não sei o que ou quando é um algoritmo
: é estável. Alguem poderia me explicar?
: 
:  Fabio Silva Dias   <fdias@linux.ime.usp.br>
: