{"id":75,"date":"2020-10-02T12:31:24","date_gmt":"2020-10-02T10:31:24","guid":{"rendered":"http:\/\/aud.ibr.cs.tu-bs.de\/?page_id=75"},"modified":"2021-02-11T08:54:39","modified_gmt":"2021-02-11T07:54:39","slug":"kapitel-5-sortieren","status":"publish","type":"page","link":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/kapitel\/kapitel-5-sortieren\/","title":{"rendered":"Kapitel 5 &#8211; Sortieren"},"content":{"rendered":"\n<p>Sortieren ist ein grundlegendes algorithmische Problem, das f\u00fcr viele komplexere Aufgaben ben\u00f6tigt wird. Zugleich bieten die zugeh\u00f6rigen Methoden und Prinzipien einen Einstieg in zahlreiche weiterf\u00fchrende Themen.<\/p>\n\n\n\n<p><strong>Termine:<\/strong><\/p>\n\n\n\n<ul><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/13\/vorlesung-17\/\">Vorlesung 17<\/a> am 13.01.21 (11:30 Uhr): Aufgabenstellung, Mergesort<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/19\/vorlesung-18\/\">Vorlesung 18<\/a> am 19.01.21 (09:45 Uhr): Behandeln von Rekursionen<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/20\/vorlesung-19\/\">Vorlesung 19<\/a> am 20.01.21 (11:30 Uhr): Erzeugende Funktionen, Master-Theorem<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/22\/uebung-6\/\">\u00dcbung 6<\/a> am 21.01.21 (11:30 Uhr): Mergesort, Master-Theorem, andere Sortierverfahren<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/26\/vorlesung-20\/\">Vorlesung 20<\/a> am 26.01.21 (09:45 Uhr): Nichtlineare Rekursionen<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/27\/vorlesung-21\/\">Vorlesung 21<\/a> am 27.01.21 (11:30 Uhr): Quicksort<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/02\/vorlesung-22\/\">Vorlesung 22<\/a> am 02.02.21 (09:45 Uhr): Mediane<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/03\/vorlesung-23\/\">Vorlesung 23<\/a> am 03.02.21 (11:30 Uhr): Sortieren in linearer Zeit<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/04\/uebung-7\/\">\u00dcbung 7<\/a> am 04.02.21 (11:30 Uhr): Quicksort, Mediane<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/09\/vorlesung-24\/\">Vorlesung 24<\/a> am 09.02.21 (09:45 Uhr): Paralleles Sortieren<\/li><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/10\/vorlesung-25\/\">Vorlesung 25<\/a> am 10.02.21 (11:30 Uhr): Zusammenfassung<\/li><li>\u00dcbung 8 am 11.02.21 (11:30 Uhr): Fragestunde, Quiz<br>Stream:\u00a0<a href=\"https:\/\/youtu.be\/0GW30mYR8Cg\">[YouTube]<\/a>, Chat:\u00a0<a href=\"https:\/\/discord.gg\/tZdcmEy\">[Discord]<\/a><\/li><\/ul>\n\n\n\n<h2>Vorlesungen<\/h2>\n\n\n<ul class=\"wp-block-latest-posts__list has-dates wp-block-latest-posts\"><li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/12\/uebung-8\/\">\u00dcbung 8<\/a><time datetime=\"2021-02-12T10:07:15+01:00\" class=\"wp-block-latest-posts__post-date\">12. Februar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">Die letzte gro\u00dfe \u00dcbung von AuD mit Spiel, Spa\u00df, Spannung und vielen Fragen.<\/div><\/li>\n<li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/10\/vorlesung-25\/\">Vorlesung 25<\/a><time datetime=\"2021-02-10T13:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">10. Februar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">Diese Vorlesung markiert das Ende der Vorlesungszeit. Es werden noch einmal einige Hinweise zur Klausur und Klausurvorbereitung gegeben. Zudem gab es noch einmal die M\u00f6glichkeit Fragen zu stellen.<\/div><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image\"><img width=\"300\" height=\"212\" src=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/bogo-sort-300x212.png\" class=\"attachment-medium size-medium wp-post-image\" alt=\"\" loading=\"lazy\" style=\"max-width:400px;\" srcset=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/bogo-sort-300x212.png 300w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/bogo-sort-1024x724.png 1024w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/bogo-sort-768x543.png 768w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/bogo-sort-1536x1086.png 1536w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/bogo-sort-816x577.png 816w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/bogo-sort.png 2000w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/09\/vorlesung-24\/\">Vorlesung 24<\/a><time datetime=\"2021-02-09T11:30:00+01:00\" class=\"wp-block-latest-posts__post-date\">9. Februar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser Vorlesung beenden wir das Kapitel zum Thema Sortieralgorithmen und werfen abschlie\u00dfend einen Blick auf parallelisierte Sortierverfahren. <\/div><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image\"><img width=\"300\" height=\"163\" src=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/02\/U7-1-300x163.jpg\" class=\"attachment-medium size-medium wp-post-image\" alt=\"\" loading=\"lazy\" style=\"max-width:400px;\" srcset=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/02\/U7-1-300x163.jpg 300w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/02\/U7-1-1024x555.jpg 1024w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/02\/U7-1-768x416.jpg 768w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/02\/U7-1-1536x833.jpg 1536w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/02\/U7-1-816x442.jpg 816w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/02\/U7-1.jpg 1920w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/04\/uebung-7\/\">\u00dcbung 7<\/a><time datetime=\"2021-02-04T15:20:48+01:00\" class=\"wp-block-latest-posts__post-date\">4. Februar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser \u00dcbung schauen wir uns noch einmal das Sortierverfahren Quicksort an und sprechen \u00fcber die Berechnung von Medianen. Au\u00dferdem schauen wir uns mit den kd-B\u00e4umen eine spezielle Datenstruktur f\u00fcr mehrdimensionale Daten an.<\/div><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image\"><img width=\"300\" height=\"240\" src=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/SEACComputer_038-300x240.jpg\" class=\"attachment-medium size-medium wp-post-image\" alt=\"\" loading=\"lazy\" style=\"max-width:400px;\" srcset=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/SEACComputer_038-300x240.jpg 300w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/SEACComputer_038-768x615.jpg 768w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/SEACComputer_038-816x653.jpg 816w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/SEACComputer_038.jpg 1024w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/03\/vorlesung-23\/\">Vorlesung 23<\/a><time datetime=\"2021-02-03T13:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">3. Februar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser Vorlesung besch\u00e4ftigen wir uns mit Sonderf\u00e4llen f\u00fcr Sortieralgorithmen, durch die Sortieren in linearer Zeit erm\u00f6glicht wird.<\/div><\/li>\n<li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/02\/02\/vorlesung-22\/\">Vorlesung 22<\/a><time datetime=\"2021-02-02T11:30:00+01:00\" class=\"wp-block-latest-posts__post-date\">2. Februar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser Vorlesung besch\u00e4ftigen wir uns mit Medianen.<\/div><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image\"><img width=\"300\" height=\"212\" src=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/quick-sort-300x212.png\" class=\"attachment-medium size-medium wp-post-image\" alt=\"\" loading=\"lazy\" style=\"max-width:400px;\" srcset=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/quick-sort-300x212.png 300w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/quick-sort-1024x724.png 1024w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/quick-sort-768x543.png 768w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/quick-sort-1536x1086.png 1536w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/quick-sort-816x577.png 816w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/quick-sort.png 2000w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/27\/vorlesung-21\/\">Vorlesung 21<\/a><time datetime=\"2021-01-27T13:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">27. Januar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser Vorlesung kehren wir zur\u00fcck zu Sortieralgorithmen und stellen den Quicksort-Algorithmus vor.<\/div><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image\"><img width=\"300\" height=\"225\" src=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Mandelbrot_set_with_coloured_environment-300x225.png\" class=\"attachment-medium size-medium wp-post-image\" alt=\"\" loading=\"lazy\" style=\"max-width:400px;\" srcset=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Mandelbrot_set_with_coloured_environment-300x225.png 300w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Mandelbrot_set_with_coloured_environment-768x576.png 768w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Mandelbrot_set_with_coloured_environment-816x612.png 816w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Mandelbrot_set_with_coloured_environment.png 1024w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/26\/vorlesung-20\/\">Vorlesung 20<\/a><time datetime=\"2021-01-26T11:30:00+01:00\" class=\"wp-block-latest-posts__post-date\">26. Januar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser Vorlesung haben wir einen Exkurs in die nichtlineare Rekursion gemacht.<\/div><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image\"><img width=\"300\" height=\"141\" src=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/01\/U6_Beitrag-300x141.png\" class=\"attachment-medium size-medium wp-post-image\" alt=\"\" loading=\"lazy\" style=\"max-width:400px;\" srcset=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/01\/U6_Beitrag-300x141.png 300w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/01\/U6_Beitrag-1024x480.png 1024w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/01\/U6_Beitrag-768x360.png 768w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/01\/U6_Beitrag-816x383.png 816w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2021\/01\/U6_Beitrag.png 1147w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/22\/uebung-6\/\">\u00dcbung 6<\/a><time datetime=\"2021-01-22T08:34:54+01:00\" class=\"wp-block-latest-posts__post-date\">22. Januar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">Wir betrachten ein weiteres Beispiel f\u00fcr Mergesort und leiten erneut die Laufzeit des Sortieralgorithmus her, indem das Master-Theorem benutzt wird. Au\u00dferdem betrachten wir einen weiteren Sortieralgorithmus: Heapsort.<\/div><\/li>\n<li><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/20\/vorlesung-19\/\">Vorlesung 19<\/a><time datetime=\"2021-01-20T13:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">20. Januar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser Vorlesung besprechen wir weitere Details zu erzeugenden Funktionen und f\u00fchren das Master-Theorem ein.<\/div><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image\"><img width=\"300\" height=\"260\" src=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Sierpinski_triangle.svg_-300x260.png\" class=\"attachment-medium size-medium wp-post-image\" alt=\"\" loading=\"lazy\" style=\"max-width:400px;\" srcset=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Sierpinski_triangle.svg_-300x260.png 300w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Sierpinski_triangle.svg_-768x665.png 768w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Sierpinski_triangle.svg_-816x707.png 816w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/1024px-Sierpinski_triangle.svg_.png 1024w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/19\/vorlesung-18\/\">Vorlesung 18<\/a><time datetime=\"2021-01-19T11:30:00+01:00\" class=\"wp-block-latest-posts__post-date\">19. Januar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser Vorlesung leiten wir konkrete Laufzeitschranken f\u00fcr das Problem des Sortierens einer Liste von Zahlen her. Zudem machen wir uns Gedanken \u00fcber das L\u00f6sen von Rekursionsgleichungen.<\/div><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image\"><img width=\"300\" height=\"159\" src=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/mergesoert-300x159.png\" class=\"attachment-medium size-medium wp-post-image\" alt=\"\" loading=\"lazy\" style=\"max-width:400px;\" srcset=\"https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/mergesoert-300x159.png 300w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/mergesoert-1024x544.png 1024w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/mergesoert-768x408.png 768w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/mergesoert-816x433.png 816w, https:\/\/aud.ibr.cs.tu-bs.de\/wp-content\/uploads\/2020\/11\/mergesoert.png 1232w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div><a href=\"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/2021\/01\/13\/vorlesung-17\/\">Vorlesung 17<\/a><time datetime=\"2021-01-13T13:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">13. Januar 2021<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser Vorlesung geben wir eine Einf\u00fchrung in das Oberthema Sortieren. Wir stellen au\u00dferdem einen Sortieralgorithmus mit dem Namen Mergesort vor und stellen grundlegende \u00dcberlegungen zur Laufzeit von Sortieralgorithmen an.<\/div><\/li>\n<\/ul>","protected":false},"excerpt":{"rendered":"<p>Sortieren ist ein grundlegendes algorithmische Problem, das f\u00fcr viele komplexere Aufgaben ben\u00f6tigt wird. Zugleich bieten die zugeh\u00f6rigen Methoden und Prinzipien einen Einstieg in zahlreiche weiterf\u00fchrende Themen. Termine: Vorlesung 17 am 13.01.21 (11:30 Uhr): Aufgabenstellung, Mergesort Vorlesung 18 am 19.01.21 (09:45 Uhr): Behandeln von Rekursionen Vorlesung 19 am 20.01.21 (11:30 Uhr): Erzeugende Funktionen, Master-Theorem \u00dcbung 6 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":30,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/pages\/75"}],"collection":[{"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/comments?post=75"}],"version-history":[{"count":17,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/pages\/75\/revisions"}],"predecessor-version":[{"id":545,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/pages\/75\/revisions\/545"}],"up":[{"embeddable":true,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/pages\/30"}],"wp:attachment":[{"href":"https:\/\/aud.ibr.cs.tu-bs.de\/index.php\/wp-json\/wp\/v2\/media?parent=75"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}