{"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-09-24T18:51:07","modified_gmt":"2021-09-24T16:51:07","slug":"kapitel-5-sortieren","status":"publish","type":"page","link":"https:\/\/aud.ibr.cs.tu-bs.de\/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<h2 class=\"wp-block-heading\">Vorlesungen<\/h2>\n\n\n<ul class=\"wp-block-latest-posts__list has-dates wp-block-latest-posts\"><li><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/grosse-uebung-10-fragestunde\/\">Gro\u00dfe \u00dcbung 9 &#8211; Fragestunde<\/a><time datetime=\"2023-02-09T11:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">9. Februar 2023<\/time><div class=\"wp-block-latest-posts__post-excerpt\">Quiz und ganz viel aus der Vorlesung!<\/div><\/li>\n<li><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-25\/\">Vorlesung 25<\/a><time datetime=\"2023-02-08T11:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">8. Februar 2023<\/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 loading=\"lazy\" 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=\"\" decoding=\"async\" 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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-24\/\">Vorlesung 24<\/a><time datetime=\"2023-02-07T09:30:00+01:00\" class=\"wp-block-latest-posts__post-date\">7. Februar 2023<\/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 loading=\"lazy\" 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=\"\" decoding=\"async\" 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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/uebung-8\/\">\u00dcbung 8<\/a><time datetime=\"2023-02-02T11:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">2. Februar 2023<\/time><div class=\"wp-block-latest-posts__post-excerpt\">chauen 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 loading=\"lazy\" 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=\"\" decoding=\"async\" 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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-23\/\">Vorlesung 23<\/a><time datetime=\"2023-02-01T11:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">1. Februar 2023<\/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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-22\/\">Vorlesung 22<\/a><time datetime=\"2023-01-31T09:30:00+01:00\" class=\"wp-block-latest-posts__post-date\">31. Januar 2023<\/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 loading=\"lazy\" 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=\"\" decoding=\"async\" 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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-21\/\">Vorlesung 21<\/a><time datetime=\"2023-01-25T11:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">25. Januar 2023<\/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 loading=\"lazy\" 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=\"\" decoding=\"async\" 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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-20\/\">Vorlesung 20<\/a><time datetime=\"2023-01-24T09:30:00+01:00\" class=\"wp-block-latest-posts__post-date\">24. Januar 2023<\/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 loading=\"lazy\" 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=\"\" decoding=\"async\" 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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/uebung-7\/\">\u00dcbung 7<\/a><time datetime=\"2023-01-19T11:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">19. Januar 2023<\/time><div class=\"wp-block-latest-posts__post-excerpt\">In dieser \u00dcbung schauen wir uns noch einmal das Sortierverfahren Mergesort an, leiten die Laufzeit her und betrachten auch noch mal das Mastertheorem. Zum Abschluss gibt es dann noch einen neuen Sortier-Algorithmus: Heapsort.<\/div><\/li>\n<li><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-19\/\">Vorlesung 19<\/a><time datetime=\"2023-01-18T11:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">18. Januar 2023<\/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 loading=\"lazy\" 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=\"\" decoding=\"async\" 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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-18\/\">Vorlesung 18<\/a><time datetime=\"2023-01-17T09:30:00+01:00\" class=\"wp-block-latest-posts__post-date\">17. Januar 2023<\/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 loading=\"lazy\" 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=\"\" decoding=\"async\" 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 class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/aud.ibr.cs.tu-bs.de\/vorlesung-17\/\">Vorlesung 17<\/a><time datetime=\"2023-01-11T11:15:00+01:00\" class=\"wp-block-latest-posts__post-date\">11. Januar 2023<\/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. Vorlesungen<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":30,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_uag_custom_page_level_css":"","site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"","footnotes":""},"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"Matthias Konitzny","author_link":"https:\/\/aud.ibr.cs.tu-bs.de\/author\/konitzny\/"},"uagb_comment_info":0,"uagb_excerpt":"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. Vorlesungen","_links":{"self":[{"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/pages\/75"}],"collection":[{"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/comments?post=75"}],"version-history":[{"count":18,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/pages\/75\/revisions"}],"predecessor-version":[{"id":705,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/pages\/75\/revisions\/705"}],"up":[{"embeddable":true,"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/pages\/30"}],"wp:attachment":[{"href":"https:\/\/aud.ibr.cs.tu-bs.de\/wp-json\/wp\/v2\/media?parent=75"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}