Author Topic: QuickSort Implementation (In-place method)  (Read 2644 times)

0 Members and 1 Guest are viewing this topic.

Offline CurryWurst

  • Camper
  • ***
  • Posts: 265
    • Soldat Global Account System
QuickSort Implementation (In-place method)
« on: July 21, 2008, 02:28:33 pm »
Script Name: QuickSort
Script Description: QuickSort - a very fast sort algorithm by using the principle "Divide & Conquer".
Original Author(s): Markus "Dual" Quär
Core Version: 2.6.3

This script allows you to sort integer as well as string arrays.
You can easily change the sort direction by swapping the relational operator  "<, >" in the following two lines of code:

1. while (Field[l] > Pivot) do
2. while (Field[r] < Pivot) do

Note: Default sort direction is in descending order.

Explanation of arguments (Thx for asking iDante):

Field - the array you would like to sort
Left - the first element of the array (actually it's always zero by dynamic arrays)
Right - the last element of the array (use ArrayHigh(YourArray) or GetArrayLength(YourArray) - 1 to get the highest possible element)

SortBy:
-------
Especially intended for my script, but i can explain it too ... you can use it, if each of your elements contains separated values for example the element[0] contains:'value1 Delimiter value2 Delimiter value3' and so on ... the other elements must contain the same structure as the first one.
If this condition is given, you can easily decide which of the values you like to use as compare value by setting the var SortBy to the position the compare value is located (Note: In my case, a tabulator is my delimiters, you can choose your own one by changing every "#9" brick to your delimiter). The pick of the bunch is, that every value can be a different type, so you can sort integers using an array of string :)

Here we go ...

/////////////////
  Integer sort: 
/////////////////

// Divide & Conquer :P
procedure QuickIntegerSort(var Field: array of integer; Left, Right: integer);
var   
  l, r, Buffer, Pivot: integer;
begin
  // Chek whether there is at least more than one element to sort
  if (Left < Right) then
  begin
    l:= Left;
    r:= Right;
    // Pick the Pivot element
    Pivot:= Field[(Left + Right) shr 1];
    // Presort
    repeat
      // Search an element which is smaller than the piviot
      while (Field[l] > Pivot) do
      begin
        Inc(l, 1);
      end;
      // Search an element which is greater than the pivot
      while (Field[r] < Pivot) do
      begin
        Dec(r, 1);
      end;
      // Swap the greater element with the smaller one
      if (l <= r) then
      begin
        Buffer:= Field[r];
        Field[r]:= Field[l];
        Field[l]:= Buffer;
        Inc(l, 1);
        Dec(r, 1);
      end;
    until (l >= r);
    if (Left < r) then
    begin
      QuickIntegerSort(Field, Left, r);
    end;
    if (Right > l) then
    begin
      QuickIntegerSort(Field, l, Right);
    end;
  end else
  begin
    exit;
  end;
end;

////////////////
  String sort:
////////////////

procedure QuickStringSort(var Field: array of string; Left, Right: integer);
var
  l, r: integer;
  Pivot, Buffer: string;
begin
  // Check whether there is at least more than one element to sort
  if (Left < Right) then
  begin
    l:= Left;
    r:= Right;
    // Pick the Pivot element
    Pivot:= Field[(Left + Right) shr 1];
    // Presort
    repeat
      // Search an element which is smaller than the piviot
      while (Field[l] > Pivot) do
      begin
        Inc(l, 1);
      end;
      // Search an element which is greater than the pivot
      while (Field[r] < Pivot) do
      begin
        Dec(r, 1);
      end;
      // Swap the greater element with the smaller one
      if (l <= r) then
      begin
        Buffer:= Field[r];
        Field[r]:= Field[l];
        Field[l]:= Buffer;
        Inc(l, 1);
        Dec(r, 1);
      end;
    until (l >= r);
    if (Left < r) then
    begin
      QuickStringSort(Field, Left, r);
    end;
    if (Right > l) then
    begin
      QuickStringSort(Field, l, Right);
    end;
  end else
  begin
    exit;
  end;
