Giter Site home page Giter Site logo

algoritmos-ordenacao's Introduction

Header 📎 Códigos desenvolvidos para a cadeira de Algoritmos e Estrutura de Dados da CESAR School.

Badge Badge Badge Badge

Como utilizar

Haskell

Antes de iniciar, instale a plataforma do Haskell em seu computador. Se você estiver no linux, basta copiar a seguinte linha no seu terminal:

$ sudo apt-get install haskell-platform

Clone este repositório:

$ git clone <https://github.com/anabxms/algoritmos-ordenacao>

Abra o GHCI, que é o modo interativo do Haskell

$ ghci

Agora, você poderá carregar as funções digitando :l sorting_algorithms.hs, desde que o arquivo esteja na mesma pasta na qual o ghci foi invocado.

C

Clone este repositório:

$ git clone <https://github.com/anabxms/algoritmos-ordenacao>

Abra o terminal e compile o programa:

gcc-10 sorting_algorithms.c -o sorting_algorithms
./sorting_algorithms

Como funcionam os algoritmos de ordenação?

Insertion Sort

  1. Pega o item e compara com o da esquerda.
  2. Se o item é menor que o da esquerda, trocam de lugar.
  3. Continua trocando até atingir um item menor que o item atual.
  4. Repete até atingir o último elemento da direita.
  • É muito eficiente para arrays parcialmente classificados, ou minúsculos (menos de 20 elementos);

Selection Sort

  1. Encontra o menor número do array.
  2. Coloca ele no primeiro índice.
  3. Encontra o próximo menor elemento e coloca no próximo índice.
  4. Repete até a lista estar toda ordenada.
  • Cada troca coloca um item em sua posição final, de modo que o número de trocas é N. Assim, o tempo de execução é denominado pelo número de comparações.
  • A desvantagem em relação ao Insertion Sort é que enquanto o Insertion verifica apenas os elementos necessários para colocar o k + 1º elemento, o Selection verifica todos os elementos restantes para encontrar o k + 1º elemento.

Bubble Sort

  1. Se o elemento da esquerda for maior que o da direita, trocam de lugar
  2. Repete até o fim do array.
  3. Retorna pra o início e repete até o último elemento já ordenado.
  4. Repete esse processo até todo o array estar ordenado.
  • É muito lento, faz muitas comparações e leva muito tempo, porém é um algoritmo bastante fácil de entender. Pode ser útil se você não se preocupar com quanto tempo um algoritmo levará ou se você tiver um conjunto muito pequeno de dados para classificar.

Heap Sort

  1. Quando a raiz do node é o maior elemento, faz um buildMaxHeap
  2. Troca a raiz do node com o elemento do último index
  3. Remove o elemento e diminui o tamanho do heap em 1
  4. Faz heapify, para que pegue novamente o maior elemento da raiz
  5. Repete até que todos os elementos estejam ordenados

Heapify é o processo de criar uma estrutura de dados heap a partir de uma árvore binária

  1. Seleciona o array inserido
  2. Transforma o array em uma árvore binária
  3. Cria um heap a partir da árvore binária
  • Quando o espaço é muito apertado, é ótimo, porque pode ser implementado com poucas linhas, enquanto ainda tem um desempenho ideal, porém tem baixo desempenho de cache.
  • Similar ao Selection Sort, mas enquanto o Selection tem performance em tempo quadrático, o Heap funciona em tempo logarítmico, pois árvores binárias são logarítmicas por natureza.

Merge Sort

  1. Divide a lista consecutivamente;
  2. Une as listas, ordenando-as na ordem correta;
  • Tende a ser muito mais fácil classificar duas listas menores e classificadas do que classificar uma única lista grande e não classificada.
  • A complexidade de tempo do Merge Sort é uma combinação de tempos lineares e logarítmicos; isso é referido como tempo linearítmico;
  • Como o Merge Sort é implementado como um algoritmo de classificação externo, ele pode fazer o trabalho de classificação fora da memória principal e, posteriormente, pode puxar os dados classificados de volta para a memória principal interna.

Quick Sort

  1. Define qual elemento será o pivô
  2. Divide a lista em 2, os menores e os maiores que o pivô
  3. Coloca os elementos menores a esquerda e os maiores na direita
  4. Escolhe um novo pivô e repete até a lista estar ordenada
  • O Quick Sort permite uma ordenação "in-place", ou seja, poupa muita memória durante sua execução. Esse é um dos principais motivos dele ser um dos algoritmos mais utilizados.
  • Não é um bom algoritmo para arrays quase ou completamente classificados.
  • É um algoritmo instável, o que significa que não é garantido que ele preservará a ordem dos elementos conforme ele reordena; dois elementos que são exatamente iguais no array não classificado podem aparecer em ordem reversa no classificado. A estabilidade acaba sendo o principal fator que faz com que as pessoas escolham o Merge Sort.

Comparação entre os algoritmos

Casos de teste

Testes Gráfico

Complexidade

Complexidade

algoritmos-ordenacao's People

Contributors

anabxms avatar

Watchers

 avatar

Forkers

sscastilho

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.