Die Programmiersprache Ruby

Blog| Forum| Wiki  

Inhaltsverzeichnis


Sortierung

Ganz einfaches Sortierverfahren: Jeweils den niedrigsten Wert heraussuchen und an ein neues Array anhängen:

1
2
3
4
5
6
7
8
9
10
def slow_sort(array)
  a = array.clone      # damit wir das urspr��ngliche Array nicht kaputt machen
  rueckgabe_array = [] # hier kommen die sortierten werte rein
  until a.empty?
    min = a.first
    a.each { |element| min = element if element < min }
    rueckgabe_array.push a.delete(min)
  end
  return rueckgabe_array
end


Schon etwas besser: Alle Werte mit dem jeweils nächsten vergleichen und ggf. vertauschen bis alles sortiert ist:

1
2
3
4
5
6
7
8
9
10
11
def bubble_sort(a)
  vertauscht = false
  anzahl_durchlaeufe = a.length - 1
  anzahl_durchlaeufe.times do |i|
    unless a[i] <= a[i + 1]           # wenn der wert nicht richtig sortiert
      a[i], a[i + 1] = a[i + 1], a[i] # vertauschen
      vertauscht = true
    end
  end
  vertauscht ? bubble_sort(a) : a
end


Für die meisten Fälle das beste: Teile das Array in zwei Arrays, die jeweils die Werte kleiner und größer als den ersten Wert enthalten:

1
2
3
4
5
6
7
def quick_sort(array)
  return [] if array.empty?
  a = array.clone
  pivot = a.shift
  left, right = a.partition{ |wert| wert < pivot }
  return quick_sort(left).push( pivot ).push(*quick_sort(right))
end


Die in-situ Variante ist etwas komplizierter, verbraucht aber keinen zusätzlichen Speicherplatz:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quick_sort!(array, range=nil)
  range ||= 0..(array.size - 1)
  left, right = range.first, range.last
  return if left >= right
  pivot = array[left]
  i = right
  right.downto(left+1) do |j|
    if array[j] > pivot
      array[i], array[j] = array[j], array[i]
      i -= 1
    end
  end
  array[i], array[left] = array[left], array[i]
  quick_sort!(array, left..(i-1))
  quick_sort!(array, (i+1)..right)
end


Fibonacci / Rekursion

Triviale Implementierung:

1
2
3
4
def fib(n)
  return n if n < 2
  return fib(n- 1) + fib(n - 2)
end


Schnellere Implementierung:

1
2
3
4
5
6
7
def fib(n, n_1 = nil, n_2 = nil)
  return n if n < 2
  n_1 ||= 0
  n_2 ||= 1
  return n_1 + n_2 if n == 2
  return fib(n - 1, n_2, n_1 + n_2)
end


Über dynamische Programmierung:

1
2
3
4
5
6
7
def fib(n)
  fibonacci = [0, 1]
  2.upto(n) do |zahl|
    fibonacci[zahl] = fibonacci[zahl-1] + fibonacci[zahl-2]
  end
  return fibonacci[n]
end


Primzahlen (Sieb des Eratosthenes)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def prim_array (maxwert)
  @maxwert = maxwert
  idx = 0
  @prim_array = []
    (1..@maxwert).each { |i| 
      prim = true
      (2..i/2).each { |j|
        if i % j == 0
          prim = false
          break
         end
       } 
       @prim_array.push(i) if prim
     }
  return @prim_array
end

# Ermittle Primzahlen bis zu einem ��bergebenen Maxwert
prim_array(112)
p @prim_array