APS 4ºSem - UNIP “DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS”

Prévia do material em texto

Atividades Práticas Supervisionadas
“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS”
Curso: Ciência da Computação (CC) - Tutelado
Nome: Gustavo Leite Antonio Vieira Marcondes RA: N936BH8 
Sumário
1.Objetivo do Trabalho	3
2.Introdução	4
3.Referencial Teórico	6
4.Desenvolvimento	16
 4.1 Insertion Sort	16
4.2 Comb Sort	19
4.3 Selection Sort	22
4.4 Timsort	25
4.5 Quicksort	25
5.Resultados e Considerações finais	35
6.Referências Bibliográficas	36
7.Ficha de Atividades Práticas Supervisionadas	37
Objetivo do Trabalho:
 Deve-se realizar um trabalho utilizando algoritmos considerando o seguinte exemplo: o geoprocessamento de imagens da floresta amazônica permite a fiscalização de ações de crimes ambientais. Os satélites geram cerca de 100 mil imagens de toda a região a cada 24 horas, essas imagens são armazenadas o catalogadas. Selecionando três ou mais técnicas que são comuns para a criação de métodos eficientes com performance elevada em ordenação de dados, para auxiliar na observação e monitoramento dos crimes ambientais na região amazônica, encontrar algoritmos computacionais para ordenação, e os principais tipos destes.
