-
Relação de algoritmos para memorizar:
Ordenação por inserção: Insertion sort, Shell sort(melhoria do Insertion sort), Gnome sort(similar ao insertion sort e funcionamento do Bubble sort),
Ordenação por seleção: Selection sort, Heap sort
Ordenação por comparação/troca: Bubble sort(ou ordenação por flutuação), Comb sort(melhoria do Bubble sort), Cocktail sort(Bubble em duas direções)
Ordenação por divisão e conquista: Quick sort, Merge sort
Outros: Radix sort, Counting sort, Bogosort(probabilístico), Bucket sort.
-
Classificação por intercalação
Os métodos de classificação por intercalação dividem a tabela em dois
ou mais segmentos, ordenam estes segmentos e depois os intercalam,
terminando, ao final, com um único segmento (toda a tabela) ordenado.
O principal algoritmo desta família é o MergeSort (ou Intercalação
Simples).
MergeSort (Intercalação Simples): A idéia por traz do MergeSort é bastante
simples: divide-se a tabela em diversos segmentos menores para a seguir
ordenar-se estes segmentos. Feito isto, estes segmentos são agrupados entre sí (intercalados) e este processo produz novos segmentos ordenados
(maiores que os segmentos iniciais).
O processo de agrupamento e ordenação dos segmentos (intercalação)
continua até que se obtenha um único segmento que contenha toda a
tabela e esteja totalmente ordenado.
-
Método da Troca e Partição (QuickSort): é o mais rápido entre os métodos
apresentados até o momento, e também o mais utilizado. Esse método foi
proposto por C. A. R. Hoare em 1962 e parte do princípio que é mais rápido
classificar dois vetores com n/2 elementos cada um, do que um com n
elementos (dividir um problema maior em dois menores).
A parte mais delicada do método é o particionamento do vetor. O vetor é
particionado em três segmentos:
V[1], ..., V[i - 1] V[i] V[i + 1], ..., V[n]
(segmento 1) (segmento 2) (segmento 3)
A partição é realizada através da escolha arbitrária de um elemento (V[i])
de modo que os elementos no segmento 1 sejam menores, e os elementos
no segmento 3 sejam maiores do que o elemento escolhido V[i].
Após a ordenação dos segmentos 1 e 3, tem-se o vetor original
classificado. O processo de partição pode ser repetido para os segmentos
1 e 3.
Obs. Quando um segmento apresenta um número de elementos menor ou
igual a M (um número pré-estabelecido), aplica-se um método simples de
ordenação.
-
c)Quick sort e Merge sort
-
MERGE SORT
Esse algoritmo segue o paradigma divisão e conquista.
Divisão: Divide a sequência de n elementos que deve ser ordenada em subsequências de n/2 elementos cada uma.
Conquista: Ordena as duas sequencias recursivamente. A recursão termina quando a sequência a ser ordenada tiver apenas um elemento.
Combinação: Intercala as duas subsequências ordenadas para produzir a resposta ordenada.
QUICK SORT
O quick sort é um método de ordenação por troca que aplica o paradigma de divisão e conquista.
Um elemento do arranjo será escolhido como pivô.
Em seguida o arranjo é dividido em 2 subarranjos:
Elementos menores ou iguais ao pivô.
Elementos maiores que o pivô
Os dois arranjos do passo anterior são ordenados recursivamente com o quick sort.
-
Gabarito C
Quicksort - Escolhe-se um pivot e particiona-se a lista em duas sublistas: uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivot, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso médio é de O(n log n).
MergeSort - divide para conquistar sucessivamente o vetor, e vai ordenando juntando os vetores. Geralmente se implementa recursivamente.
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !