Die Mathe-Redaktion - 19.11.2017 20:39 - Registrieren/Login
Auswahl
Schwarzes Brett
Fragensteller hat Anwort gelesen, aber bisher nicht weiter reagiert2017-11-19 20:01 bb
Matheformeln mit MathML
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 884 Gäste und 32 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Sortieren Bubble-Sort & Insertion-Sort Allgemein
Druckversion
Druckversion
Autor
Universität/Hochschule J Sortieren Bubble-Sort & Insertion-Sort Allgemein
jul4ik
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 18.10.2017
Mitteilungen: 4
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-11-10 14:33


Hallo, ich habe in der Uni, diese Aufgabe gestellt bekommen:

"Geben Sie für Bubble-Sort (mit Abbruchkontrolle) und Insertion-Sort an, auf welcher Art von Eingabefeldern eine maximale Anzahl an Vergleichen bzw. Vertauschungen in Abhängigkeit von der Größe n des Eingabefeldes benötigt wird. Begründen Sie jeweils ihre Antwort."

Doch leider weiss ich nicht ganz genau was ich machen soll (also eher ein Verständnissproblem).

Ich hätte jetzt die Aufgabe so verstanden, dass ich, zum beispiel für Bubble-Sort angebe, dass man maximal n(n-1)/2 Schlüsselvergleiche und max. 3n(n-1)/2 Satzbewegungen braucht und Begründe warum n(n-1)/2 Schlüsselvergleiche und 3n(n-1)/2 Satzbewegungen man braucht.
Das selbe würde ich für Insertion-Sort machen: maximal n(n-1)/2 Schlüsselvergleiche und maximal (n^2+3n-4)/2 Satzbewegungen.

Wäre denn meine Denkweise so richtig oder habe ich die Aufgabe doch nicht richtig verstanden.
 confused  



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5294
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-11-11 15:18


Hallo,

Bei klassischer Implementierung ist in beiden Fällen ein absteigend sortiertes Array der Worst Case smile
Dies bedeutet für Bubblesort <math>n\cdot(n-1)/2</math> Vertauschungen und nach dem mindestens ebenso viele Vergleiche notwendig sind, hier die gleiche Anzahl.
Für Insertionsort gilt das selbe bei naiver Implementierung, man kann allerdings die Suche allerdings etwas intelligenter gestalten und auch mit weniger Verschiebeoperationen auskommen, doch dann wird die Komplexitätsanalyse etwas komplizierter.

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



  Profil  Quote  Link auf diesen Beitrag Link
jul4ik hat die Antworten auf ihre/seine Frage gesehen.
jul4ik hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 

 AQA

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-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]