end; 

I'm using a combination of both to sort a TStringArray by different variable types.
It will be implemented in my upcoming project calling "LogInSystem"  :D

Here is a proper look at my development:

Code: [Select]
procedure QuickSort(var Field: array of string; Left, Right: integer; SortBy: integer); // Thanks DorkeyDear for your note
var
  l, r: integer;
  Pivot, Buffer: string;
begin
  if (Left < Right) then
  begin
    l:= Left;
    r:= Right;
    Pivot:= GetPiece(Field[(Left + Right) shr 1], #9, SortBy);
    repeat
      while (GetPiece(Field[l], #9, SortBy) > Pivot) do
      begin
        Inc(l, 1);
      end;
      while (GetPiece(Field[r], #9, SortBy) < Pivot) do
      begin
        Dec(r, 1);
      end;
      if (l <= r) then
      begin
        Buffer:= Field[r];
        Field[r]:= Field[l];
        Field[l]:= Buffer;
        Inc(l, 1);
        Dec(r, 1);
      end;
    until (l >= r);
    if (Left < r) then
    begin
      QuickSort(Field, Left, r, SortBy);
    end;
    if (Right > l) then
    begin
      QuickSort(Field, l, Right, SortBy);
    end;
  end else
  begin
    exit;
  end;
end; 

For more information visit http://en.wikipedia.org/wiki/Quicksort;)
« Last Edit: December 15, 2008, 06:11:59 pm by Markus Quär »
Soldat Global Account System: #soldat.sgas @ quakenet

Offline Neosano

  • Camper
  • ***
  • Posts: 253
  • IIAWAK!
Re: QuickSort Implementation (In-place method)
« Reply #1 on: July 21, 2008, 05:20:55 pm »
Well, sorry, but, how is it useful?
KAWAAAAAAAIIIIIIIIII

Offline JFK

  • Camper
  • ***
  • Posts: 255
    • My TraxInSpace Account
Re: QuickSort Implementation (In-place method)
« Reply #2 on: July 21, 2008, 05:57:14 pm »
It would be a efficient method of sorting arrays of strings or integeres.. That is, if it would work. I wonder if you tried to compile this and tested it out in your project. There are a few things I notice when i quickly go over the script:

You can input an array in the procedure, but nothing will come out. It looks as if you think that an 'array of String/Integer' is a pointer, but it's not. I think you will need to make a function out of it, one that will return the sorted array.

The procedure will call itself in the process. I'm not sure if that's possible, actually.. Is it?

I'm using a combination of both to sort a TStringArray by different variable types.
It will be implemented in my upcoming project calling "LogInSystem"  :D
I really wonder what you mean here. AFAIK a TStringArray is not much different as an Array of String... again: Is it?

Besides that it looks like an interesting part of code, also nice you like beer...



Come join: EliteCTF
Listen to: My Music

Offline CurryWurst

  • Camper
  • ***
  • Posts: 265
    • Soldat Global Account System
Re: QuickSort Implementation (In-place method)
« Reply #3 on: July 21, 2008, 06:01:52 pm »
Well, sorry, but, how is it useful?

I'm using it to sort user data by names, kills, deaths etc... for example. You can use QuickSort for every aspect when you want to sort a big amount of data in short time  ;)
Soldat Global Account System: #soldat.sgas @ quakenet

Offline DorkeyDear

  • Veteran
  • *****
  • Posts: 1506
  • Also known as Curt
    • Soldat Global Account System
Re: QuickSort Implementation (In-place method)
« Reply #4 on: July 21, 2008, 06:09:03 pm »
Dang man, this is wicked awesome! Definitly usful for charts and tables and stuff. Possibly could be used w/ my Table function to draw tables organized in any way on ppl''s consoles. Good job!

EDIT: using tstringarray instead of array of string slightly slows down the function, which can be bad for larger arrays.
« Last Edit: July 21, 2008, 06:11:55 pm by DorkeyDear »
Soldat Global Account System (SGAS): QuakeNet in #soldat.sgas
Rent Cheap Servers: contact CurryWurst

Offline CurryWurst

  • Camper
  • ***
  • Posts: 265
    • Soldat Global Account System
Re: QuickSort Implementation (In-place method)
« Reply #5 on: July 21, 2008, 06:24:23 pm »
You can input an array in the procedure, but nothing will come out. It looks as if you think that an 'array of String/Integer' is a pointer, but it's not. I think you will need to make a function out of it, one that will return the sorted array.

You have got it :D There shouldn't be an output, you can access on it by accessing on your array, but if you really like an output write a little workaround - you simply need a loop which writes each array element in line of a file.

The procedure will call itself in the process. I'm not sure if that's possible, actually.. Is it?

Yes, that's possible.

I'm using a combination of both to sort a TStringArray by different variable types.
It will be implemented in my upcoming project calling "LogInSystem"  :D
I really wonder what you mean here. AFAIK a TStringArray is not much different as an Array of String... again: Is it?

On the one hand you're absolutely right - I mean the sens of my sentences, but on the other hand I tried to express the way I'm doing my workaround by using a TSringArray for string content as well as integer vars. You will undertand what I mean, when I release my LogInSystem :)

Besides that it looks like an interesting part of code, also nice you like beer...

Thanks man =)

Date Posted: July 21, 2008, 07:20:07 pm
Dang man, this is wicked awesome! Definitly usful for charts and tables and stuff. Possibly could be used w/ my Table function to draw tables organized in any way on ppl''s consoles. Good job!

Yea yea yea, that's the way I'm using it! - I will post my table procedure later :)

EDIT: using tstringarray instead of array of string slightly slows down the function, which can be bad for larger arrays.

Oh didn't know that before, I'm really thankful for your note! I will fix my code as soon as possible.
« Last Edit: July 21, 2008, 07:41:49 pm by Markus Quär »
Soldat Global Account System: #soldat.sgas @ quakenet

Offline iDante

  • Veteran
  • *****
  • Posts: 1966
Re: QuickSort Implementation (In-place method)
« Reply #6 on: July 21, 2008, 06:56:05 pm »
Could you explain the args?
procedure QuickSort(var Field: array of string; Left, Right: integer; SortBy: integer);
I get Field, but what do Left, Right, and SortBy mean?

Offline CurryWurst

  • Camper
  • ***
  • Posts: 265
    • Soldat Global Account System
Re: QuickSort Implementation (In-place method)
« Reply #7 on: July 21, 2008, 07:39:23 pm »
Could you explain the args?
procedure QuickSort(var Field: array of string; Left, Right: integer; SortBy: integer);
I get Field, but what do Left, Right, and SortBy mean?

Okay. First of all use one of the codes above, so Integer sort or rather String sort, because the one you're asking for is a special QuickSort optimized for my own script, but if you are able to handle it, feel free to use it.

See #1 post for more information ;)
« Last Edit: July 22, 2008, 06:11:25 am by Markus Quär »
Soldat Global Account System: #soldat.sgas @ quakenet

Offline DorkeyDear

  • Veteran
  • *****
  • Posts: 1506
  • Also known as Curt
    • Soldat Global Account System
Re: QuickSort Implementation (In-place method)
« Reply #8 on: July 21, 2008, 09:47:46 pm »
Relating to the SortBy value, i suggest having two inputs, a delimiter string, along with the number of delimiter passes (that one getpiece number), but -1 = whole string though

EDIT: is there a choice for ascending or descending? I suggest having a boolean input for descending if true
« Last Edit: July 21, 2008, 09:49:17 pm by DorkeyDear »
Soldat Global Account System (SGAS): QuakeNet in #soldat.sgas
Rent Cheap Servers: contact CurryWurst

Offline CurryWurst

  • Camper
  • ***
  • Posts: 265
    • Soldat Global Account System
Re: QuickSort Implementation (In-place method)
« Reply #9 on: July 22, 2008, 05:07:46 am »
Relating to the SortBy value, i suggest having two inputs, a delimiter string, along with the number of delimiter passes (that one getpiece number), but -1 = whole string though

EDIT: is there a choice for ascending or descending? I suggest having a boolean input for descending if true

That's quite a good idea. I've implemented this idea in another function I made, therefore it won't be hard to figure out how to implement it.
I thought about having a choice to decide, whether the sort algorithm sorts in ascending or descending order too. I will code it in combination with Median-of-three :)

Edit: Do you mean that I still have to use GetPiece and adding the exception - 1 = whole string or do I have to implement my own loop catching all the split points and then using the value which comes before the split point as compare value?

I think you mean something like this?! (Note: This is just an example):
Edit: Added support for altering the sort order.
Edit: Minor bugfixes

Code: [Select]
// Divide & conquer in order you would like to sort:P
procedure QuickSort(var Field: array of string; Left, Right, SortBy: integer; Delimiter: string; DescendingOrder: boolean);
var
  l, r: integer;
  Pivot, Buffer, CompareValueL, CompareValueR: string;
begin
  // Chek whether there is at least more than one elment to sort
  if (Left < Right) then
  begin
    l:= Left;
    r:= Right;
    if (SortBy <= 0) then
    begin
      CompareValueL:= Field[l];
      CompareValueR:= Field[r];
      // Pick the Pivot element
      Pivot:= Field[(Left + Right) shr 1];
    end else
    begin
      CompareValueL:= GetPiece(Field[l], Delimiter, SortBy);
      CompareValueR:= GetPiece(Field[l], Delimiter, SortBy);
       // Pick the Pivot element
      Pivot:= GetPiece(Field[(Left + Right) shr 1], Delimiter, SortBy);
    end;
    repeat
      if (DescendingOrder = true) then
      begin
        // Search an element which is smaller than the piviot
        while (CompareValueL > Pivot) do
        begin
          Inc(l, 1);
        end;
        // Search an element which is greater than the pivot
        while (CompareValueR < Pivot) do
        begin
          Dec(r, 1);
        end;
      end else
      begin
        // Search an element which is greater than the pivot
        while (CompareValueL < Pivot) do
        begin
          Inc(l, 1);
        end;
        // Search an element which is smaller than the pivot
        while (CompareValueR > Pivot) do
        begin
          Dec(r, 1);
        end;
      end;
      // Swap the greater element with the smaller one
      if (l <= r) then
      begin
        Buffer:= Field[r];
        Field[r]:= Field[l];
        Field[l]:= Buffer;
        Inc(l, 1);
        Dec(r, 1);
      end;
    until (l >= r);
    if (Left < r) then
    begin
      QuickSort(Field, Left, r, SortBy, Delimiter, DescendingOrder);
    end;
    if (Right > l) then
    begin
      QuickSort(Field, l, Right, SortBy, Delimiter, DescendingOrder);
    end;
  end else
  begin
    exit;
  end;
end; 
« Last Edit: August 27, 2008, 09:19:05 am by Markus Quär »
Soldat Global Account System: #soldat.sgas @ quakenet

Offline DorkeyDear

  • Veteran
  • *****
  • Posts: 1506
  • Also known as Curt
    • Soldat Global Account System
Re: QuickSort Implementation (In-place method)
« Reply #10 on: July 22, 2008, 05:45:19 pm »
Quote
Edit: Do you mean that I still have to use GetPiece and adding the exception - 1 = whole string
Yes
Soldat Global Account System (SGAS): QuakeNet in #soldat.sgas
Rent Cheap Servers: contact CurryWurst

Offline CurryWurst

  • Camper
  • ***
  • Posts: 265
    • Soldat Global Account System
Re: QuickSort Implementation (In-place method)
« Reply #11 on: May 10, 2009, 03:24:50 pm »
I updated the script. It's much more reliable and can handle strings representing numeric values.
Set Ival to true if you want to sort strings representing numeric values.

Here we go...

Code: [Select]
function ZeroFill(S: string; Peak: integer; IsEnabled: boolean): string;
var
  i, m: integer;
begin
  if (IsEnabled) then
  begin
    m:= Peak - length(S);
    for i:= 1 to m do
    begin
      S:= '0' + S;
    end;
  end;
  result:= S;
end;

function QuickSort(var AOS: array of string; Left, Right: integer; Ival: boolean): integer;
var
  b, e, Pivot: string;
  i, l, m, r: integer;
begin
  if (Right > Left) then
  begin
    for i:= 0 to Right do
    begin
      if (length(AOS[i]) > m) then
      begin
        m:= length(AOS[i]);
      end;
    end;
    l:= Left;
    r:= Right;
    Pivot:= ZeroFill(AOS[Random(Left, Right)], m, Ival);
    repeat
      while ((ZeroFill(AOS[l], m, IVal) > Pivot) and (l < Right)) do
      begin
        Inc(l, 1);
      end;
      while ((ZeroFill(AOS[r], m, IVal) < Pivot) and (r > Left)) do
      begin
        Dec(r, 1);
      end;
      if (l <= r) then
      begin
        b:= AOS[r];
        AOS[r]:= AOS[l];
        AOS[l]:= b;
        Inc(l, 1);
        Dec(r, 1);
        Inc(Result, 1);
      end;
    until (l >= r);
    if (Left < r) then
    begin
      QuickSort(AOS, Left, r, Ival);
    end;
    if (Right > l) then
    begin
      QuickSort(AOS, l, Right, Ival);
    end;
  end else
  begin
    exit;
  end;
end;

Feel free to use this function in your script :)
Soldat Global Account System: #soldat.sgas @ quakenet

