Re: Lista de exercícios

[Fabio Silva <fdias@linux.ime.usp.br>]

Não entendi direito. Deixe-me ver: em outras palavras, um algoritmo de
ordenação é estavel quando ele não altera a ordem de um outro componente
do vetor de entrada não relacionado com o que pedimos para ordenar????

 Fabio Silva Dias   <fdias@linux.ime.usp.br>

On Fri, 3 Sep 1999, Imre Simon wrote:

> 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>
> : 
>