Sabendo que um satélite é responsável pela obtenção de fotos do estado da floresta, um algoritmo deverá ser criado para realizar as comparações entre os dados e revelar se alguma área está sendo lesada pelos crimes ambientais, assim facilitando e otimizando os processos de fiscalizações. Organização e eficiência, no mundo de hoje é imprescindível, e não poderia ser diferente no Mundo Digital, que dobra de tamanho a cada 2 anos. Os Algoritmos de Ordenação de Vetores têm justamente esse fim, automatizar o processo de ordenação de dados, sejam eles quais for. No seu dia a dia o Homem se depara com a necessidade de consultar dados ordenados e será apresentado neste trabalho diversos algoritmos de ordenação de dados.
Um computador é uma máquina que manipula informações. O estudo da ciência da computação inclui o exame da organização, manipulação e utilização destas informações num computador. Consequentemente, é muito importante compreendê-los. Na sociedade atual, a automatização de tarefas está marcante, pra onde quer que olhe a um processo que é desenvolvido simultaneamente com maquinas e elementos para uma geração automática de dados. Todo o contexto histórico será abordado para início de conversa, como seu surgimento, evolução, suas aplicações e passando por ramificações históricas pontos de atenção até sua importância na atualidade em operações do cotidiano.
Introdução:
O uso de meios tecnológicos como ferramenta de fiscalização vem crescendo e se difundindo em meio ao mundo moderno, visto que não é limitado ao tema do trabalho sabendo que monitoramento de dados é algo importante para tomadas de decisões em diversas áreas e um perigo em outras. O Brasil tem o seu primeiro satélite de monitoramento, ele é chamado de "amazonia-1" e é integrado, testado, projetado e operado pelo Brasil e fiscaliza justamente a região amazônica, tendo monitoramento para atividades que possam trazer prejuízos para o meio ambiente, com o intuito de fornecer o máximo de informações necessárias para autoridades e ongs.
O uso de tecnologias para evitar futuras degradações ambientais serve de apoio até para a área da agricultura esses softwares podem reduzir o uso de insumos e fertilizantes se baseando nas imagens obtidas pelo satélite, que por sua vez desenvolve menos gases que seria prejudicial para atmosfera e o aquecimento global. Junto disso, o seu uso mais popular, não deste em especifico, mas dos satélites em geral, seria o GPS, facilitando rotas de veículos, diminuindo seus trajetos e junto a diminuição da geração de carbono com alternativas mais viáveis. Com os processos dessas tecnologias, visa-se a criação de dados e sua ordenação com os recursos computacionais necessários para um eficiente estudo e posteriormente resultados mais precisos seguindo o tema do trabalho e sua fiscalização proposta.
Ordenação é o ato de se colocar os elementos de uma sequência de informações, ou dados, em uma ordem predefinida. O termo técnico em inglês para ordenação é sorting. Algumas ordens são facilmente definidas. Por exemplo, a ordem numérica, ou a ordem alfabética -- crescentes ou decrescentes. Contudo, existem ordens, especialmente de dados compostos, que podem ser não triviais de se estabelecer. Os algoritmos que ordenam um conjunto, geralmente representados em um vetor, são chamados de algoritmos de ordenação. Entre os mais importantes, podemos citar Bubble sort, Heapsort, Insertion sort, Merge sort e o Quicksort.
A ordenação de dados é uma operação aritmética básica essencial e amplamente utilizada que facilita a compreensão e o acesso rápido aos diferentes tipos de dados operados pelas aplicações. Para o processo de ordenação de dados computacionais, existem métodos dedicados alguns abordam uma variedade de técnicas existente para o estudo e analise do comportamento teórico ou pratico visto.
Um algoritmo é uma sequência de instruções bem definidas, normalmente usadas para resolver problemas de matemática específicos, executar tarefas, ou para realizar cálculos e equações. A origem da palavra “algoritmo” remete a Al Khowarizmi, famoso matemático árabe do século IX. É uma sequência de raciocínios, instruções ou operações para alcançar um objetivo, sendo necessário que os passos sejam finitos e operados sistematicamente. Um algoritmo, portanto, conta com a entrada e saída de informações mediadas pelas instruções.
É fundamental compreender que o algoritmo se justifica no resultado que ele almeja alcançar, logo, deve ter um objetivo específico. Uma sequência de instruções simples pode se tornar mais complexa conforme a necessidade de considerar outras situações. Ele engloba vários cenários existente, veja, se um programa de computador trava, ele recebeu uma quantidade de informações que não foi programado para processar, não considerado então um cenário que poderia ter acontecido. É necessário seguir uma linha sistemática para no final coexistir com a teoria do que foi programado no começo, com o código, é a mesma coisa, sendo necessário ler linha por linha para que ele atinja o objetivo final. Com estruturas como "variáveis" e "comandos de repetição", o algoritmo fica mais completo e capaz de englobar múltiplas situações para permitir que o resultado final seja alcançado.
Quando juntas, essas técnicas trazem os necessários para estudos de topologia, agricultura e até o geoprocessamento de imagens com a ajuda de um satélite como proposto nesse trabalho. Conhecidos como Algoritmos de Ordenação, essas series de algoritmos utilizam diferentes técnicas de ordenação para organizar um conjunto de dados gerados por alguma tecnologia previamente programada.
Os métodos de ordenação se classificam em:
Ordenação Interna: onde todos os elementos a serem ordenados cabem na memória principal e qualquer registro pode ser imediatamente acessado.
Ordenação Externa: onde os elementos a serem ordenados não cabem na memória principal e os registros são acessados sequencialmente ou em grandes blocos, gasta-se mais recurso para tal operação, já que a máquina terá que acessar dados que não estão na memória principal, realizando assim uma transferência de dados em cada acesso lá e cá.
Na interna temos os Métodos Simples e os Métodos Eficientes, sendo o simples para pequenos vetores, programas pequenos e fáceis de entender, enquanto os eficientes são mais complexa nos detalhes e são projetados para trabalhar com uma quantidade maior de dados.
Na externa, como o acesso a memória secundaria é bem mais lento, a preocupação passa ser minimizar a quantidade de leituras e escritas nos dispositivos, por razões como esta que se utilizada o modelo simplificado para ordenação externa, pois preocupa-se com operações de transferências dos registros obtidos entre a primaria e secundária.
Referencial Teórico
A ideia por trás de aprender vários algoritmos para a organizaçãode dados é saber qual usar para melhorar desempenho ou legibilidade de código, dependendo da situação. Não precisamos, por exemplo, de um algoritmo "supercomplexo" para ordenar 10 valores em um vetor, pois seria ser uma perda de tempo para desenvolver um algoritmo tão complexo para algo tão simples.
É interessante conhecer sua complexidade no Pior Caso, Caso Médio e o melhor caso ao analisar um algoritmo de ordenação. Citando a complexidade do algoritmo através de notação matemática, estas três características presentes em todos os algoritmos dizem respeito a sua velocidade dada uma situação específica. 
Sabendo que os algoritmos de ordenação servem como uma forma de manipulação de dados colocando em ordem os elementos de uma dada sequência e efetuando sua ordenação, podendo ser completa ou parcialmente executada. 
A possibilidade de acessar os dados de maneira mais eficaz dentre muitas razões, é o principal gatilho para sua utilização. ordenando os dados de forma pratica e funcional em um algoritmo, acabada facilitando o acesso aos dados ordenados, deixando este processo mais rápido. 
Diversos algoritmos de ordenação foram criados diante várias ocasiões necessárias, destrincharei sobre alguns deles para se familiarizar, são eles:
Bogosort: não tão eficiente e nem muito utilizado, ele é baseado na reordenação aleatória dos elementos, pode ser usado no ensino de algoritmos mais eficientes. Sendo um algoritmo de ordenação não estável, possui número finito de estados e não são realmente aleatórios, podendo nunca terminar para certos conjuntos de valores a serem ordenados. Praticamente um método de tentativa e erro para os mais leigos.
Esse algoritmo é probabilístico por natureza. Se todos os elementos a serem ordenados são distintos, a complexidade esperada O(n x n!). O tempo exato de execução esperado depende dos quantos diferentes valores de elementos ocorrem, e quantas vezes cada um deles ocorre, mas para casos não-triviais o tempo esperado de execução é exponencial ou super-exponencial a n. Ele termina pela mesma razão do teorema do macaco infinito; existe alguma probabilidade de que aconteça a permutação correta, dado que em um infinito número de tentativas fatalmente a encontrará. (ASCENCIO, 2012).
Insertion Sort: também chamado de ordenação por inserção, funciona quando dado uma estrutura (lista) ele constrói uma matriz final com um elemento de cada vez, uma inserção por vez, acaba sendo bem eficiente com pequenas entradas, como os algoritmos de ordenação quadrática, ele acaba sendo o mais eficiente dentre a sua classificação.
O método de ordenação Insertion Sort funciona subdividindo a entrada de dados em duas listas, uma das quais receberá permutações de pedidos anteriormente chaves, enquanto o outro será decrementada durante todo o processo de ordenamento. Será usado um elemento que é chamado de eleito, que permitirá que as duas listas coexistam. Inicialmente, o primeiro elemento da entrada de dados será eleito, e o conteúdo desse elemento será, em seguida, ser comparado com os outros elementos do vetor i+1 até i+n. (COLLINGS, 1988). Esta é a ideia por trás da ordenação por inserção. Percorra as posições, começando com o índice 1 (um), cada nova posição você precisa inseri-la no lugar correto ordenado à esquerda daquela posição.
Selection Sort: conhecido como ordenação por seleção é um algoritmo de ordenação que se baseia em passar para a primeira posição o menor valor do vetor, podendo ser o maior, de acordo com a ordem pré-estabelecida, após essa tarefa o segundo de menor valor para a segunda posição e segue sucessivamente esta ordem até os dois últimos elementos, sempre efetuando as trocas para obter a ordenação. 
O Selection Sort compara a cada interação um elemento com os outros, visando encontrar o menor. Dessa forma, podemos entender que não existe um melhor caso mesmo que o vetor esteja ordenado ou em ordem inversa serão executados os dois laços do algoritmo, o externo e o interno. A complexidade deste algoritmo será sempre O(n²) enquanto que, por exemplo, os algoritmos Heapsort e Mergesort possuem complexidades O(n log n) (ASCENCIO, 2010), (COLLINGS, 1988).
Bubble Sort: ou ordenação por flutuação, é um dos mais simples. Com a ideia de percorrer o vetor diversas vezes, indo e voltando, e com isso levar para o topo o maior elemento da sequência que foi reconhecido, lembrando o jeito em que as bolhas buscam espaço para cima procurando o nível para estar, daí o nome dado a este método.
O elemento na posição i é comparado com o elemento na posição i+1, de forma crescente ou decrescente caso a condição da comparação for aceita então uma variável auxiliar irá guardar o valor de i+1 que então recebe o valor de i, então i recebe o valor contido na variável auxiliar, ocorrendo então a troca de posições entre os elementos (ASCENCIO, 2010), (COLLINGS, 1988).
Não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados. Pois este algoritmo percorre a lista de itens ordenáveis do início ao fim, verificando a ordem dos elementos dois a dois, e trocando-os de lugar se necessário. Percorre-se a lista até que nenhum elemento tenha sido trocado de lugar na passagem anterior.
Comb Sort: é relativamente simples, faz parte da família de algoritmos de ordenação por troca. Foi desenvolvido inicialmente por Wlodzimierz, mas só depois de redescoberto por Stephen e Richard em um artigo de uma revista foi popularizado (Wikipedia,2018). Ele melhora o algoritmo citado anteriormente e bate de frente com Quick Sort (será citado mais adiante).
Tem como ideia eliminar os pequenos valores, mas veja, apenas os que estão no final da lista, já que no Bubble estes retardam a classificação absurdamente. O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente, lá, quando quaisquer dois elementos são comparados, eles sempre têm uma distância um do outro de 1. O fator de encolhimento tem um grande efeito sobre a eficiência do Comb sort. No artigo original, os autores sugeriram 1,3 depois de tentar algumas listas aleatórias e encontrando-se, geralmente as mais eficazes. Um valor muito pequeno retarda o algoritmo porque mais comparações devem ser feitas, ao passo que um valor muito grande não pode tratar um número suficiente de pequenos dados para ser prático.
 A ideia básica do Comb é que a diferença pode ser muito mais do que um. O intervalo começa com o comprimento da lista a ser ordenada dividida pelo fator de encolhimento, e a lista é ordenada com este valor para o intervalo. Então, a diferença é dividida pelo fator de encolhimento novamente, a lista é ordenada com este novo gap, e o processo se repete até que a diferença seja de 1. Neste ponto, o Comb sort continua usando um espaço de 1 até que a lista esteja totalmente ordenada. A fase final da classificação é, portanto, equivalente a um Bubble sort, mas desta vez a maioria dos elementos pequenos já foram tratados. (AZEREDO, 1996).
