Matroids Matheplanet Forum Index
Moderiert von Bilbo matph
Matroids Matheplanet Forum Index » Informatik » Ein Array k-sortieren in O(n log k)
Autor
Universität/Hochschule J Ein Array k-sortieren in O(n log k)
Dennis28
Junior Letzter Besuch: im letzten Monat
Dabei seit: 26.05.2022
Mitteilungen: 13
  Themenstart: 2022-05-26

Hey ich brauche eure Hilfe bei folgender Aufgabe: Wir nennen ein Array A[1...n] k-sortiert, wenn man es in k Blöcke der Größe n/k aufteilen kann, so dass für jeden Block alle darin enthaltenen Elemente größer sind, als alle Elemente aus vorherigen Blöcken. Die Elemente innerhalb eines Blocks müssen nicht sortiert sein. Tipp: Sie dürfen in dieser Aufgabe annehmen, dass n durch k teilbar ist, und dass n und k Zweierpotenzen sind. a) Entwerfen Sie einen Algorithmus, der beliebige Arrays k-sortiert. Das heißt, das Eingabe Array soll so permutiert werden, dass es danach k-sortiert ist. Den Parameter k erhält Ihr Algorithmus als Eingabe. Ihr Algorithmus soll eine Laufzeit in O(n log k) haben. Ich verzweifle momentan an der Aufgabe, da mir jegliche Idee fehlt. Ich hoffe das mir jemand weiterhelfen kann. Grüße Dennis


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1155
Wohnort: Kiel, Deutschland
  Beitrag No.1, eingetragen 2022-05-26

Hallo Dennis28, und willkommen auf dem Matheplaneten. Da ist kein Bild. Alternativ kannst du die Aufgabe auch abtippen, mitsamt einem Hinweis, was du dir schon überlegt hast. mfg thureduehrsen


   Profil
Dennis28
Junior Letzter Besuch: im letzten Monat
Dabei seit: 26.05.2022
Mitteilungen: 13
  Beitrag No.2, vom Themenstarter, eingetragen 2022-05-26

Hey thureduehrsen, irgendwie hat er das Bild nicht übernommen. Naja habs jetzt mal abgetippt. Zu meinen Ideen: Wie gesagt mir fehlt hier leider total der Ansatz. Die einzige Idee die ich hatte, war das man vielleicht Quickselect benutzen könnte. Aber mehr habe ich dazu leider auch nicht.


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1155
Wohnort: Kiel, Deutschland
  Beitrag No.3, eingetragen 2022-05-26

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Quickselect dürfte hier aber rausfallen, da es im Worst Case quadratische Laufzeit hat. Überhaupt: reden wir von Worst-Case- oder Average-Case-Laufzeiten? Und was genau soll \(\mathcal{O}(n\,\log(k))\) bedeuten? Wenn \(k\) konstant ist, ist das dasselbe wie \(\mathcal{O}(n)\). mfg thureduehrsen\(\endgroup\)


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 266
  Beitrag No.4, eingetragen 2022-05-26

Moin, denke mal an divide and conquer: Kannst du einen Algroithmus angeben, der in O(n) eine Zwei-Sortierung deines Arrays leifert? Und wenn du den hast: Kannst du diesen durch wiederholte Anwendung auch für dein Problem gewinnbringend einsetzen?


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 266
  Beitrag No.5, eingetragen 2022-05-26

\quoteon(2022-05-26 16:01 - thureduehrsen in Beitrag No. 3) Überhaupt: reden wir von Worst-Case- oder Average-Case-Laufzeiten? Und was genau soll \(\mathcal{O}(n\,\log(k))\) bedeuten? Wenn \(k\) konstant ist, ist das dasselbe wie \(\mathcal{O}(n)\). \quoteoff Hier wird eine Worst-Case-Laufzeit-Betrachtung durchgeführt und n und k sind unabhängige Variablen, sodass du nicht einfach konstantes k annehmen kannst.


   Profil
Dennis28
Junior Letzter Besuch: im letzten Monat
Dabei seit: 26.05.2022
Mitteilungen: 13
  Beitrag No.6, vom Themenstarter, eingetragen 2022-05-26

\quoteon(2022-05-26 16:12 - Ixx in Beitrag No. 4) Moin, denke mal an divide and conquer: Kannst du einen Algroithmus angeben, der in O(n) eine Zwei-Sortierung deines Arrays leifert? Und wenn du den hast: Kannst du diesen durch wiederholte Anwendung auch für dein Problem gewinnbringend einsetzen? \quoteoff Naja für die erste Frage würden mir jetzt erstmal Mergesort und Quicksort einfallen. Aber ich weiß leider echt nicht wie ich die Aufgabe lösen soll mfg


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3135
  Beitrag No.7, eingetragen 2022-05-26

