Stabilität (Sortierverfahren)

Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.

Wenn bspw. eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert wird, dann bleiben unter einem stabilen Sortierverfahren alle Personen mit gleichem Geburtsdatum alphabetisch sortiert.

Will man mit einem instabilen Sortierverfahren, etwa Quicksort, sortieren und dabei die Reihenfolge der Datensätze mit gleichem Schlüssel beibehalten, so kann man sich damit behelfen, dass man die Datensätze um eine Reihenfolgenummer erweitert und diesem Feld den niedrigsten Rang im Sortierschlüssel gibt. Weniger aufwändig ist es aber, ein stabiles Sortierverfahren zu benutzen.

Stabile und instabile Sortierverfahren verhalten sich gleich, wenn die Multimenge der Schlüssel in der Eingabe eine Menge ist, es also keine Duplikate unter den Schlüsseln gibt; ebenso, wenn Datensätze mit gleichem Schlüssel in keiner Weise unterscheidbar sind – beispielsweise, weil der Schlüssel den ganzen Datensatz umfasst. Eine Multimenge von Zahlen oder Namen etwa kann man mit einem stabilen oder instabilen Sortierverfahren sortieren, das Ergebnis ist immer gleich:

Stabiles oder instabiles Sortierverfahren:

  4       1
  3       2
  5       3
  3   →   3
  2       3
  1       4
  3       5

Stabiles oder instabiles Sortierverfahren (alphabetisch):

  Carla        Annette
  Annette  →   Birgit
  Birgit       Carla

Kombiniert man jedoch etwa Namen und Zahlen zu je einem Datensatz und sortiert nur nach einem Teilschlüssel, etwa nach Zahlen, dann existieren bei gleichen Schlüsseln verschiedene Möglichkeiten für die Reihenfolge. Ein stabiles Verfahren wählt diejenige Reihenfolge, die bei gleichen Schlüsseln die Originalreihenfolge der Namen beibehält, etwa

Stabiles Sortierverfahren nach Zahlen:

  1 Anton       1 Anton       
  4 Karl        1 Paul
  3 Otto        3 Otto
  5 Bernd   →   3 Herbert
  3 Herbert     4 Karl
  8 Alfred      5 Bernd
  1 Paul        8 Alfred

Instabiles Sortierverfahren nach Zahlen:

  1 Anton        1 Paul         1 Anton        1 Paul         1 Anton
  4 Karl         1 Anton        1 Paul         1 Anton        1 Paul
  3 Otto         3 Otto         3 Herbert      3 Herbert      3 Otto
  5 Bernd   →    3 Herbert oder 3 Otto    oder 3 Otto    oder 3 Herbert
  3 Herbert      4 Karl         4 Karl         4 Karl         4 Karl
  8 Alfred       5 Bernd        5 Bernd        5 Bernd        5 Bernd
  1 Paul         8 Alfred       8 Alfred       8 Alfred       8 Alfred

Bei instabiler Sortierung kann Paul vor Anton oder Herbert vor Otto stehen.

Sortieralgorithmen

Quicksort

Der Quicksort-Algortithmus ist eines der schnellsten und zugleich einfachsten Sortierverfahren. Es arbeitet nach dem Divide-and-Conquer-Prinzip.
Es wird zunächst ein Pivotelement ausgewählt und die Liste in zwei geteilt. Die Elemente, die kleiner als das Pivotelement sind, kommen in die erste Liste und die anderen in die zweite. Mit den entstehenden Listen wird genauso fortgefahren, bis es nur noch Teillisten der Länge 1 gibt. Diese Listen werden nun der Reihe nach wieder zusammengefügt.

Mergesort

Ähnlich wie bei Quicksort beruht das Verfahren auf der Divide-and-Conquer-Strategie. Die zu sortierende Folge wird in zwei gleichgroße Hälften geteilt. Die entstehenden Listen werden weiter und weiter geteilt, bis es wieder nur noch Teillisten der Länge 1 gibt. Zusammengefügt wird, indem die ersten beiden Elemente zweier Teillisten verglichen werden, das kleinere gelöscht und in eine neue Liste eingetragen wird. Die neuen ersten beiden Elemente verglichen, das kleinere gelöscht und in die neue Liste eingetragen wird…

