Forum > Beginners

QuickSort Problem

<< < (2/3) > >>

avk:
Just in case, I would like to add a few remarks.
1. Since the FPC currently supports array slices well, there is no particular need to pass the start and end indexes to the QuickSort() procedure:

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---procedure QuickSort(var AI: array of Integer);var  Lo, Hi, Pivot, T: Integer;begin  Lo := Low(AI);  Hi := High(AI);  Pivot := AI[(Lo + Hi) div 2];  repeat    while AI[Lo] < Pivot do      Inc(Lo);    while AI[Hi] > Pivot do      Dec(Hi);    if Lo <= Hi then    begin      T := AI[Lo];      AI[Lo] := AI[Hi];      AI[Hi] := T;      Inc(Lo);      Dec(Hi);    end;  until Lo > Hi;  if Hi > Low(AI) then    QuickSort(AI[Low(AI)..Hi]);  if Lo < High(AI) then    QuickSort(AI[Lo..High(AI)]);end; 
2. For sorting arrays of several dozen elements, such QuickSort() is inefficient, it is better to use InsertionSort().
3. For large arrays, this implementation guarantees neither O(n log n) time complexity nor O(log n) space complexity.

PascalDragon:

--- Quote from: avk on June 15, 2022, 08:32:20 am ---1. Since the FPC currently supports array slices well, there is no particular need to pass the start and end indexes to the QuickSort() procedure:
--- End quote ---

Though array slices only work if it's declared as an open array like you (and JLWest) did and not as a dynamic array like Handoko adjusted it. (And “currently” is a bit of a misnomer, as FPC supports these for quite some time already)

avk:

--- Quote from: PascalDragon on June 15, 2022, 08:51:15 am ---...
 (And “currently” is a bit of a misnomer, as FPC supports these for quite some time already)

--- End quote ---

As you wish, but "for quite some time already" is somewhat of a relative term, how often do you come across examples of using array slices in the wild?
I haven't checked for a while, but it seems that Delphi still has some problems with this?

PascalDragon:

--- Quote from: avk on June 15, 2022, 10:49:53 am ---
--- Quote from: PascalDragon on June 15, 2022, 08:51:15 am ---...
 (And “currently” is a bit of a misnomer, as FPC supports these for quite some time already)

--- End quote ---

As you wish, but "for quite some time already" is somewhat of a relative term, how often do you come across examples of using array slices in the wild?
--- End quote ---

Then if you want an absolute time: array slices where introduced in October 2006, thus are available since FPC 2.2.0.


--- Quote from: avk on June 15, 2022, 10:49:53 am ---I haven't checked for a while, but it seems that Delphi still has some problems with this?

--- End quote ---

Delphi supports array slices only in the form of the Slice intrinsic (which FPC supports as well).

avk:

--- Quote from: PascalDragon on June 15, 2022, 01:51:00 pm ---...
Then if you want an absolute time: array slices where introduced in October 2006, thus are available since FPC 2.2.0.
...

--- End quote ---

Thanks, but still curious, how often do you see this very handy feature being used in some code?


--- Quote from: PascalDragon on June 15, 2022, 01:51:00 pm ---...
Delphi supports array slices only in the form of the Slice intrinsic
...

--- End quote ---

That is, everything there is the same as it was many years ago.

Navigation

[0] Message Index

[#] Next page

[*] Previous page

Go to full version