Métodos De Ordenação
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Métodos De Ordenação as PDF for free.
More details
- Words: 950
- Pages: 5
INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE PERNAMBUCO CAMPUS BELO JARDIM ANNE INGRID F. BEZERRA TÉCNICO INFORMÁTICA 2º C
MÉTODOS DE ORDENAÇÃO
Belo Jardim - PE 05-05-2009
Métodos de Ordenação
Ordenação consiste ao método de reorganizar um conjunto de objetos em ordem crescente ou decrescente comparando os elementos para determinar qual deles vem em primeira ordem na lista ordenada, tendo como objetivo facilitar a recuperação de itens de um determinado conjunto. Existem muitos algoritmos de ordenação, a escolha mais eficiente vai depender de vários fatores, tais como: número de itens a ser classificado; se os valores já estão agrupados em subconjuntos ordenados etc. Atualmente há uma grande necessidade de guardar informações e possuílas ordenadas, seja por ordem alfabética, por idade, localidade entre outros. Os principais Métodos de ordenação são: •Método de ordenação por selecção (Selecção Directa) • Método de ordenação por inserção (com Pivot) • Método de ordenação por bolha (Bubble Sort) • Método de torneio (Quick Sort)
Métodos de ordenação Bolha (“Bubble Sort”) Por ser simples e fácil de entender e implementar, o Bubble Sort está entre os mais conhecidos algoritmos de ordenação. Porém, devido a sua baixa eficiência, devemos tratá-lo como uma solução mais para desenvolvimento de raciocínio que de uso recorrente (embora não seja um problema usá-lo em casos onde não exige muita performance, como quando desejamos ordenar um conjunto com poucos elementos). Seu princípio é a comparação e troca de valores entre posições consecutivas, fazendo com que os valores mais altos ( ou mais baixos) migrem (“borbulhem”) para o final do vetor a ser ordenado. Ex: int aux; for ( i=0; i <= tam-2; i++ ) for ( j=0; j<= tam-2-i; j++ ) if ( Array[j] > Array[j+1] ) aux = Array[j]; Array[j] = Array[j+1]; Array[j+1] = aux
Selecção
O método de ordenação por Selecção Directa é levemente mais eficiente que o método Bubblesort, ainda que se trate de um algoritmo apenas para estudo e ordenação de pequenas listas. A lógica consiste em se varrer a lista comparando todos os seus elementos com o primeiro. Caso o primeiro elemento esteja desordenado em relação ao elemento que está sendo comparado com ele no momento, é feita a troca. Ao se chegar ao final da lista, teremos o menor valor ( ou o maior, conforme a comparação ) na primeira posição do arranjo. Int aux; for( i=0; i <= tam - 2; i++ ) { for( j=i+1; j <= tam - 1; j++ ) { if ( Array[j] < Array[i] ) { aux = Array[j]; Array[j] = Array[i]; Array[i] = aux;
Comparações de tempo: Existe um ciclo que é executado n vezes, mas o tempo não é de ordem n, pois é necessária a informação do menor elemento e isto produz outro ciclo, logo o algoritmo é de ordem N^2.
Inserção
Este método é o mais rápido entre os outros métodos considerados básicos. O algoritmo, consiste em ordenar uma lista utilizando uma sub-lista ordenada localizada em seu inicio, e a cada novo passo, acrescentamos a esta sub-lista mais um elemento, até que atingimos o último elemento da lista fazendo assim com que ela se torne ordenada. Funciona como se ordenássemos um baralho que temos na mão direita, para a mão esquerda, passando uma carta de cada vez. long int aux; long int j; for( long int i=1; i <= tam - 1; i++ ) { aux = Array[i]; j = i - 1; while ( j >= 0 && aux < Array[j] ) { Array[j + 1] = Array[j] ; j--; } Array[j+1] = aux;
Métodos mais eficientes
Merge sort
Este método baseia-se na estratégia do dividir para conquistar! A sua ideia é dividir o vector em duas partes iguais, até que resultem dois vectores com apenas um único elemento. void merge(int M[50], int p, int r) { int q; if (pq) for(k=seg; k<=r; k++) { C[res] = M[k]; res++; } else { for(k=prim; k<=q; k++) { C[res] = M[k]; res++; } } for(k=p; k<=r; k++) M[k] = C[k];
Que tempos de ordenação podemos esperar? O algoritmo requer 2n passos, um para copiar a lista para a sequência intermediária e outra para a reordenar. Logo é de O(2nlog(n)) = O(n log n).
Quicksort
O quicksort é um dos algoritmos de ordenação mais simples e eficientes que existem. O seu principio é muito semelhante ao mergesort. Primeiro a lista a ordenar é partida em duas partes, de maneira a que os elementos primeira parte sejam menores ou iguais a todos os elementos da segunda. Recursivamente, as duas partes são ordenadas pelo mesmo algoritmo e são então combinadas para dar a lista final. O primeiro passo é escolher um elemento x e depois dividir. A ideia usada neste algoritmo também é a dividir para conquistar void quick(int Q[50], int inicio, int fim) { int meio; if (inicio
No melhor caso, quando a partição da lista produz duas listas de igual tamanho, o algoritmo tem O(N*logN). No Pior caso, quando a divisão faz com que todos os elementos se posicionem de um lado, o algoritmo tem O(n^2).
MÉTODOS DE ORDENAÇÃO
Belo Jardim - PE 05-05-2009
Métodos de Ordenação
Ordenação consiste ao método de reorganizar um conjunto de objetos em ordem crescente ou decrescente comparando os elementos para determinar qual deles vem em primeira ordem na lista ordenada, tendo como objetivo facilitar a recuperação de itens de um determinado conjunto. Existem muitos algoritmos de ordenação, a escolha mais eficiente vai depender de vários fatores, tais como: número de itens a ser classificado; se os valores já estão agrupados em subconjuntos ordenados etc. Atualmente há uma grande necessidade de guardar informações e possuílas ordenadas, seja por ordem alfabética, por idade, localidade entre outros. Os principais Métodos de ordenação são: •Método de ordenação por selecção (Selecção Directa) • Método de ordenação por inserção (com Pivot) • Método de ordenação por bolha (Bubble Sort) • Método de torneio (Quick Sort)
Métodos de ordenação Bolha (“Bubble Sort”) Por ser simples e fácil de entender e implementar, o Bubble Sort está entre os mais conhecidos algoritmos de ordenação. Porém, devido a sua baixa eficiência, devemos tratá-lo como uma solução mais para desenvolvimento de raciocínio que de uso recorrente (embora não seja um problema usá-lo em casos onde não exige muita performance, como quando desejamos ordenar um conjunto com poucos elementos). Seu princípio é a comparação e troca de valores entre posições consecutivas, fazendo com que os valores mais altos ( ou mais baixos) migrem (“borbulhem”) para o final do vetor a ser ordenado. Ex: int aux; for ( i=0; i <= tam-2; i++ ) for ( j=0; j<= tam-2-i; j++ ) if ( Array[j] > Array[j+1] ) aux = Array[j]; Array[j] = Array[j+1]; Array[j+1] = aux
Selecção
O método de ordenação por Selecção Directa é levemente mais eficiente que o método Bubblesort, ainda que se trate de um algoritmo apenas para estudo e ordenação de pequenas listas. A lógica consiste em se varrer a lista comparando todos os seus elementos com o primeiro. Caso o primeiro elemento esteja desordenado em relação ao elemento que está sendo comparado com ele no momento, é feita a troca. Ao se chegar ao final da lista, teremos o menor valor ( ou o maior, conforme a comparação ) na primeira posição do arranjo. Int aux; for( i=0; i <= tam - 2; i++ ) { for( j=i+1; j <= tam - 1; j++ ) { if ( Array[j] < Array[i] ) { aux = Array[j]; Array[j] = Array[i]; Array[i] = aux;
Comparações de tempo: Existe um ciclo que é executado n vezes, mas o tempo não é de ordem n, pois é necessária a informação do menor elemento e isto produz outro ciclo, logo o algoritmo é de ordem N^2.
Inserção
Este método é o mais rápido entre os outros métodos considerados básicos. O algoritmo, consiste em ordenar uma lista utilizando uma sub-lista ordenada localizada em seu inicio, e a cada novo passo, acrescentamos a esta sub-lista mais um elemento, até que atingimos o último elemento da lista fazendo assim com que ela se torne ordenada. Funciona como se ordenássemos um baralho que temos na mão direita, para a mão esquerda, passando uma carta de cada vez. long int aux; long int j; for( long int i=1; i <= tam - 1; i++ ) { aux = Array[i]; j = i - 1; while ( j >= 0 && aux < Array[j] ) { Array[j + 1] = Array[j] ; j--; } Array[j+1] = aux;
Métodos mais eficientes
Merge sort
Este método baseia-se na estratégia do dividir para conquistar! A sua ideia é dividir o vector em duas partes iguais, até que resultem dois vectores com apenas um único elemento. void merge(int M[50], int p, int r) { int q; if (p
Que tempos de ordenação podemos esperar? O algoritmo requer 2n passos, um para copiar a lista para a sequência intermediária e outra para a reordenar. Logo é de O(2nlog(n)) = O(n log n).
Quicksort
O quicksort é um dos algoritmos de ordenação mais simples e eficientes que existem. O seu principio é muito semelhante ao mergesort. Primeiro a lista a ordenar é partida em duas partes, de maneira a que os elementos primeira parte sejam menores ou iguais a todos os elementos da segunda. Recursivamente, as duas partes são ordenadas pelo mesmo algoritmo e são então combinadas para dar a lista final. O primeiro passo é escolher um elemento x e depois dividir. A ideia usada neste algoritmo também é a dividir para conquistar void quick(int Q[50], int inicio, int fim) { int meio; if (inicio
No melhor caso, quando a partição da lista produz duas listas de igual tamanho, o algoritmo tem O(N*logN). No Pior caso, quando a divisão faz com que todos os elementos se posicionem de um lado, o algoritmo tem O(n^2).
Related Documents
De
November 2019 92
De
November 2019 101
De
May 2020 87
De
June 2020 79
De
June 2020 68