Bubblesort

Bubblesort ist einer der simpelsten Sortieralgorithmen.
Im ersten Durchlauf wird nach dem kleinsten Element gesucht, im zweiten Durchlauf nach dem zweitkleinsten usw.
Man geht den Array immer von hinten nach vorne durch. Zunächst vergleicht man das letzte mit dem vorletzten Element. Ist das hintere kleiner, werden die beiden Elemente vertauscht. Dann wird mit dem vorletzten und dem vorvorletzten weitergemacht. Dadurch bleiben die größeren liegen und die kleineren Elemente werden nach vorne durchgereicht.

Insertionsort

Man hat eine zu sortierende Folge a0, a1, … , an-1, wobei der erste Teil a0, a1, … , ak-1 bereits aufsteigend sortiert ist und der zweite Teil ak, ak+1, … , an-1 noch unsortiert ist. Zu Anfang besteht der sortierte Teil nur aus a0, zum Schluss aus allen Elementen a0, a1, … , an-1.
Das Element ak wird als nächstes in die bereits sortierte Liste eingefügt, indem es der Reihe nach mit ak-1, ak-2 usw. verglichen wird. Sobald ein Element aj mit aj≤ak gefunden wird, wird es hinter dieses eingefügt. Wird kein solches Element gefunden, wird ak an den Anfang der Folge gesetzt.
Damit ist der sortierte Teil um ein Element länger geworden. Im nächsten Schritt wird ak+1 in den sortierten Teil eingefügt…

Vergleich Mergesort und Quicksort

von http://www.gm.fh-koeln.de/~ehses/ap/folien/folien9.pdf

  • Mergesort ist garantiert O(n log n), Quicksort im Mittel
  • Die Anzahl der Vergleich und der Datenbewegungen ist bei Mergesort n log2(n)
  • Quicksort hat im Mittel O(1.4 n log2 n) Vergleiche
  • Quicksort hat im Mittel O(0.7 n log2 n) Datenbewegungen
  • Quicksort ist schneller, wenn die Vergleiche schneller sind als die Datenbewegungen (einfache Datentypen)
  • Mergesort ist schneller, wenn die Vergleiche die Zeit dominieren (Objekte)
  • Es gibt Varianten von Mergesort für Felder und Listen (nicht rekursiv)

Links

zu Laufzeiten s.a.: O-Notation
www.sortieralgorithmen.de – mit klasse Applet
Merkblatt zu topologisches Sortieren von Augustin

Kaynak: http://www.tilman.de/uni/ws03/alp/sortieralgorithmen.php

 

Zaman buldugumda Türkce cevirisini yapacagim!

P ve NP Karmasikligi

P-NP Problemi

P-NP Problemi (P versus NP olarak da gecer) Matematik ve Bilgisayar Bilimlerinde halen cözülemeyen bir Problemdir. Özellikle Karmasiklik Teorisinde.

Asil merak edilen sey ise P ve NP arasinda ki karsilikli iliskinin ne oldugudur aslinda. 1970li yillarda birbirinden bagimsiz calisan Stephan Cook ve Leonid Levin tarafindan ilk defa üzerine gidilmistir.

P-NP Problemi Bilgisayar Biliminde Clay Mathematics Institute tarafindan Millenium Problemlerinden biri olan ve halen cözülemeyen bir Sorudur.

P ve NP

Karmasiklik Teorisi sorunu ortaya koymakla beraber Bilgisyarlar tarafindan da hesaplanabilindigini ….

https://de.wikipedia.org/wiki/P-NP-Problem#P_und_NP

P

P, Karmasiklik Teorisinde Problem kategorilerinde Karmasiklik Sinifidir.

Bu Sinifin icindeki her Problem icin bir deterministik Turing Makinesi mevcuttur. (Bir Algoritma ile yada Programlama ile bu Problemi cözen ve bir n^k seklinde bir Polinom (k bir sabittir)) ile Zaman Karmasikligi ile cözen ve Durumu n uzunlugunda sinirlandirir.