Offline soldat-game

  • Camper
  • ***
  • Posts: 255
  • GG: 10210041
Re: QuickSort Implementation (In-place method)
« Reply #12 on: June 12, 2017, 10:53:15 am »
QuickSort3(AllPlayers, 0, AllPlayers.Count-1, true, 0); Work good
QuickSort3(AllPlayers, AllPlayers.Count-1, 0, true, 0); Already sorts wrong?

Code: [Select]
function ZeroFill(S: string; Peak: integer; IsEnabled: boolean): string;
var i, m: integer;
begin
if (IsEnabled) then begin
m:= Peak - length(S);
for i:= 1 to m do S:= '0' + S;
    end;
result:= S;
end;

function QuickSort3(var AOS: TStringList; Left, Right: integer; Ival: boolean; SortBy: integer): integer;
var b, e, Pivot: string; i, l, m, r: integer;
begin
if (Right > Left) then begin
for i:= 0 to Right do begin
e:= GetPiece(AOS[i], ':', SortBY);
if (length(e) > m) then m:= length(e);
end;
l:= Left; r:= Right;
Pivot:= ZeroFill(GetPiece(AOS[Random(Left, Right)],':', SortBy), m, Ival);
repeat
while ((ZeroFill(GetPiece(AOS[l], ':', SortBy), m, IVal) > Pivot) and (l < Right)) do Inc(l, 1);
while ((ZeroFill(GetPiece(AOS[r], ':', SortBy), m, IVal) < Pivot) and (r > Left)) do Dec(r, 1);
if (l <= r) then begin
b:= AOS[r];
AOS[r]:= AOS[l];
AOS[l]:= b;
Inc(l, 1);
Dec(r, 1);
Inc(Result, 1);
end;
until (l >= r);
if (Left < r) then QuickSort3(AOS, Left, r, Ival, SortBy);
if (Right > l) then QuickSort3(AOS, l, Right, Ival, SortBy);
end else exit;
end;

Should zerofill not look like that?
Code: [Select]
function ZeroFill(S: string; Peak: integer; IsEnabled: boolean): string;
var i, m: integer; zero:string
begin
if (IsEnabled) then begin
m:= Peak - length(S);
for i:= 1 to m do zero:= '0' + zero;
    end;
result:= zero+S;
end;