[Ruby] Algoritmo #1 - otrS => Sort

[Raizen]

[box class=windowbg1]

Índice das aulas básicas

• Aula 1 - Introdução
  
• Aula 2 - Objetos
  
• Aula 3 - Operações
  
• Aula 4 - Condições
  
• Aula 5 - Repetição
  
• Aula 6 - Arrays
  
• Aula 7 - Hashes
  [/box]
  [box class=windowbg1]
  Índice das aulas avançadas
• Aula 8 - Superclasses e instâncias
  [/box]
  [box class=windowbg1]
  Índice das aulas de algoritmos
• Aula 1 - Sort
  
• Aula 2 - Busca
  
• Aula 3 - Recursividade
  [/box]
  
  [box class=windowbg]
  Algoritmo de Sort
  [/box]
  
  Conhecimento necessário : médio
  [box class=windowbg]
  Introdução
  [/box]
  [box class=windowbg2]
  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.
  [/box]
  
  [box class=windowbg]
  Bubble Sort
  [/box]
  
  [box class=windowbg2]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.
  
  

  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,
  

  p [1, 4, 7, 0, 104, 10, 2, 1, 5, 3].bubblesort
  

  
  Você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².
  [/box]
  
  [box class=windowbg]
  Merge Sort
  [/box]
  
  [box class=windowbg2]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.
  
  

  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.
  [/box]
  
  [box class=windowbg]
  Quick Sort
  [/box]
  
  [box class=windowbg2]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.
  

  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.
  [/box]
  
  [box class=windowbg]
  Finalizando
  [/box]
  
  [box class=windowbg2]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á.
  [/box]

[Shiroyasha]

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:

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]

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:

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,

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

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

[Kvothe]

 Eita gostei da aula brother. Espero ver mais do tipo, pretende aprofundar mais em aulas com a classe Array?

[Raizen]

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]

 Legal o que 'cê tá fazendo. Passando o que está aprendendo. Bom boa sorte aí.