P sinifinda ki Problemler böylelikle deterministik ve Polinomial zamanda cözülebilirler.

Örnek olarak vermek gerekirse: Siralama Problemleri ve Devre Analiz Problemleri.

NP

Karmasilik Teorisi deterministik Turing Makinesinden baska Makinelerle de tanimlanmaktadir.
Ein önemlilerinden biri deterministik olmayan Turing Makineleridir, deterministik olanlarin gelistirilmis hali gibi.

Deterministik olmayan Turing Makineleri her Zaman diliminde potansiyel olarak daha cok Özellige sahiptir.
Hesaplamalari , Islem adimlari tam olarak takip edilemezdirler.

Bu yüzden teorik bir Modell olarak kabul edilir. Suan ki Bilgisayarlarda kullanilmamaktadir.

NP Karmasiklik Sinifi tam olarak deterministik olmayan Turingmakinalarini Polinomiel Zamanda cözülebilen Problemleri kapsar.

P Sinifinda ki Problemler deterministik olamayan Polinomial Zamanda da cözülebildiklerinden, P ayni zamanda NP sinifinin bir Altkümesidir.

P_NP_Karmasiklik

 

Ruby on Rails ile Blog Uygulamasi Gelistirme

Bu Yazmiz da hemen bir Blog Uygulamasinin nasil kurulacagini anlatacagim.

$ rails new blog

Ile hemen Rails Kütüphanesinden yeni bir Blog olusturmak istedigimizi terminale aktariyoruz.

jquery-rails yükle degilse onu da

gem install jquery-rails

diyerek yükleyelim.

cd blog

diyerek Blog klasörümüze giriyoruz.

 

Ruby on Rails Ders 1

#1 Ruby Versiyonunu sorgulama kodu:

basbayandur:~ $ ruby -v 
ruby 1.9.3p484 (2013-11-22 revision 43786) [x86_64-linux]

#2 sqlite3 in yüklü olup olmadigini, degilse yükleme kodu:

basbayandur: ~ $ sqlite3 --version
basbayandur: ~ $ sudo apt-get install sqlite3

#3 $ sqlite3 –version komutu ile tekrar versiyon sorgulamasi yapiyoruz.

basbayandur: ~ $ sqlite3 --version  
3.8.2 2013-12-06 14:53:30 27392118af4c38c5203a04b8013e1afdb1cebd0d

#4 Sistemimizde Ruby hali hazirda yüklü, lakin Rails Kütüphanesini de eklememiz gerekiyor. (Kütüphane dedim, dogru terim mi bendebilmiyorum)

basbayandur: ~ $ gem install rails

Bu islemi koding.com da uygulamk icin de root haklarina sahip olmaniz gerekiyor. bunun icin sudo -i yazarak yeni bir root sifresi olusturabilirsiniz.

root: /home/basbayandur $ gem install rails
Fetching: i18n-0.7.0.gem (100%)
Fetching: json-1.8.3.gem (100%)
Building native extensions.  This could take a while...
ERROR:  Error installing rails:
        ERROR: Failed to build gem native extension.
 
        /usr/bin/ruby1.9.1 extconf.rb
creating Makefile
 
make
sh: 1: make: not found
 
 
Gem files will remain installed in /var/lib/gems/1.9.1/gems/json-1.8.3 for inspection.
Results logged to /var/lib/gems/1.9.1/gems/json-1.8.3/ext/json/ext/generator/gem_make.out
root: /home/basbayandur $

#5 rails in versiyonunu test edelim

$ rails --version

hata verdi, yukarda ki islem dogru tamamlanmadigindan root olarak giris yaptigimiz icin tekrar asagida ki kodu yazip yükleme islemini tamamliyoruz.

$ gem install rails

#6 Tekrar Rails Versiyonu Kontrol edelim.

root: /home/basbayandur $ rails --version                                                                                                                                                                             
Rails 3.2.16

 

Bu yazimiz da Ruby on Rails icin gerekli Yazilimlari koding de bulunan sanal sunucumuza yüklemis olduk.

Bir sonra ki yazimizda da Ruby on Rails ile gelen hazir script lerden olan bir Blog kuracagiz.