\quoteon(2022-05-26 15:48 - Dennis28 in Beitrag No. 2) Zu meinen Ideen: Wie gesagt mir fehlt hier leider total der Ansatz. Die einzige Idee die ich hatte, war das man vielleicht Quickselect benutzen könnte. Aber mehr habe ich dazu leider auch nicht. \quoteoff Passt doch. :-) 1. Finde den Median des Blocks via QuickSelect 2. Teile den Block damit in zwei passend gefilterte Hälften Wiederhole, bis du k Blöcke hast. Jede Interation läuft in Linearzeit (mit naivem Quickselect akkumuliert, mit erweitertem Pivotalgorithmus sogar deterministisch) und man benötigt O(log(k)) Iterationen, was die gewünschte Laufzeit ergibt. [Die Antwort wurde nach Beitrag No.2 begonnen.]


   Profil
Dennis28
Junior Letzter Besuch: im letzten Monat
Dabei seit: 26.05.2022
Mitteilungen: 13
  Beitrag No.8, vom Themenstarter, eingetragen 2022-05-26

Hey DerEinfaeltige, danke für die Hilfe. Die Idee habe ich soweit denke ich verstanden. Allerdings bekomme ich es gerade nicht in Code umgesetzt, kannst du mir da villeicht helfen? Habe momentan folgenden Python-Code, der aber nicht funktioniert: def ksort(A,k): return helpme (A, k, 0, len(A)-1) def hilfsfunktion (A, k, l, r): n=len(A) if r-l <= (n//k): return A else: x=(r-1)//2 quickselect(A, l, r, x) hilfsfunktion(A, k, l, x-1) hilfsfunktion(A, k, x, r) def quickselect(A, l, r, k): if l < r: q = partition(A, l, r) L = q - l + 1 if k < L: return quickselect(A, l, q-1, k) elif k > L: return quickselect(A, q+1, r, k-L) else: return A[q] else: return A[l] def partition(A, l, r): p = A[l] A[l], A[r] = A[r], A[l] s = l for i in range(l, r): if A[i] <= p: A[i], A[s] = A[s], A[i] s = s + 1 A[s], A[r] = A[r], A[s] return s mfg Dennis


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3135
  Beitrag No.9, eingetragen 2022-05-27

Vielleicht hilft diese Beispielimplementierung: \sourceon Python \numberson # Sort the slice array[lo:hi] into k blocks # with each block only containing values # greater than or equal the maximum of all # preceeding blocks def ksort(array,lo,hi,k): if k == 1: return median = find_median(array,lo,hi) partition(array,lo,hi,median) ksort(array,lo,(lo+hi)//2,k//2) ksort(array,(lo+hi)//2,hi,k-k//2) def find_median(array,lo,hi): return quick_select(array,lo,hi,(hi-lo)//2) # Select the k-th element of slice array[lo:hi] def quick_select(array,lo,hi,k): pivot = guess_pivot(array,lo,hi) lt,eq,gt = partition(array,lo,hi,pivot) if lt >= k: return quick_select(array,lo,lo+lt,k) if lt+eq >= k: return array[lo+k] return quick_select(array,hi-gt,hi,k-lt-eq) def guess_pivot(array,lo,hi): # If required, implement a more sophisticated pivot selection return sorted([array[lo],array[(lo+hi)//2],array[hi-1]])[1] # Partition the slice array[lo:hi] into three parts # according to the given pivot value # Return the length of each partition def partition(array,lo,hi,pivot): lt = [x for x in array[lo:hi] if x < pivot] eq = [x for x in array[lo:hi] if x == pivot] gt = [x for x in array[lo:hi] if x > pivot] array[lo:hi] = lt + eq + gt return len(lt),len(eq),len(gt) \sourceoff Zu klären wäre in jedem Fall die konkrete Aufgabenstellung. Sollen es vielleicht monoton steigende, näherungsweise gleichgroße Blöcke sein? (das liefert meine Implementierung, da ich das als sinnvoll erachte insbesondere auch der Zusatzbemerkung mit den 2er-Potenzen wegen) Oder sollen es wirklich streng(!) monoton steigende Blöcke sein? (Das wird problematisch, wenn bspw. alle n Elemente gleichgroß sind) Leere Blöcke sind ja wohl nicht erlaubt, da man sonst die Triviallösung mit k-1 leeren Blöcken anbieten könnte.


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1155
Wohnort: Kiel, Deutschland
  Beitrag No.10, eingetragen 2022-05-27

\quoteon(2022-05-27 08:54 - DerEinfaeltige in Beitrag No. 9) Vielleicht hilft diese Beispielimplementierung: \sourceon Python [...] def partition(array,lo,hi,pivot): lt = [x for x in array[lo:hi] if x < pivot] eq = [x for x in array[lo:hi] if x == pivot] gt = [x for x in array[lo:hi] if x > pivot] array[lo:hi] = lt + eq + gt return len(lt),len(eq),len(gt) \sourceoff Zu klären wäre in jedem Fall die konkrete Aufgabenstellung. \quoteoff Und zu klären wäre auch, welche Mittel beim Entwurf des Algorithmus zulässig sind. List Comprehensions wie hier sind zwar hübsch, aber vermutlich kein Standard in "Algorithmen und Datenstrukturen"-Vorlesungen. mfg thureduehrsen


   Profil
Dennis28 hat die Antworten auf ihre/seine Frage gesehen.
Dennis28 hat selbst das Ok-Häkchen gesetzt.
Dennis28 wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]