Para aplicações mais complexas que acabam necessitando de alto nível de processamento, recomenda-se métodos mais sofisticados, pois, além de serem mais detalhados, apresentam uma quantidade menor de comparações, citarei alguns para comparações futuras.
Merge Sort: é um exemplo de algoritmo de ordenação por comparação do tipo que se divide pra conquistar. Sua ideia básica consiste em dividir o problema em pequenos problemas e resolvendo através da recursividade, e conquistar com a resolução desses problemas menores se unem para a resolução do problema mor.
Os três passos úteis dos algoritmos de divisão e conquista, que se aplicam ao merge sort são: 
Dividir, pois ele calcula o ponto médio do sub-arranjo, o que demora um tempo constante; 
Conquistar, porque recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui para o tempo de execução; 
Combinar, pois uni os sub-arranjos em um único conjunto ordenado, que leva o tempo (Cormen, Thomas, Charles, 2012)
HeapSort:ele é generalista e faz parte da família de algoritmos de ordenação por seleção desenvolvido em 1964. 
Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espetacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória. O Heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n log n). Lê-se logaritmo (ou log) de "n" na base 2. Para valores de n, razoavelmente grandes, o termo log n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar. (Sara,1988)
O Heapsort não é um algoritmo de ordenação estável. Porém, é possível adaptar a estrutura a ser ordenada de forma a tornar a ordenação estável. Cada elemento da estrutura adaptada deve ficar no formato de um par (elemento original, índice original). Assim, caso dois elementos sejam iguais, o desempate ocorrerá pelo índice na estrutura original.
O Heapsort utiliza uma estrutura de dados chamada heap, para ordenar os elementos à medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada, lembrando-se sempre de manter a propriedade de max-heap. A heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais [1]) ou como um vetor. Para uma ordenação decrescente, deve ser construída uma heap mínima (o menor elemento fica na raiz). Para uma ordenação crescente, deve ser construído uma heap máxima (o maior elemento fica na raiz).
Shell Sort: Dentre os de complexidade quadrática é o algoritmo de classificação mais eficiente, funciona como o método de inserção direta só que mais refinado. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção.
A ordenação Shell utiliza a quebra sucessiva da sequência a ser ordenada e implementa a ordenação por inserção na sequência obtida. Devido a sua complexidade possui excelentes desempenhos em N muito grandes, inclusive sendo melhor que o Merge Sort. (Azeredo,1996). A complexidade do algoritmo é desconhecida, ninguém ainda foi capaz de encontrar uma fórmula fechada para sua função de complexidade e o método não é estável.
Radix Sort: é um algoritmo de ordenação rápido e estável que pode ser usado para ordenar itens que estão identificados por chaves únicas. Cada chave é uma cadeia de caracteres ou número, e o Radix sort ordena estas chaves em qualquer ordem relacionada com a lexicografia. Na ciência da computação, Radix sort é um algoritmo de ordenação que ordena inteiros processando dígitos individuais. Como os inteiros podem representar strings compostas de caracteres e pontos flutuantes especialmente formatados, Radix sort não é limitado somente a inteiros.
 O tempo de execução de Radix parece ser melhor do que Quick Sort para uma ampla gama de números de entrada. Os fatores constantes escondidos na notação assintótica são mais elevados para Radix sort e Quick-Sort usa caches de hardware de forma mais eficaz. Além disso, o tipo Radix usa o tipo de contagem como uma sub-rotina e o tipo de contagem requer espaço extra para classificar números.
