O Desenvolvimento de um Sistema Para Análise do Desempenho de Algoritmos de Ordenação de Dados

UNIP – UNIVERSIDADE PAULISTA

8° Semestre Ciência Da Computação (CC)

Fabio Marques de Lima – N1284F-0

Campus - Alphaville

Desenvolvimento de um sistema para análise do desempenho de algoritmos de ordenação de dados.

SÃO PAULO

2020

Sumário

Insertion Sort        2

SelectionSort        4

Vantagens do Selection Sort:        5

Desvantagens do Selection Sort:        5

QuickSort        5

Pior Caso        6

Melhor Caso        6

Dividir e Conquistar        6

Insertion Sort

Insertion Sort, ou ordenação por inserção, é o algoritmo de ordenação que, diante de uma estrutura, seja ela um array ou uma lista, constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação.

Imagine que é começado a pegar uma carta de cada vez do topo de um monte de baralho, conforme vai sendo pego cartas para a mão as mesmas devem ser ordenadas corretamente. Então, após pegar uma carta nova é necessário verificar as cartas anteriores até achar uma posição no qual ela se encaixe. O algoritmo de ordenação por inserção (Insertion Sort) cumpre exatamente esse papel. É percorrido as posições de um array ou uma lista, começando de sua primeira posição e a cada nova carta é uma nova posição onde é preciso que seja inserida no lugar correto no subarray ordenado á esquerda daquela posição. Aqui está um exemplo ilustrado pratico:

Na primeira imagem temos 6 posições já preenchidas e então adicionamos mais um valor:

[pic 1]

Figura 1 - Lista de itens Isertion Sort não ordenada

Então é aplicado o algoritmo e o resultado final ficará assim:

[pic 2]

Figura 2 - Lista de itens Isertion Sort ordenada

Então, em resumo:

• É comparado um valor de um item que está sendo inserido em um grupo de itens para que sua posição correta seja encontrada e essa comparação é realizada em direção a esquerda.
• Caso o item comparado for menos, desloque o mesmo para a DIREITA, com objetivo de obter um novo espaço para colocar o item no lugar correspondente.
• E então, ao encontrar um item de valor maior ou chegar no fim da lista/array, significa que foi encontrado a posição no qual esse item deve ser alocado.
• O Insertion Sort possui algumas características consideráveis:
• È de simples implementação, leitura e manutenção;
• In-place: Apenas requer uma quantidade constante de O (1) espaço de memória adicional;
• Estável: Não muda a ordem relativa de elementos com valores iguais;
• Útil para pequenas entradas;
• Muitas trocas, e menos comparações;
• Melhor caso: O (n), quando a matriz está ordenado;
• Médio caso: O (n²/4), quando a matriz tem valores aleatórios sem ordem de classificação (crescente ou decrescente);
• Pior caso: O (n²), quando a matriz está em ordem inversa, daquela que deseja ordenar.

SelectionSort

A ordenação por seleção ou selection sort, é um algoritmo de ordenação que tem como função sempre mover o menor ou maior, depende da ordem pedida, valor de um array/lista para a primeira posição, depois o segundo menor/maior valor para a segunda posição e assim sucessivamente com os restantes dos valores.

O Selection Sort seleciona um número a partir do primeiro item no array/lista, então com esse numero é feita a comparação com os números a sua direita, quando entrado um item de valor menor/maior o numero escolhido ocupa seu lugar. Após a ocupação o numero que teve sua posição ocupada é o próximo escolhido e assim sucessivamente até que não aja mais valores maiores/menores que o item escolhido e assim seguindo o processo até que a lista seja ordenada.

[pic 3]

Figura 3 - Exemplificação de ordenação com Selecion Sort

• No item 1, o primeiro numero escolhido foi o 3, então foi feita a comparação com os números a direta e o menor encontrado foi o 1, sendo o numero escolhido o primeiro da lista, consequentemente o item comparado e movido para a posição é o menor da lista.
• No item 2 foi feito o mesmo processo que o passo 1;.+
• No item 3 não foi encontrado nenhum numero menos que 3 a direta, logo ele permaneceu no mesmo lugar
• No item 4, foi feita a última ordenação.
• No item 5 é mostrado a lista totalmente ordenada.

Vantagens do Selection Sort:

• É implementado de forma simples em comparação com os demais.
• Não é necessário um vetor auxiliar (in-place).
• Ocupa menos memoria por não usar vetor auxiliar.
• Sendo um dos que possui melhor desempenho com listas pequenas

Desvantagens do Selection Sort:

• É um dos que possui pior desempenho com listas grandes.
• Ele não é estável.
• Ele faz sempre {\displaystyle (n^{2}-n)/2}(n² - n) /2 comparações, independente do vetor está ordenado ou não.

QuickSort

O Algoritmo QuickSort ou ordenação rápida, foi criado a partir de uma necessidade de traduzir um dicionário de inglês para russo, ordenando as palavras, sendo que seu objetivo era reduzir o problema original em subproblemas (Divide and Conquer) que assim pode ser resolvido de formas mais fáceis e rápidos.

O QuickSort tem como estratégia o conceito “Divide and Conquer” (Dividir e Conquistar). Esse conceito tem como funcionalidade rearrumar as chaves de um vetor de modo que as chaves “menores” precedam as chaves “maiores”. Então o quicksort ordena as duas sublistas do vetor em chaves menores e maiores recursivamente até que a lista se complete ordenadamente.