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 |