Computadores, na sua maioria, representam internamente todos os tipos de dados como números binários, por isso processar os dígitos na forma de inteiros em grupos representados por dígitos binários se torna mais conveniente. Existem duas classificações do Radix sort, que são:
Least significant digit (LSD – Dígito menos significativo)
Most significant digit (MSD – Dígito mais significativo)
O Radix sort LSD começa do dígito menos significativo até o mais significativo, ordenando tipicamente da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Os valores processados pelo algoritmo de ordenação são frequentemente chamados de “chaves”, que podem existir por si próprias ou associadas a outros dados. As chaves podem ser strings de caracteres ou números.
Já o Radix sort MSD trabalha no sentido contrário, usando sempre a ordem lexicográfica, que é adequada para ordenação de strings, como palavras, ou representações de inteiros com tamanho fixo.
Algoritmos de ordenação baseados em comparações oferecem flexibilidade por serem aptos a ordenar de outras formas que não a lexicográfica. No entanto, essa habilidade é de pouca importância em várias aplicações práticas. O algoritmo de ordenação Radix sort foi originalmente usado para ordenar cartões perfurados. 
Gnome Sort: Similar ao Insertion Sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma sequência grande de trocas assim como o Bubble sort. O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.
Baseado no conceito de um Gnomo jardim classificando seus vasos de flores. Um gnomo de jardim classifica os vasos de flores pelo seguinte método. 
Ele olha para o vaso de flores ao lado dele e o anterior; se estiverem na ordem correta, ele avança um pote, caso contrário, ele os troca e recua um pote.
Se não houver nenhum pote anterior (ele está no início da linha do pote), ele avança; se não houver pote próximo a ele (ele está no final da linha do pote), ele está pronto.
Counting Sort: é um algoritmo de ordenação estável cuja complexidade é O(n). As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1. 
A ideia básica do counting sort é determinar, para cada entrada x, o número de elementos menor que x. Essa informação pode ser usada para colocar o elemento x diretamente em sua posição no array de saída. Por exemplo, se há 17 elementos menores que x, então x pertence a posição 18. Esse esquema deve ser ligeiramente modificado quando houver vários elementos com o mesmo valor, uma vez que nós não queremos que sejam colocados na mesma posição.
Cria CNT[M+1] e B[max N]; Inicializa todas as posições de CNT a 0; Percorre o vector A e, para cada posição i de a faz CNT[A[i]-1]++ o que faz com que, no final, cada posição i de CNT contem o nº de vezes que a chave i-1 aparece em A; Acumula em cada elemento de CNT o elemento somado ao elemento anterior: CNT[i] indica a posição ordenada do primeiro elemento de chave i; Guarda em B os valores de A ordenados de acordo com B[CNT[A[i]++]=A[i]; Copia B para A; Counting-Sort trabalha como uma contadora de ocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem números repetidos, números únicos e números que não existem um outro vetor indica a quantidade de ocorrências. (Cormen,2001)
Esta implementação tem a desvantagem de precisar de vectores auxiliares. O Counting Sort ordena exclusivamente números inteiros pelo fato de seus valores servirem como índices no vetor de contagem.
Bucket Sort: ou bin sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucket sort recursivamente. O Bucket Sort tem complexidade linear quando o vetor a ser ordenado contém valores que são uniformemente distribuídos
Bucket sort funciona do seguinte modo: Inicialize um vetor de "baldes", inicialmente vazios;
Vá para o vetor original, incluindo cada elemento em um balde;Ordene todos os baldes não vazios; 
Coloque os elementos dos baldes que não estão vazios no vetor original. O tipo de balde é principalmente útil quando a entrada é uniformemente distribuída ao longo de uma faixa. Por exemplo, considere o seguinte problema. (Stein, Clifford 2012)
https://media.geeksforgeeks.org/wp-content/uploads/BucketSort.png
Se assumirmos que a inserção em um balde leva o (1) tempo, então os passos 1 e 2 do algoritmo acima claramente tomam O(n) tempo. O O(1) é facilmente possível se usarmos uma lista vinculada para representar um balde (No código a seguir, o vetor C++ é usado para simplificar). O passo 4 também leva o(n) tempo, pois haverá n itens em todos os baldes.
O passo principal a ser analisado é o passo 3. Esta etapa também leva O(n) tempo em média se todos os números são distribuídos uniformemente (por favor, encaminhe o livro CLRS para mais detalhes)
A seguir está a implementação do algoritmo acima.
Cocktail Sort: também conhecido como bubble sort bidirecional, cocktail sort, shaker sort (o qual também pode se referir a uma variação do insertion sort), ripple sort, shuffle sort, ou shuttle sort, dentre muitos nomes a função é a mesma,
É uma variante do bubble sort, que é um algoritmo com não-estável e efetua Ordenação por comparação. O algoritmo difere de um bubble sort no qual ordena em ambas as direções a cada iteração sobre a lista. Esse algoritmo de ordenação é levemente mais difícil de implementar que o bubble sort, e e resolve o problema com os chamados coelhos e tartarugas no bubble sort. Ele possui performance levemente superior ao bubble sort, mas não melhora a performance assintótica; assim como o bubble sort, não é muito usado na prática (insertion sort é escolhido para ordenação simples), embora seja usado para fins didáticos.
A complexidade do Cocktail shaker sort em notação big-O é O(n²) para o pior caso e caso médio, mas tende a se aproximar de O(n) se a lista se encontra parcialmente ordenada antes da execução do algoritmo. Por exemplo, se cada elemento se encontra em uma posição cuja distância até sua posição ordenada é k (k ≥ 1), a complexidade do algoritmo se torna O(kn). (Paul, 2009)
Timsort: é um algoritmo de ordenação híbrido derivado do merge sort e do insertion sort, projetado para ter boa performance em vários tipos de dados do mundo real. Foi inventado por Tim Peters em 2002 para ser usado na linguagem de programação Python, e tem sido o algoritmo de ordenação padrão de Python. Ele atualmente é usado para ordenar arrays em Java.
Tim Peters descreve o algoritmo da seguinte forma: "[...]um adaptativo, estável, merge sort natural, modestamente chamado de timsort (hey, eu mereço <wink>). Tem desempenho sobrenatural em muitos tipos de arrays parcialmente ordenados (menos de lg(N!) comparações necessárias, e tão poucas quanto N-1), no entanto, tão rápido quanto o algoritmo anterior altamente sintonizado, híbrido, samplesort de Python em matrizes aleatórias. Em suma, a rotina principal passa sobre a matriz uma vez, da esquerda para a direita, alternadamente, identificando o próximo passo, em seguida, fundindo-os em passos anteriores "inteligentemente". Todo o resto é complicação pela velocidade, e alguma medida duramente conquistada da eficiência de memória."
O algoritmo baseia-se na ideia de que, no mundo real, um vetor de dados a ser ordenado contém sub-vetores já ordenados, não importando como (decrescentemente ou crescentemente). Assim, o TimSort está à frente da maioria dos algoritmos de ordenação, mesmo não apresentando descobertas matemáticas complexas. O fato é que na realidade o TimSort não é um algoritmo autônomo, mas um híbrido, uma combinação eficiente de outros algoritmos, temperado com as ideias do autor. 
Quick Sort: é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante. Naquela época, Hoare trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. Ele criou o quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rápido. Foi publicado em 1962 após uma série de refinamentos.
O quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. Os passos são: Escolha um elemento da lista, denominado pivô; Particiona: rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sub listas não ordenadas. Essa operação é denominada partição; recursivamente ordene a sub lista dos elementos menores e a sub lista dos elementos maiores;
O caso base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte. A escolha do pivô e os passos do Particiona podem ser feitos de diferentes formas e a escolha de uma implementação específica afeta fortemente a performance do algoritmo.
Apresentado todos esses algoritmos de ordenação, percebemos métodos de funcionamentos usados de diferentes modos, mas com o mesmo princípio. É importante falar um pouco deles também, para maior entendimento do funcionamento.
Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear (ou busca sequencial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logaritmo.
No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos. No caso médio, o elemento é encontrado após (N+1)/2 comparações. O algoritmo de busca linear é um algoritmo O(n).
Outro método bastante citado anteriormente é a pesquisa ou busca binária, que é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
A minha escolha para o desenvolvimento do trabalho da forma como foi pedido, conforme a avaliação feita a partir de pesquisas realizadas em livros e sites sobre os algoritmos de ordenação e da forma como foi apresentado os cenários possíveis, cheguei a alguns melhores para a identificação desse determinado cenário.
Desenvolvimento
INSERTION SORT
Começaremos nos aprofundando no Insertion Sort com exemplos, explicações mais detalhadas sobre seu uso/funcionamento, com imagens e códigos e relembrando o que foi dito sobre este algoritmo.
Lembra-se que ele é um algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez.
Para familiarizar vamos perceber um exemplo que é mais presente em cotidianos alheios. Podemos fazer uma comparação do Insertion Sort com o modo como algumas pessoas organizam um baralho num jogo de cartas. Imagine que vocêestá jogando às cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma a que as cartas obedeçam à ordenação.
A cada nova carta adicionada à sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, a sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim em diante, até não receber mais cartas.
Percebemos isso na sequência de figuras abaixo:
Primeiro o "6" é selecionado e colocado pra depois do número "5" pois é maior;
Na sequência, os próximos números são escolhidos para entrar na sequencia correta (3 e 1);
Como os dois números são menores dos que já tinham sido ordenados, eles fica antes dos mesmos, senão ficariam depois assim como no exemplo acima;
este processo é repetido até o ultimo número ser selecionado (4) e colocado na ordem correta, assim arrumando toda sequencia como deve ser.
Com uma tabela mais intuitiva e para facilitar o entendimento, mesmo que feita com elementos diferentes, conclui-se que:
Escolha um elemento, compare o elemento atual ao seu antecessor
Se o elemento escolhido for menor que o seu antecessor, compare-o com os elementos anteriores. Mova os elementos maiores uma posição para cima para abrir espaço para o elemento trocado. Como mostrado abaixo:
CARACTERISTICAS
· É 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á ordenada;
· 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.
Para a ordenação de uma matriz ordenada de forma aleatória, com diferentes chaves, o algoritmo - Insertion Sort-, se utiliza de ¼ N² comparações e ½ N² trocas. 
Para o caso médio, assume que todas as permutações de entrada são igualmente prováveis. Com a auxílio de funções geradoras, o caso médio do Insertion sort.
Para o melhor caso (itens já ordenados) temos;
1=n-1=O(n)
Pior caso (itens em ordem reversa) temos: 
i=(n-1)(n)/2 = n²/2 – n/2 = O(n²)
VANTAGENS E DESVANTAGENS
PRÓS:
· É o método a ser utilizado quando o arquivo está "quase" ordenado
· É um bom método quando se desejar adicionar poucos elementos em um arquivo já ordenado, pois seu custo é linear.
· O algoritmo de ordenação por inserção é estável.
CONTRA:
· Alto custo de movimentação de elementos no vetor.
COMB SORT
Seu método tem muito de outros métodos, ainda mais eficiente do que seus similares. O algoritmo Comb Sort repetidamente reordena diferentes pares de dados, separados por um intervalo, que é calculado a cada passagem. Esse método é similar ao Bubble Sort, só que mais eficiente. No algoritmo Bubble, quando dois dados são comparados, eles sempre têm um intervalo (distância um do outro) de 1. No caso do Comb Sort, esse intervalo pode ser muito maior que 1. Vemos na figura abaixo uma representação teórica do seu funcionamento:
O algoritmo Comb Sort tem como princípio de funcionamento (como ilustrado na figura acima) uma variável chamada intervalo (gap) que começa com o comprimento do vetor (lista de dados) a ser ordenada dividido pelo fator de encolhimento (valor geralmente 1,3 ou 1,24), e os valores presentes no vetor são ordenados com o valor do intervalo sendo arredondado para um número inteiro. Então, a diferença é dividida pelo fator de encolhimento novamente, com isso os dados são ordenados novamente com um novo valor de intervalo, e o processo se repete até que a diferença seja de 1.
O fator de encolhimento tem um grande efeito sobre a eficiência do Comb sort. No artigo original, os autores sugeriram 1,3 depois de tentar algumas listas aleatórias e encontrando-se, geralmente as mais eficazes. Um valor muito pequeno retarda o algoritmo porque mais comparações devem ser feitas, ao passo que um valor muito grande não pode tratar um número suficiente de "tartarugas" para ser prático.
O texto descreve uma melhoria no comb sort usando o valor base aproximado de 1.247330950103979 como fator de encolhimento. Ele também contém uma implementação em pseudocódigo com uma tabela de gaps pré-definidos.
Quando os valores estão ordenados na ordem crescente, na descrição, não tem a necessidade de troca e quando os dados estão ordenados em ordem decrescente e o algoritmo tem que ordenar de forma decrescente, pois terá que trocar de posição todos os valores e o caso mediano é quando os valores estão ordenados de forma aleatória o Comb pode ou não ter que trocar os lugares dos dados no vetor, porque ele pode já estar no lugar correto.
VARIAÇÕES
Combsort11
Com um fator de encolhimento de cerca de 1,3, só existem três caminhos possíveis para a lista de gaps terminar: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), ou (11, 8, 6, 4, 3, 2, 1). Experimentos mostram que melhorias significativas de velocidade podem ser feitas se o gap for definido como 11, sempre que, caso contrário, tornar-se 9 ou 10. Esta variação é chamada Combsort11.
Se uma das sequências que começam com nove ou 10, forem utilizadas, o passo final, com um intervalo de 1 tem menor probabilidade de ordenar os dados sendo necessário então outro passo com gap de 1. Os dados são ordenados quando não ocorrem mais trocas durante uma passagem com gap= 1.
Também é possível usar uma tabela pré-definida, para escolher quais gaps a utilizar em cada passo.
Combsort com diferentes finais
Como muitos outros algoritmos eficientes de ordenação, o comb sort é mais eficaz em suas passagens anteriores do que durante o passo final, quando ele se assemelha a um bubble sort. O Comb sort pode ser mais eficaz se o método de classificação é mudado uma vez que os gaps cheguem a um número pequeno o suficiente. Por exemplo, uma vez que a diferença chegue a um tamanho de cerca de 10 ou menor, parando o comb sort e fazendo um simples gnome sort ou cocktail sort, ou, melhor ainda, um insertion sort, se aumentará a eficiência global da ordenação.
Outra vantagem deste método é que não há necessidade de manter o controle das operações de troca durante os passos da classificação para saber se a ordenação deve parar ou não.
ALGORITMO OU FUNCIONAMENTO
Esse algoritmo funciona da seguinte forma dado o tamanho do vetor, uma variável chamada intervalo receberá o valor da divisão entre o tamanho do vetor e o fato de encolhimento. Posteriormente, o algoritmo estará no laço While se o valor do intervalo for maior que 0 e uma variável chamada troca for diferente do valor do tamanho do vetor – 1. Em seguida, dada as condições no laço While forem verdadeiras o algoritmo entrará em um novo laço de repetição o For que iniciará com uma contagem de valor igual a 0 e se encerrará quando o valor da contagem inicial (i) mais o valor do intervalo for maior ou igual ao valor do tamanho do vetor. 
O if é responsável por comparar o valor da posição i número[i] com o valor da posição i + intervalo número[i + intervalo] se número[i] for maior número[i + intervalo]então acontecerá uma troca com ajuda da variável aux. No caso, a aux. receberá o valor de número[i] e número[i] receberá o valor número [i + intervalo] e para completa o processo de troca o número [i + intervalo] recebe o valor da variável aux. 
Por fim, o intervalo será dividido novamente pelo fator de encolhimento gerando um novo valor que será usado na nova repetição. Quando as condições não forem mais verdadeiras no While o algoritmo se encerra e é gerado na tela o resultado dos valores ordenados. Essealgoritmo foi implementado para que além de ordenar o vetor, também retorne o valor da quantidade de trocas e o valor da quantidade de comparações
Selection Sort
Torna estática uma posição do vetor e analisa os índices para encontrar o menor ou maior valor e cambiar os elementos. Em outras palavras o algoritmo seleciona um elemento da lista e exerce uma comparação com os demais componentes e quando encontra um menor ou maior, realoca para a primeira posição. Este procedimento se repete até que todos os valores estejam ordenados.
Assim como o método Bubblesort, utilizando o SelectionSort em listas muito extensas de dados, não poderemos obter bons resultados, por seu algoritmo como o do Bubblesort é de ordem quadrática, ou seja, ele utiliza-se de dois elementos do vetor duas vezes para obter a ordenação completa.
Repare na seguinte sequência que será colocada em ordem crescente:
O algoritmo seleciona o valor do primeiro índice (5) e compara com o segundo (1). Se for maior, realiza-se a troca; caso contrário, mantêm-se o elemento estático.
Uma vez realizado a troca o algoritmo seleciona o menor valor (1) e compara com o terceiro (6). A lógica se repete até que todos os elementos estejam ordenados.
Vantagens e desvantagens:
Vantagens:
· Ele é um algoritmo simples de ser implementado em comparação aos demais.
· Não necessita de um vetor auxiliar (in-place).
· Por não usar um vetor auxiliar para realizar a ordenação, ele ocupa menos memória.
· Ele é uns dos mais velozes na ordenação de vetores de tamanhos pequenos.
Desvantagens:
· Ele é um dos mais lentos para vetores de tamanhos grandes.
· Ele não é estável.
· Ele faz sempre {\displaystyle (n^{2}-n)/2} comparações, independentemente do vetor estar ordenado ou não.
Timsort
O algoritmo ordena um segmento específico do vetor de entrada incrementalmente da esquerda para a direita, buscando por consecutivos elementos ordenados. Se esses segmentos não forem grandes o suficiente eles são estendidos e ordenados usando o InsertionSort. A posição de início e o tamanho dos segmentos gerados são armazenados em uma pilha. Durante a execução alguns desses segmentos são combinados (via Mergesort) de acordo com condições analisadas sobre os elementos que estão no topo da pilha, garantindo que os comprimentos dos segmentos gerados estão diminuindo e o comprimento de cada segmento gerado é maior que a soma dos próximos dois. No final, faz-se o merge de todos elementos restante, resultando em um vetor ordenado.
TimSort é um algoritmo de ordenação bastante eficiente se comparado aos demais existentes na literatura. Isso o levou a ser escolhido como algoritmo de ordenação padrão em linguagens de programação como Python e Java.
O mecanismo do algoritmo pode ser explicado brevemente da seguinte maneira:
1. Um algoritmo específico é usado para dividir o vetor de entrada em sub-vetores.
2. Cada sub-vetor é ordenado usando um simples InsertionSort estável.
3. Os sub-vetores ordenados são mesclados com o uso do MergeSort.
Observação: Algumas otimizações são feitas no passo 1, na divisão em sub-vetores, e no MergeSort.
Definições do algoritmo:
1. N: Comprimento do vetor de entrada.
2. Run: Um sub-vetor ordenado que compõe o vetor de entrada.
3. Minrun: É o comprimento mínimo dos Runs. Este número é calculado baseado no tamanho do vetor de entrada (N).
Otimizações
Algumas otimizações são feitas no MergeSort utilizado no TimSort visando diminuir o custo do algoritmo, mais precisamente o espaço de memória adicional e o número de comparações. Em algumas implementações, geralmente cria-se um vetor temporário cujo tamanho é dado pela soma dos dois sub-vetores de entrada. Porém isso não é necessário quando deseja-se fazer o merge de dois sub-vetores cujos elementos são consecutivos, pois criar um vetor temporário com o tamanho do menor sub-vetor é suficiente. O processo de merge pode ser feito da seguinte forma:
1. Um vetor temporário é criado com o tamanho do menor dos dois Runs que são combinados.
2. Copia-se o Run mais curto para o vetor temporário.
3. Marca-se a posição corrente com os primeiros elementos do maior Run e do "Run" temporário.
4. Em cada passo seguinte compare os primeiros elementos do maior Run e do Run temporário e mova o menor para o vetor ordenado. Move-se (incrementa) o endereço base do Run que teve o elemento movido.
5. Repete o passo 4 até um dos Runs esvaziar.
6. Adiciona todos os elementos do Run remanescente para o final 
7. do Run ordenado.
Processo de merge no TimSort
Caso o Run da direita seja menor, a comparação é feita marcando o endereço base do Run da esquerda e do Run temporário na última posição válida e ambos os vetores são percorridos da direita para a esquerda, sempre buscando o maior elemento em vez do menor.
Galopeamento binário adotado no processo de merge do TimSort.
O galopeamento binário é uma técnica que minimiza o custo de comparações, entretanto deve ser chamada apenas quando se percebe que os dados apresentam o padrão em que ela pode ser empregada. Caso essa função fosse chamada em todos os casos, seriam exigidas mais comparações do que a busca linear. Nota-se também que caso o Run da esquerda seja menor, o galopeamento binário é feito da esquerda para a direita, caso contrário é feito no sentido oposto.
A análise de complexidade aqui presente, é baseada no artigo, onde o autor prova que o custo de comparações para o pior caso no TimSort é {\displaystyle O(nlogn)}.
Considerações do autor:
1. O merge considera o Run como sendo um único elemento, e neste caso o custo de decomposição de cada Run será constante.
2. O custo de dois Runs é definido como {\displaystyle c(R,R0)-1}, onde {\displaystyle c(R,R0)=|R|+|R0|}.
3. O autor não utiliza o tamanho dos Runs como sendo Minrun, ou seja, ele não usa tamanhos artificiais de Runs, apenas considera Runs que realmente estejam originalmente ordenados. Logo não existe o custo relacionado à ordenação feita pelo Insertion sort.
4. Não são consideradas as otimizações do merge. Isso não implica mudanças da análise do pior caso.
O autor também define um conjunto de regras, propostas no trabalho, que visavam tornar o algoritmo do TimSort correto após a detecção de um erro gerado na implementação usada na linguagem Java. Abaixo são apresentadas as regras e as implicações caso as mesmas NÃO sejam satisfeitas, onde {\displaystyle W,X,Y,\mathrm {Z} }W, X, Y, Z são os 4 elementos que estão no topo da pilha
Dividimos o Array em blocos conhecidos como Run. Classificamos essas corridas usando a inserção tipo um a um e, em seguida, mesclamos essas corridas usando a função combinada usada no tipo de mesclagem. Se o tamanho do Array for menor do que o executado, então o Array será classificado apenas usando o Insertion Sort. O tamanho da corrida pode variar de 32 a 64, dependendo do tamanho da matriz. Observe que a função de fusão funciona bem quando as subarrays de tamanho são poderes de 2. A ideia baseia-se no fato de que o tipo de inserção funciona bem para pequenas matrizes.
Algoritmos de TimSort
· Inicialize uma RUN com o tamanho de 32.
· Implementar o tipo de inserção para pedaços de tamanho RUN.
· Uma fusão de função (int arr[], int l, int m, int r) leva uma matriz, elementos esquerdos, no meio da matriz e elementos certos da matriz como entrada. A função retorna os pedaços mesclados do tamanho 32.
· Inicialize o comprimento da matriz tendo todos os elementos esquerdos e o comprimento da matriz tendo todos os elementos certos.
· Depois de preencher a matriz esquerda e a matriz direita, iterar sobre a matriz esquerda, bem como a matriz direita.
· Se o elemento na matriz esquerda for menor que o elemento na matriz direita, empurre o elemento para uma matriz maior.
· Caso contrário, empurre o elemento para uma matriz menor de acordo.
· Copie o elemento restante na matriz esquerda e na matriz direita em uma matriz maior.
· Uma função timSortAlgo (int arr[], int n) toma uma matriz e seu tamanho como entrada. Que chama a inserção de sort inicialmente e mescla os elementos de matriz.
· Retorne a saídacomo os elementos finais da matriz usando Tim Sort.
A matriz tem menos de 64 elementos nele
Se a matriz que estamos tentando classificar tem menos de 64 elementos nele, Timsort executará um tipo de inserção.
Um tipo de inserção é um tipo simples que é mais eficaz em listas pequenas. É bastante lento em listas maiores, mas muito rápido com listas pequenas. A ideia de um tipo de inserção é a seguinte:
· Olhe para elementos um por um
· Construa a lista classificada inserindo o elemento no local correto
Aqui está uma tabela de rastreamento mostrando como o tipo de inserção classificaria a lista [34, 10, 64, 51, 32, 21]
Enquanto Timsort está fundindo A e B, ele nota que uma corrida foi "ganhar" muitas vezes seguidas. Se descobrisse que a corrida A consistia em números totalmente menores do que a corrida B, então a corrida A acabaria de volta em seu lugar original. A fusão das duas corridas envolveria muito trabalho para não conseguir nada.
Na maioria das vezes, os dados terão alguma estrutura interna pré-existente. Timsort assume que se muitos valores de execução A são inferiores aos valores da série B, então é provável que A continue a ter valores menores que B.
Timsort, então, entrará no modo galopando. Em vez de verificar A[0] e B[0] um contra o outro, Timsort realiza uma busca binária pela posição apropriada de b[0] em um[0]. Assim, Timsort pode mover uma seção inteira de A para o lugar. Em seguida, Timsort procura a localização apropriada de A[0] em B. Timsort, em seguida, moverá uma seção inteira de B de uma só vez, e no lugar.
Vamos ver isso em ação. Timsort verifica B[0] (que é 5) e usando uma pesquisa binária ele procura o local correto em A.
Bem, B[0] pertence ao fundo da lista de A. Agora Timsort verifica para A[0] (que é 1) na localização correta de B. Então, estamos olhando para ver onde o número 1 vai. Este número vai no início de B. Agora sabemos que B pertence ao final de A e A pertence no início de B.
Acontece que essa operação não vale a pena se o local apropriado para B[0] estiver muito próximo do início de A (ou vice-versa). então o modo galope sai rapidamente se não estiver valendo a pena. Além disso, Timsort toma nota e torna mais difícil entrar no modo galope mais tarde, aumentando o número de vitórias consecutivas apenas A ou B necessárias para entrar. Se o modo galope está valendo a pena, Timsort torna mais fácil reentrar.
Quicksort
O algoritmo QuickSort utiliza-se de ordenação por divisão e conquista, partindo disto, dividimos os elementos de forma que eles se arranjem em duas partes para que assim sejam ordenados separadamente antes de retornarmos a uni-los.
Melhor dizendo, num conjunto de elementos onde necessitam ser ordenados, a ordenação por divisão e conquista utiliza-se primeiramente de um pivô, que seria definido como o elemento central do grupo, e os grupos seriam definidos de tal forma que os elementos anteriores ao pivô sejam menores do que ele e os elementos posteriores ao pivô sejam maiores do que ele. Após esta separação entre os valores maiores e menores do conjunto, definimos um novo pivô entre os conjuntos criado, novamente ordenando eles de forma em que os maiores estejam à direita do novo pivô e os menores a esquerda do novo pivô. Assim, continuamos criando subgrupos e escolhendo novos pivôs dentro dos subgrupos até que todos estejam devidamente ordenados e volte à junção do grupo num total.
O caso base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.
A escolha do pivô e os passos do Particiona podem ser feitos de diferentes formas e a escolha de uma implementação específica afeta fortemente a performance do algoritmo.
Método de partição de Lomuto
Método atribuído a Nico Lomuto e popularizado por Bentley em seu livro Programming Pearls[4] e por Cormen et al. no livro Introduction to Algorithms. Este método escolhe um pivô tipicamente no início ou no final do array. O Particiona recebe como parâmetro dois índices do array, lo e hi, que será a parte do array a ser particionada, então escolhe-se um índice i e percorre-se o array usando outro índice j realizando trocas, quando necessário, a fim de que todos os elementos menores ou iguais ao pivô fiquem antes do índice i e os elementos i + 1 até hi, ou j - 1, sejam maiores que o pivô. Esta é a maneira mais simples e fácil de entender, geralmente utilizada como uma introdução ao quicksort, entretanto é menos eficiente que o método Hoare. Este Método decai para O(n2) quando o array já está ordenado ou quando só possui elementos iguais. Existem várias formas para melhorar a eficiência do algoritmo através da escolha do pivô, lidar com elementos iguais, usar outros algoritmos para pequenos arrays como o Insertion sort e assim por diante.
Complexidade :
Comportamento no pior caso
O pior caso de particionamento ocorre quando o elemento pivô divide a lista de forma desbalanceada, ou seja, divide a lista em duas sub listas: uma com tamanho 0 e outra com tamanho n - 1 (no qual n se refere ao tamanho da lista original). Isso pode ocorrer quando o elemento pivô é o maior ou menor elemento da lista, ou seja, quando a lista já está ordenada, ou inversamente ordenada.
Se isso acontece em todas as chamadas do método de particionamento, então cada etapa recursiva chamará listas de tamanho igual à lista anterior - 1. Teremos assim, a seguinte relação de recorrência:
Se somarmos os custos em cada nível de recursão, teremos uma série aritmética que tem valor {\displaystyle \theta (n^{2})}0(n²), assim, o algoritmo terá tempo de execução igual à {\displaystyle \theta (n^{2})}0(n²).
Comportamento no melhor caso
O melhor caso de particionamento acontece quando ele produz duas listas de tamanho não maior que n/2, uma vez que uma lista terá tamanho [n/2] e outra tamanho [n/2] - 1. Nesse caso, o quicksort é executado com maior rapidez. A relação de recorrência é a seguinte:
que, a partir do teorema mestre, terá solução {\displaystyle T(n)=O(n*log(n))}
· Complexidade de espaço: {\displaystyle \theta (log_{2}n)}0(log2n) no melhor caso e no caso médio e {\displaystyle \theta (n)}0(n) no pior caso. R. Sedgewick desenvolveu uma versão do quicksort com partição recursão de cauda que tem complexidade {\displaystyle \theta (n^{2})}0(n) no pior caso.
Quicksort utilizando dois ou mais pivôs
Dentre inúmeras tentativas de melhorar a eficiência do quicksort clássico, em 2009 foi proposto por Yaroslavskiy (2009) o Dual-Pivot Quicksort[5] , onde são utilizados 2 pivôs, particionando um array de entrada em 3 partes. Yaroslavskiy demonstra que o uso de dois pivôs é mais eficaz, especialmente quando possui uma quantidade maior de dados de entrada, comprovando a sua vantagem em relação ao algoritmo quicksort clássico.
O algoritmo Dual-Pivot Quicksort, particiona um array de entrada de dados de diferentes dados primitivos (tais como, int, char, double float e long) em três partes, utilizando dois pivôs P1 e P2. Desse modo, estabelecem os seguintes ponteiros, L, K, G e left e right (índices para o primeiro e último elementos).
Segue abaixo a descrição do algoritmo.
1. Para pequenos vetores (tamanho < 17) utilizar o algoritmo Insertion Sort.
2. Escolha dois pivôs (P1 e P2), podemos escolher por exemplo, o primeiro (a[left]) elemento como P1 e o último como P2.
3. P1 deve ser menor do que o P2, caso contrário, eles são trocados. Então, existem as seguintes partes:
1. Parte I: com índices elemento mais a esquerda, de left até L-1 contendo os elementos que são menores que o P1.
2. Parte II: com índices de L até K-1 contendo os elementos maiores ou iguais a P1 e menores ou iguais a P2.
3. Parte III: Com índices de G + 1 até o último elemento a direita, contendo os elementos superiores P2.
4. Parte IV: contendo os elementos a ser examinados com índices de K até G
4. O próximo elemento na posição K pertencente a parte IV é comparado com os pivôs P1 e P2, e alocado na partecorrespondente, I, II ou III.
5. Os ponteiros L, K e G são alterados nas direções correspondentes.
6. Os passos 4 e 5 são repetidos enquanto G se aproxima de K.
7. O pivô P1 é trocado com o último elemento da parte I, o pivô P2 é trocado com o primeiro elemento da parte III.
8. As etapas 1 e 7 são repetidas de forma recursiva para cada parte I, II e III.
Comparação com outros algoritmos de ordenação
Gráfico comparativo, exibindo o comportamento assintótico de alguns algorítmos de ordenação.
O quicksort é uma versão optimizada de uma árvore binária ordenada. Em vez de introduzir itens sequencialmente numa árvore explicita, o quicksort organiza-os correntemente na árvore onde está implícito, fazendo-o com chamadas recursivas à mesma. O algoritmo faz exatamente as mesmas comparações, mas com uma ordem diferente.
O algoritmo que mais se familiariza com o quicksort é o Heapsort. Para o pior caso neste algoritmo temos {\displaystyle {\mathcal {O}}(n\log 2n).} Mas, o Heapsort em média trata-se de um algoritmo mais lento que o quicksort, embora essa afirmação já tenha sido muito debatida. No quicksort permanece o caso do pior caso, à exceção quando se trata de usar a variante Intro sort, que muda para Heapsort quando um pior caso é detectado. Caso se saiba à partida que será necessário o uso do heapsort é aconselhável usá-lo diretamente, do que usar o introsort e depois chamar o heapsort, torna mais rápido o algoritmo.
O quicksort também compete com o Mergesort, outro algoritmo de ordenação recursiva, tendo este o benefício de ter como pior caso {\displaystyle {\mathcal {O}}(n\log n).} Mergesort, ao contrário do quicksort e do Heapsort, é estável e pode facilmente ser adaptado para operar em listas encadeadas e em listas bastante grandes alojadas num tipo de acesso lento a média como um Network-Attached Storage ou num disco. Embora o quicksort possa ser operado em listas encadeadas, por vezes escolhendo um mau pivô sem acesso aleatório. A maior desvantagem do Mergesort é que quando opera em arrays, requer {\displaystyle {\mathcal {O}}(n)}espaço para o melhor caso, considerando que o quicksort com um particionamento espacial e com recursão.
Bucket sort com dois buckets é muito parecido ao quicksort (quase idêntico), o pivô neste caso é garantidamente o valor do meio do vector.
Conclusão
No trabalho foi apresentado o que são métodos de ordenação, alguns mais conhecidos, outros menos, porem com vantagem em usos específicos, foi explicado como funcionam, seus desempenhos e métodos utilizados, e foram também aplicados em vários exemplos citados na dissertação do trabalho.
Algoritmo de ordenação em ciência da computação é um algoritmo, de manipulação de dados, que coloca os elementos de uma dada sequência em uma certa ordem em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica. Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.
É um esquema de resolução de um problema. Pode ser implementado com qualquer sequência de valores ou objetos que tenham uma lógica infinita, ou seja, qualquer coisa que possa fornecer uma sequência lógica.
Problemas são questões propostas em busca de uma solução. Com o propósito de conceder uma solução para certo problema, existem os algoritmos, cada problema que é definível possui um algoritmo que determina uma solução para cada instância desse problema. Os algoritmos de ordenação, que servem para ordenar/organizar uma lista de números ou palavras de acordo com a sua necessidade. Por esse motivo foi citado alguns que melhor desempenhavam em suas funções, ou por fator de praticidade ou desempenho e até pela economia de tempo e dinheiro dependendo dos casos.
Dos exemplos dados, percebemos que Insertion e Selection são algoritmos de ordenação que possuem uma leitura fácil, podendo ser atribuídos em diferentes linguagens como C, C++, Java e Phyton, pois tem a vantagem de serem eficientes para resoluções menores, não devendo ser utilizadas em aplicações que requerem um alto nível de processamento, aplicações que sejam muito complexas requerem métodos com comparações menores e mais sofisticados.
O Quick é um desses métodos de ordenação interna que são eficientes, com isso podendo ser aplicado em uma gama de variações muito maior, talvez o mais utilizado dos algoritmos de ordenação, usando a estratégia de dividir em dois problemas menores os resultados são combinados posteriormente obtendo a resposta final.
Ele mostra um crescimento mais estabilizado e menor ao longo das escalas de entrada, se comparar os tempos de execução desenvolvidos por seus concorrentes, ele é esplêndido, ainda com suas escalas de entrada mais ágeis ele pode ter seu custo e demanda de tempo maior que o esperado.
O algoritmo Comb rivaliza com o Quick por ser tão simples quanto, eliminando pequenos valores e usando seu método de ordenação por troca, ele reordena diferentes pares de itens, aprimorando algoritmos como o Bubble. Como muitos outros algoritmos eficientes de ordenação, o comb sort é mais eficaz em suas passagens anteriores do que durante o passo final.
O Comb sort pode ser mais eficaz se o método de classificação é mudado uma vez que os gaps cheguem a um número pequeno o suficiente. Por exemplo, uma vez que a diferença chegue a um tamanho de cerca de 10 ou menor, parando o comb sort e fazendo a continuação da resolução por meio de outros métodos como o simples Insertion citado a pouco, aumentando a eficiência da ordenação. Outra vantagem deste método é que não há necessidade de manter o controle das operações de troca durante os passos da classificação para saber se a ordenação deve parar ou não.
Derivado do Insertion, o Tim é o mais diferente de todos pois é hibrido, podendo ser aplicado em vários projetos do mundo real, vem sendo o algoritmo de ordenação padrão de Python, possui um desempenho extraordinário em tipos de arrays parcialmente ordenados, tão rápido quanto seu antecessor, ele funde os passos pelo qual foi feito, utilizando a eficiência da memória ele usa da velocidade para tirar uma resolução estável.
Por esses motivos TimSort é um algoritmo de ordenação bastante eficiente se comparado aos demais existentes na literatura. Isso o levou a ser escolhido como algoritmo de ordenação padrão em linguagens de programação como Python e Java.
Referências Bibliográficas
https://pt.wikipedia.org/wiki/Ordena%C3%A7%C3%A3o_(computa%C3%A7%C3%A3o)
https://pt.wikibooks.org/wiki/Algoritmos_e_Estruturas_de_Dados/Algoritmos_de_Ordena%C3%A7%C3%A3o#:~:text=Algoritmo%20de%20ordena%C3%A7%C3%A3o%20%C3%A9%20uma%20implementa%C3%A7%C3%A3o%20em%20uma,principais%20s%C3%A3o%20Selection%20Sort%2C%20Bubble%20Sort%20e%20Quicksort.
https://exame.com/ciencia/inpe-divulga-imagens-surpreendentes-feitas-pelo-satelite-amazonia-1-veja/
https://rockcontent.com/br/blog/algoritmo/
https://www.treinaweb.com.br/blog/conheca-os-principais-algoritmos-de-ordenacao/
https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261#:~:text=Os%20mais%20populares%20algoritmos%20de,Heap%20sort%20e%20Shell%20sort.
https://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o
https://hackernoon.com/
“Introduction to Algorithms”, de (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein)
“Algorithms Unlocked”, de (Thomas H. Cormen)
CODELOGICA – A diferença é que aqui funciona (wordpress.com)
Escola online para desenvolvedores | TreinaWeb.com.br
Algoritmos de Ordenação: Análise e Comparação (devmedia.com.br)
2