Re: Lista de exercícios

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

Sugiro Voce ler o livro: página 259.

Imre Simon

: Date: Fri, 3 Sep 1999 15:09:29 -0300 (EST)
: From: Fabio Silva <fdias@linux.ime.usp.br>
: To: Imre Simon <is@ime.usp.br>
: cc: Antonio Joao Ferreira Francisco <ajoaoff@linux.ime.usp.br>,
:   is-122-99@ime.usp.br
: Subject: Re: =?ISO-8859-1?Q?Lista_de_exerc=EDcios?=
: 
: 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>
: > : 
: > 
: