Visitante!
Faça seu Login ou Registre-se!

Galeria de Jogos

[Ruby] Algoritmo #1 - otrS => Sort 5 Respostas | 1018 Visualizações

0 Membros e 1 Visitante estão vendo este tópico.

Raizen

  • *
  • Mensagens: 2462 Ouro: 1820

    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
[Ruby] Algoritmo #1 - otrS => Sort
Online: 27 Fev 2014, 16:09
Índice das aulas básicas
Índice das aulas avançadas
Índice das aulas de algoritmos
Algoritmo de Sort
Conhecimento necessário : médio
Introdução

Olá jovens, bem-vindo a minha seção de aulas sobre algoritmos :)

Antes de tudo devo dizer que as aulas aqui não serão tão triviais para quem não teve nada de programação ou qualquer coisa sobre Ruby, por isso aconselho olhar as aulas anteriores sobre o básico de Ruby e programação.
Essa é a primeira aula de algoritmos, então vou dar uma breve definição do que é um algoritmo. O algoritmo é uma sequência finita de instruções que resultam em um objetivo, seja o algoritmo apenas parte de um sistema, ou ele inteiro. Os algoritmos são reutilizados, e por isso nessas aulas vou explicar os algoritmos mais famosos que tem, ou seja, código utilizado e reutilizado como Pathfinding, de busca ou como no que está nessa aula, de ordenação.


Os algoritmos em geral utilizam arrays, se olharam a minha aula de Arrays, devem ter reparado que já tem a função sort. Basicamente se eu fizer isso,

array = [1, 3, 6, 2, 7, 1]
array.sort!
array == [1, 1, 2, 3, 6, 7] # esse será o resultado do sort.

Mas obviamente, esse sort não apareceu do nada, ele foi programado por alguém, e nela contém um dos melhores se não o melhor algoritmo de ordenação, mas será que você conseguiria reproduzir o mesmo algoritmo de ordenação?
Antes de continuar, recomendo que tente algumas vezes a fazer, e depois veja abaixo os modos mais conhecidos de ordenação.

Bubble Sort

Bubble sort é a ordenação mais lógica, aquela que provavelmente seja a sua primeira solução para o problema, ela nada mais é do que o seguinte.



Veja ele fica verificando o próximo campo com o anterior e troca ambos de posição caso o maior seja o primeiro.

Como isso ficaria no código, colocando dentro de uma Array.

Código: [Selecionar]
class Array
  def bubblesort
    contador = 0
    for i in 1...self.size
      for n in 0...self.size - 1
        if self[i] < self[n]
          oldn = self[n]
          self[n] = self[i]
          self[i] = oldn
        end
        contador += 1
      end
    end
    p contador
    return self
  end
end

O contador dentro do código serve para simplesmente contar o número de contas para que possamos comparar com os outros modos de ordenação.
se utilizar esse código junto com o script acima,
Código: [Selecionar]
p [1, 4, 7, 0, 104, 10, 2, 1, 5, 3].bubblesortVocês terá o resultado esperado, que é de ordenar a array(vetor), e o número de cálculos utilizaados verá que foi de 81, resumindo o número de loops necessários para o bubble sort é na ordem de (n-1)², considerando que há 10 números dentro da array, logo (10-1)² = 81.
Se pesquisarem na internet o dito cujo é n², pois isso na verdade está errado, a ordem de loops máximos é de (n-1)², porém para números grandes como 100 registros na array, verá que o crescimento dos calculos é tão imenso que já faz o bubble search não ser utilizável para condições normais de programação e por essa razão é simplificado como n².

Merge Sort

O merge sort é um método mais avançado que o bubble sort, veja abaixo como ele se comporta na ordenação da array.

Abaixo o código do merge sort.

Código: [Selecionar]
class Array
  def merge_sort
    mergesort(self)
  end
  def mergesort(list)
    return list if list.size <= 1
    mid = list.size / 2
    left  = list[0, mid]
    right = list[mid, list.size-mid] 
    merge(mergesort(left), mergesort(right))
  end
 
  def merge(left, right)
   sorted = []
 
   until left.empty? or right.empty?
     if left.first <= right.first
       sorted << left.shift
     else
        sorted << right.shift   
      end
   end
   sorted.concat(left).concat(right)
  end
end

O código acima não é meu :), apenas usando para explicar como funciona o merge sort. Ele constantemente divide a array em 2, e então recria essa array verificando se o primeiro valor da nova array é menor ou maior.
Isso sai do mesmo principio que o bubblesort, porém dividindo a array em 2 constantemente, sabemos que as novas arrays já estão na ordem, e portanto o número de contas para concatenar a array é visivelmente menor que a bubble sort, o número de loops para esse arranjo é na ordem de (n log2 n), como podem perceber com arrays maiores o número se torna muitas vezes menor que com o bubble sort, porém como contra tem um número muito grande de novas arrays criadas para esse tipo de arranjo.

Quick Sort

O quick sort é um método muito rápido e eficiente de ordenação da array, inclusive ele é o utilizado pela classe padrão da array do Ruby.
O código nativo da array é a seguinte.
Código: [Selecionar]
class Array
def sort(array = self)
        return array if array.size <= 1
        pivot = array[0]
        return sort(array.select { |y| y < pivot }) +
            array.select { |y| y == pivot } +
            sort(array.select { |y| y > pivot })
    end
end
ele na verdade usa 2 métodos então dei uma simplificada no método acima para explicar. a ideia do quicksort é pegar um valor qualquer, e por segurança é utilizado sempre o primeiro da array já que ele sempre existirá e feito o seguinte.

em um vetor [1, 3, 2, 5, 4, 6, 8, 7] os seguintes passos acontecem.
1 é utilizado como pivo, e tudo que é maior que ele vai pro lado direito, e tudo que é menor pro esquerdo.
no caso todos pro lado direito e retiro o 1 da array,
a array ficará como [3, 2, 5, 4, 6, 8, 7]

O 2 vai para o lado esquerdo e os demais para o direito, e assim em diante.... até terminar a array, apesar de ter um um número máximo de loops semelhantes ao bubblesort (n-1)² o número médio de passos é altamente reduzido, resumindo, é o mais rápido em média da maioria das ordenações, mas pode ter também um tempo muito grande imposto para fazer a ordenação.

Finalizando

Finalizando:
A ideia das aulas é mostrar um pouco dos algoritmos e das lógicas que o programa usa e que você pode usar, métodos de ordenação existem vários, e por isso para quem quiser, tente inventar um modo novo de ordenação e coloque um contador para ver o quão eficiente o seu método está.
« Última modificação: 16 Dez 2015, 10:30 por Raizen »

Shiroyasha

  • *
  • Mensagens: 270 Ouro: 328

    Participantes do Maps Together 2

  • Tomando gank no combate eventer. Mds. )o)
    • RPG Maker VX/Ace
    • Ver perfil
Re: Algoritmo #1 - otrS => Sort
Resposta 1 Online: 27 Fev 2014, 17:28
Ah, aí está.
Muito importante essa aula Raizen, mas esse Bubble Sort teu é bugado... aushaushuas
A complexidade do Bubble Sort é, de fato, n² para o melhor (vetor já ordenado) e pior caso (vetor invertido).
Se você testar o seu método de bubble sort com um vetor de valores já ordenado de forma invertida perceberá que ele não o ordenará por completo.

Eu percebi que você usou o self.size - 1 para evitar que n+1 acessasse uma memória fora do array.
Só que ao fazer isso você não executa o algoritmo n² vezes.
Desconfio que o mais correto seria:

Código: [Selecionar]
class Array
  def bubblesort
    contador = 0
    for i in 0...self.size
      for n in 0...self.size
        if self[i] < self[n]
          oldn = self[n]
          self[n] = self[i]
          self[i] = oldn
        end
        contador += 1
      end
    end
    p contador
    return self
  end
end

Até.

Raizen

  • *
  • Mensagens: 2462 Ouro: 1820

    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
Re:  Algoritmo #1 - otrS => Sort
Resposta 2 Online: 27 Fev 2014, 17:37
Ah, aí está.
Muito importante essa aula Raizen, mas esse Bubble Sort teu é bugado... aushaushuas
A complexidade do Bubble Sort é, de fato, n² para o melhor (vetor já ordenado) e pior caso (vetor invertido).
Se você testar o seu método de bubble sort com um vetor de valores já ordenado de forma invertida perceberá que ele não o ordenará por completo.

