Ergebnis der Suchanfrage

• Forum: Programmieren allgemein

  Re: Insertion Sort Problem

   
    by r2c2, 28. Okt 2006
  Also ich würde sagen out-of-place is bei verketteten Listen eher komplizierter, da man jeweils die einzelnen Items neu erzeugen muss(siehe unten).
  
  
  Das wäre aber auch wieder in-plcae, da du die Daten nicht doppelt im Speicher hast. Du hast eben nur n 2. Pointer. Und den brauchst du sowieso, weil du den Anfang des unsortieren Bereiches braucht. Welche Pointer baucht man nun fürs...
• Forum: Programmieren allgemein

  Re: Insertion Sort Problem

   
    by r2c2, 28. Okt 2006
  Für was out-of-place sortieren? InsertionSort is doch geradezu gemacht dafür Verkettete Listen zu sortieren... Warum? Verschieben is bei verketteten Listen O(1), bei arrays O(n)(naja nciht ganz, das wär jetzt worst-case. Im average-case isses etwas besser). Du kannst also annähernd linear sortieren! Jedenfalls in Bezug auch die Zuweisungen.
  
  Alles was du dazu brauchst is ne...