Hvorfor bruge QuickSort?

http://www.cs.duke.edu/~mlittman/courses/Archive/cps130-97/lectures/lect06/lect06.html

QuickSort er blot en sorterings algoritme - altså en måde at sorterer nogle data på. Der findes utallige måder at sorterer på f.eks. bubble sort,quicksort, insertion sort etc der hver især har deres fordele og ulemper.

Forfattere der skriver lærebøger i programmering har, som du selv har opdaget, en forkærlighed for sorteringsalgoritmer og da quick sort er en ganske fornuftig en, er den selvfølgelig ganske udbredt i bøger

også fordi den tit er en udemærket introduktion til rekursivitet.

Hvad er rekursivitet (teoretisk).
Jeg har set rekursivitet som eksempler, men jeg vil have en teoretisk forklaring på hvad det er ?

Når du kalder noget rekursivt, så er det noget der kalder sig selv... Se på følgende:

function f(x: Integer): Integer;
begin
  if x > 10 then Result := 1 else
  Result := f(x+1);
end;

Den kalder sig selv et utal af gange, hvilket er helt lovligt... Resultatet bliver:

f(f(f(f(x)+1)+1)+1)+1 og så videre og så videre og så videre...

Det kan f.eks. være smart hvis du skal udregne fakultet (!6 = 1*2*3*4*5*6), eller hvis du laver en søgning hvor du søger du søger i undermapper (det har Borrisholt bl.a. lavet)...

Der findes mange eksempler hvor du kan have brug for at kalde noget rekursivt, men pas på uendelige lykker!!!! ;)

//hermandsen

Som hermandsen siger, så er Quicksort rigtig illustrativ, og så er det nok den hurtigste måde at sortere på. Og sortering af store talmængder er jo fint som eksempel(simpelt, mange tal, uoverskueligt i hånden og perfekt for programmer).

Hvis du vil vide noget mere on Resusive kald etc så kig på
http://www.pythia.dk/ under artikler. Jeg har skrevet en artikkel der hedder "En begynders guide til rekursion" Den kan læses der.

Jens B

QuickSort Er blandt de hurtigste sorterings algoritmer. De findes hurtigere, men de er svære at implm. I specielle tilfælde kan du overveje ar bruge andere algoritmer. Hvis du har en datamængde der er NÆSTEN sorteret er insertsort hurtigere end Quicksort, men det er måske kun 10% så det er pisse ligemeget, fordi hvis di datamængde er MEGET stor så er QuickSort igen hurtigere .....

Brug quicksort det gør Borland også. Her er et uddrag af kilde koden til TStringList.

procedure TStringList.CustomSort(Compare: TStringListSortCompare);
begin
  if not Sorted and (FCount > 1) then
  begin
    Changing;
    QuickSort(0, FCount - 1, Compare);
    Changed;
  end;
end;

Jens B