Eu percebi que você usou o self.size - 1 para evitar que n+1 acessasse uma memória fora do array.
Só que ao fazer isso você não executa o algoritmo n² vezes.
Desconfio que o mais correto seria:

Código: [Selecionar]
class Array
  def bubblesort
    contador = 0
    for i in 0...self.size
      for n in 0...self.size
        if self[i] < self[n]
          oldn = self[n]
          self[n] = self[i]
          self[i] = oldn
        end
        contador += 1
      end
    end
    p contador
    return self
  end
end

Até.
Ah eu fiz algo errado deverás  :-.-:

Mas não sou louco quando digo que é (n -1)² ao invés de n² ele realmente é (n-1)² que pode ser provado com isso daqui :X
[2, 1] tem 1 mudança de posição para ficar em ordem (2-1)²
[3, 2, 1] tem 4 mudanças ([2,3,1], [2, 1, 3], [1, 2, 3] e caso tivesse um ultimo [1, 3, 2]) (n-1)² (3-1)² = 4

Então eu fiz algo errado no meu algoritmo >__<, mas o bubblesort no modo mais optimizado é nessa ordem, por exemplo.
esse código corrige :X,
Código: [Selecionar]
class Array
  def bubblesort
    contador = 0
    for i in 0...self.size
      for n in 0...self.size - 1
        if self[i] < self[n]
          oldn = self[n]
          self[n] = self[i]
          self[i] = oldn
        end
        contador += 1
      end
    end
    p contador
    return self
  end
end

Vou tentar ver, deve ter algo nos índices, vlws ai manolo :D

Edit: Ahhh achei, então o modo mais optimizado eh esse abaixo, vou mudar no tópico principal :P
ele tem (n-1)² no pior e no melhor caso xD

Código: [Selecionar]
class Array
  def bubblesort
    contador = 0
    for i in 1...self.size
      for n in 0...self.size - 1
        if self[i] < self[n]
          oldn = self[n]
          self[n] = self[i]
          self[i] = oldn
        end
        contador += 1
      end
    end
    p contador
    return self
  end
end
« Última modificação: 27 Fev 2014, 17:40 por Raizen »

Kvothe

  • *
  • Mensagens: 614 Ouro: 1236
  • Maker Geral
    • Unity
    • Facebook
    • DeviantArt
    • Ver perfil
    • E-mail
Re: Algoritmo #1 - otrS => Sort
Resposta 3 Online: 27 Fev 2014, 20:43
 Eita gostei da aula brother. Espero ver mais do tipo, pretende aprofundar mais em aulas com a classe Array?
"Amamos aquilo que amamos. A razão não entra nisso. Sob muitos aspectos, o amor insensato é o mais verdadeiro. Qualquer um pode amar uma coisa por causa de. É tão fácil quanto por um vintém no bolso. Mas amar algo apesar de, conhecer suas falhas e amá-las também, isto é raro, puro e perfeito". (O Temor do Sábio, pág. 58)

Raizen

  • *
  • Mensagens: 2462 Ouro: 1820

    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
Re:  Algoritmo #1 - otrS => Sort
Resposta 4 Online: 27 Fev 2014, 21:02
Eita gostei da aula brother. Espero ver mais do tipo, pretende aprofundar mais em aulas com a classe Array?
Sim sim, apesar que eu peguei a classe Array para explicar alguns algoritmos, a próxima é do search, que na classe Array é include? :D

Mas a ideia não é bem explicar a classe, e sim dar algo que dão no curso superior de computação, que são os algoritmos e as lógicas e talz :D

Kvothe

  • *
  • Mensagens: 614 Ouro: 1236
  • Maker Geral
    • Unity
    • Facebook
    • DeviantArt
    • Ver perfil
    • E-mail
Re: Algoritmo #1 - otrS => Sort
Resposta 5 Online: 27 Fev 2014, 22:02
 Legal o que 'cê tá fazendo. Passando o que está aprendendo. Bom boa sorte aí.
"Amamos aquilo que amamos. A razão não entra nisso. Sob muitos aspectos, o amor insensato é o mais verdadeiro. Qualquer um pode amar uma coisa por causa de. É tão fácil quanto por um vintém no bolso. Mas amar algo apesar de, conhecer suas falhas e amá-las também, isto é raro, puro e perfeito". (O Temor do Sábio, pág. 58)

 

Versão Mobile