SRL Archive - Research & Development Lounge

Well, i made some functions related to Radix Sort.. Its quite effective way of sorting things..
Try to understand it ^^

program Hoi;
Const
  Radix = 10;  //I can't really explain.. Radix 10 is used the most.. It stands for 0,1,2,3,4,5,6,7,8,9.. And if your using negative numbers to, its -9..9
Procedure RadixSort(Integers : TIntegerArray; Digits : Integer; Negative : Boolean);
var
  Dump : Array[-Radix + 1..Radix-1] of TIntegerArray; //We store them temporary here
  Counts : Array[-Radix + 1..Radix-1] of Integer; //Counts, for the length of the Dump
  Len,Divider,I,II,III,Temporary,Counter : Integer;
  RadixMax,RadixMin : integer;
begin
  Divider := 1; //We use this, to sort all the digits time by time ;).
  Len := High(Integers);
  if Negative then
    RadixMin := -Radix + 1
  else
    RadixMin := 0;
  RadixMax := Radix - 1;
  For I := RadixMin to RadixMax do
    SetLength(Dump[I],Len + 1);
  For I := 1 to Digits do //Digits!
  begin;
    For II := RadixMin to RadixMax do
      Counts[II] := -1; //Reset the counts
    For II := 0 to Len do
    begin;
      Temporary := (Integers[II] div Divider) mod Radix // We get the single digit of the number..
      Counts[Temporary] := Counts[Temporary] + 1; //Increase the Counts ;)
      Dump[Temporary][Counts[Temporary]] := Integers[II]; //Store the whole number in in its own digit 'dump', 0 to Radix - 1.. E.G. : Dump[0][0] := Integers[II];
    end;
    Counter := -1;
    For II := RadixMin to RadixMax do
      For III := 0 to  Counts[II] do
      begin;
        Counter := Counter + 1;
        Integers[Counter] := Dump[II][III]; //Place back the orignal var, "Integers"
      end;
    Divider := Divider * Radix; //So that we go to the next Digit
  end;
end;

Function GetDigits( Num  : Integer):Integer;
begin;
  if Num = 0 then Result := 1;
  While Num <> 0 do
  begin;
    Result := Result + 1;
    Num := Num div 10;
  end;
end;

Function GetDigitsArray ( Ints : TIntegerArray) : Integer;
var
  C,I : Integer;
  Len : Integer;
begin;
  Len := High(Ints);
  if Len < 0 then Exit;
  C := 1;
  For I := 0 to Len do
    if (Ints[I] >= C) or (Ints[I] <= -C) then
    begin;
      C := C * 10;
      Dec(I);
    end;
  Result := GetDigits(C - 1);
end;

var
  Ints : TIntegerArray;
  I : integer;
  Time : Integer;
begin
  Writeln(inttostr(GetDigits(100)));
  Writeln(inttostr(GetDigitsArray([15,0,10,-99])));
//  exit;
  SetLength(Ints,1000);
  For I := 0 to 999 do
   Ints[I] := Random(999) - Random(999);
  Time := GetSystemTime;
  RadixSort(Ints,GetDigitsArray(Ints),True);
  Time := GetSystemTime - Time;
  For I := 0 to high(ints) do
   Writeln(inttostr(ints[I]));
  Writeln(IntToStr(Time) + ' msec - RadixSort with Digit finding!');
end.

Lemme guess how it works:
Imagine you got a bunch of numbers:
32, 12, 89, 1023, 6581 and 2364
First it'll sort the last digits:
6581, 32, 12, 1023, 2364 and 89
Then it'll sort the second last digits
12, 1023, 32, 2364, 6581, 89
Then the third last digits:
12, 32, 89, 1023, 2364, 6581 (ok, they are already sorted now) and so on :)

Am I right? ^^

From: Markus
Wow, Radixsort, isnt it one of the fastest sorting algorithms around?

Lemme guess how it works:
Imagine you got a bunch of numbers:
32, 12, 89, 1023, 6581 and 2364
First it'll sort the last digits:
6581, 32, 12, 1023, 2364 and 89
Then it'll sort the second last digits
12, 1023, 32, 2364, 6581, 89
Then the third last digits:
12, 32, 89, 1023, 2364, 6581 (ok, they are already sorted now) and so on :)

Am I right? ^^

Yep! Idk.. Depends on what your sorting etc..

Someone else mentioned radix sort not too long ago… You do know that the only reason radix sort was ever used was because its easy to do mechanically right? It was designed to sort punch cards when some retard dropped a stack of 1000+ cards which had to be in the right order ;) Problem is, compared to other algorithms, its just not that fast…

program Hoi;
Const
  Radix = 10;  //I can't really explain.. Radix 10 is used the most.. It stands for 0,1,2,3,4,5,6,7,8,9.. And if your using negative numbers to, its -9..9
Procedure RadixSort(Integers : TIntegerArray; Digits : Integer; Negative : Boolean);
var
  Dump : Array[-Radix + 1..Radix-1] of TIntegerArray; //We store them temporary here
  Counts : Array[-Radix + 1..Radix-1] of Integer; //Counts, for the length of the Dump
  Len,Divider,I,II,III,Temporary,Counter : Integer;
  RadixMax,RadixMin : integer;
begin
  Divider := 1; //We use this, to sort all the digits time by time ;).
  Len := High(Integers);
  if Negative then
    RadixMin := -Radix + 1
  else
    RadixMin := 0;
  RadixMax := Radix - 1;
  For I := RadixMin to RadixMax do
    SetLength(Dump[i],Len + 1);
  For I := 1 to Digits do //Digits!
  begin;
    For II := RadixMin to RadixMax do
      Counts[II] := -1; //Reset the counts
    For II := 0 to Len do
    begin;
      Temporary := (Integers[II] div Divider) mod Radix // We get the single digit of the number..
      Counts[Temporary] := Counts[Temporary] + 1; //Increase the Counts ;)
      Dump[Temporary][Counts[Temporary]] := Integers[II]; //Store the whole number in in its own digit 'dump', 0 to Radix - 1.. E.G. : Dump[0][0] := Integers[II];
    end;
    Counter := -1;
    For II := RadixMin to RadixMax do
      For III := 0 to  Counts[II] do
      begin;
        Counter := Counter + 1;
        Integers[Counter] := Dump[II][III]; //Place back the orignal var, "Integers"
      end;
    Divider := Divider * Radix; //So that we go to the next Digit
  end;
end;

Function GetDigits( Num  : Integer):Integer;
begin;
  if Num = 0 then Result := 1;
  While Num <> 0 do
  begin;
    Result := Result + 1;
    Num := Num div 10;
  end;
end;

Function GetDigitsArray ( Ints : TIntegerArray) : Integer;
var
  C,I : Integer;
  Len : Integer;
begin;
  Len := High(Ints);
  if Len < 0 then Exit;
  C := 1;
  For I := 0 to Len do
    if (Ints[i] >= C) or (Ints[i] <= -C) then
    begin;
      C := C * 10;
      Dec(I);
    end;
  Result := GetDigits(C - 1);
end;

procedure QuickSort(var arr: TIntegerArray; s, e: integer);
var
  cs, ce: Integer;
  pivot, swap: Variant;
begin
  cs:= s;
  ce:= e;
  pivot:= arr[(s + e) / 2];
  repeat
    while arr[cs] > pivot do cs:= cs + 1;
    while arr[ce] < pivot do ce:= ce - 1;
    if cs <= ce then
    begin
      swap:= arr[cs];
      arr[cs]:= arr[ce];
      arr[ce]:= swap;
      cs:= cs + 1;
      ce:= ce - 1;
    end;
  until cs > ce;
  if ce > s then QuickSort(arr, s, ce);
  if cs < e then QuickSort(arr, cs, e);
end;

var
  Ints : TIntegerArray;
  I : integer;
  Time : Integer;
begin


  SetLength(Ints,1000);
  For I := 0 to 999 do
   Ints[i] := Random(999) - Random(999);
  Time := GetSystemTime;
  RadixSort(Ints,GetDigitsArray(Ints),True);
  Time := GetSystemTime - Time;
  {For I := 0 to high(ints) do
   Writeln(inttostr(ints[i]));}
  Writeln(IntToStr(Time) + ' msec - RadixSort with Digit finding!');

  SetLength(Ints,1000);
  For I := 0 to 999 do
   Ints[i] := Random(999) - Random(999);
  Time := GetSystemTime;
  QuickSort(Ints,0,999);
  Time := GetSystemTime - Time;
  {For I := 0 to high(ints) do
   Writeln(inttostr(ints[i])); }
  Writeln(IntToStr(Time) + ' msec - Quicksort!');
  
end.

Successfully compiled
156 msec - RadixSort with Digit finding!
78 msec - Quicksort!
Successfully executed

From: BenLand100
Someone else mentioned radix sort not too long ago… You do know that the only reason radix sort was ever used was because its easy to do mechanically right? It was designed to sort punch cards when some retard dropped a stack of 1000+ cards which had to be in the right order ;) Problem is, compared to other algorithms, its just not that fast…

I never claimed it was the fastest way, i said it is a fast way ;).

The difference is, Quicksort isn't stable (Wikipedia..), while radixsort is..

How 'bout you make it faster by using C++?


Lolz. XD. Nice googling skillz though, I'd never know where to start with something like this…




But, Ben, my Dad has told me how GAY it was when you dropped a punch-card program…

I tested radixsort and another one called quicksort a while ago. Quicksort, if I remember right, was quite a bit faster. Though, when I tried to put it in a plugin, I got a lot of errors. I don't know if that was because I did something wrong, or because of quicksort itself though.

EDIT: Oh, I see you mentioned it already Ben…

From: mastaraymond
I never claimed it was the fastest way, i said it is a fast way ;).

The difference is, Quicksort isn't stable (Wikipedia..), while radixsort is..

If you can give me a real life situation where stability is a problem, I might consider that a valid point ;) As it stands, it would be quicker to sort a key/value set twice (once for each key and then like keys by values) with quicksort than comparing them with radix sort. Even then, because radix sort is stable, the like-key entries would not be sorted, just in the same order they were in. Doing a more precise comparison of the two sorts yields:

Successfully compiled
Random Numbers took on average 12.5ms
QuickSort took on average 87.5ms
RadixSort took on average 203.1ms
Successfully executed

From: R0b0t1
But, Ben, my Dad has told me how GAY it was when you dropped a punch-card program…

Yes, especially if the jackass that wrote it didn't take the time to number the cards so the card sorter can sort them… In that case you just buy a new set cause there is almost no way to get it back to the way it should be ;)

Wait… You were AROUND back then? Damn! Did you play fetch with a Tyrannosaurus?

From: R0b0t1
Wait… You were AROUND back then? Damn! Did you play fetch with a Tyrannosaurus?

I wasn't around back then, in the normal sense of the word, seeings as I'm only 17… However, that does not mean that I haven't worked with a punch card machine ;)

Oh, those things are still around? Like to get my hands on one…

But ben, my intentions weren't publish the Fastest Way of soritng array's.. I wanted people to learn how it works.. Its just an different way of sorting, non recusion…

From: mastaraymond
But ben, my intentions weren't publish the Fastest Way of soritng array's.. I wanted people to learn how it works.. Its just an different way of sorting, non recusion…

From: Markus
Wow, Radixsort, isnt it one of the fastest sorting algorithms around?

I was responding to that anyway ;)

Ben! Your last 3 posts have ended with a ";)"!!!

From: BenLand100
Yes, especially if the jackass that wrote it didn't take the time to number the cards so the card sorter can sort them… In that case you just buy a new set cause there is almost no way to get it back to the way it should be ;)

From: BenLand100
I wasn't around back then, in the normal sense of the word, seeings as I'm only 17… However, that does not mean that I haven't worked with a punch card machine ;)

From: BenLand100
I was responding to that anyway ;)

Roflcopter :D

–Useful post here–
Radixsort looks like a fast way of sorting :D If I'm getting it right, this could be converted to a script that can sort words alphabetically? That'd be cool :p But for no use :D

(Only 4 smileys in my post :D 5 Now)

-Knives

Hey! I didn't post anything :D

From: King of Knives
Ben! Your last 3 posts have ended with a ";)"!!!



Roflcopter :D

–Useful post here–
Radixsort looks like a fast way of sorting :D If I'm getting it right, this could be converted to a script that can sort words alphabetically? That'd be cool :p But for no use :D

(Only 4 smileys in my post :D 5 Now)

-Knives

Yeah, this can be used for words to.. If your interested…

Oh, btw Ben!

I made a little compare script.. In rare circumstantials RadixSort is faster than Quicksort, overall Quicksort is better! BUT, CountSort.. Well, it's a real fast one.. Although CountSort takes some more memory, its a quite effective algorithm for array's with small numbers.. (Which we have in SCAR a lot). I made it work with negative's also,

heres the script:

program Hoi;
Const
  ArrayLength = 9999; //The length of the input array
  Negatives = True; //Put in Negative numbers?
  Randoms = 9999; // The random?






  Radix = 10;  //I can't really explain.. Radix 10 is used the most.. It stands for 0,1,2,3,4,5,6,7,8,9.. And if your using negative numbers to, its -9..9

Procedure RadixSort(Integers : TIntegerArray; Digits : Integer; Negative : Boolean);
var
  Dump : Array[-Radix + 1..Radix-1] of TIntegerArray; //We store them temporary here
  Counts : Array[-Radix + 1..Radix-1] of Integer; //Counts, for the length of the Dump
  Len,Divider,I,II,III,Temporary,Counter : Integer;
  RadixMax,RadixMin : integer;
begin
  Divider := 1; //We use this, to sort all the digits time by time ;).
  Len := High(Integers);
  if Negative then
    RadixMin := -Radix + 1
  else
    RadixMin := 0;
  RadixMax := Radix - 1;
  For I := RadixMin to RadixMax do
    SetLength(Dump[I],Len + 1);
  For I := 1 to Digits do //Digits!
  begin;
    For II := RadixMin to RadixMax do
      Counts[II] := -1; //Reset the counts
    For II := 0 to Len do
    begin;
      Temporary := (Integers[II] div Divider) mod Radix // We get the single digit of the number..
      Counts[Temporary] := Counts[Temporary] + 1; //Increase the Counts ;)
      Dump[Temporary][Counts[Temporary]] := Integers[II]; //Store the whole number in in its own digit 'dump', 0 to Radix - 1.. E.G. : Dump[0][0] := Integers[II];
    end;
    Counter := -1;
    For II := RadixMin to RadixMax do
      For III := 0 to  Counts[II] do
      begin;
        Counter := Counter + 1;
        Integers[Counter] := Dump[II][III]; //Place back the orignal var, "Integers"
      end;
    Divider := Divider * Radix; //So that we go to the next Digit
  end;
end;

Procedure MySort(var Integers : TIntegerArray);
var
  Counts : Array of Integer;
  Min, Max : Integer;
  I,II,Len,CountOr : Integer;
begin;
  Len := High(integers);
  Max := Integers[0];
  Min := Integers[0];
  For I := 1 to Len do
  begin;
    if Integers[I] < Min then
      Min := Integers[I]
    else if Integers[I] > max then
      Max := Integers[I];
  end;
  CountOr := 0;
  if Min < 0 then
  begin;
    Min := -Min;
    Max := Min  + Max;
    SetLength(Counts, Max + 1);
    For I := 0 to Len do
      Inc(Counts[Integers[I] + Min]);
    For I := 0 to Max do
      For II := 1 to Counts[I] do
      begin;
        Integers[CountOr] := I - Min;
        CountOr := CountOr + 1;
      end;
  end else
  begin;
    SetLength(Counts,Max +1 );
    For I := 0 To Len do
      Inc(Counts[INtegers[I]])
    For I := Min to Max do
      For II := 1 to Counts[I] do
      begin;
        Integers[CountOr] := I;
        CountOr := CountOr + 1;
      end;
  end;
end;

procedure QuickSort(var arr: TIntegerArray; s, e: integer);
var
  cs, ce: Integer;
  pivot, swap: INteger;
begin
  cs:= s;
  ce:= e;
  pivot:= arr[(s + e) div 2];
  repeat
    while arr[cs] < pivot do cs:= cs + 1;
    while arr[ce] > pivot do ce:= ce - 1;
    if cs <= ce then
    begin
      swap:= arr[cs];
      arr[cs]:= arr[ce];
      arr[ce]:= swap;
      cs:= cs + 1;
      ce:= ce - 1;
    end;
  until cs > ce;
  if ce > s then QuickSort(arr, s, ce);
  if cs < e then QuickSort(arr, cs, e);
end;

Function GetDigits( Num  : Integer):Integer;
begin;
  if Num = 0 then Result := 1;
  Num := iAbs(Num);
  While Num > 0 do
  begin;
    Result := Result + 1;
    Num := Num div 10;
  end;
end;

Function GetDigitsArray ( Ints : TIntegerArray) : Integer;
var
  C,I : Integer;
  Len : Integer;
begin;
  Len := High(Ints);
  if Len < 0 then Exit;
  C := 1;
  For I := 0 to Len do
    if (Ints[I] >= C) or (Ints[I] <= -C) then
    begin;
      C := C * 10;
      Dec(I);
    end;
  Result := GetDigits(C - 1);
end;

var
  Ints,SortInts : TIntegerArray;
  I,Len : integer;
  J : Integer;
  Time : Integer;
begin
{  Writeln(inttostr(GetDigits(100)));
  Writeln(inttostr(GetDigitsArray([15,0,10,-99])));    }
//  exit;
  SetLength(Ints, ArrayLength);
  Len := High(ints);
  SetLength(SortInts,Len+ 1);
  if Negatives then
    For I := 0 to Len do
     Ints[I] := Random(Randoms) - Random(Randoms)
  else
    For I := 0 to Len do
     Ints[I] := Random(Randoms);
  For I:= 0 to Len do
    SortInts[i] := Ints[I];
  Time := GetSystemTime;
  MySort(SortInts);
  Time := GetSystemTime - Time;
{  For I := 0 to high(SortInts) do
   Writeln(inttostr(SortInts[I]));  }
  Writeln(IntToStr(Time) + ' msec - Count sort!');
  For I:= 0 to Len do
    SortInts[i] := Ints[I];
  J := GetDigitsArray(SortInts);
  Time := GetSystemTime;
  RadixSort(SortInts,J, Negatives);
  Time := GetSystemTime - Time;
  Writeln(IntToStr(Time) + ' msec - Radix sort!');
  For I:= 0 to Len do
    SortInts[i] := Ints[I];
  Time := GetSystemTime;
  QuickSort(SortInts,0,Len);
  Time := GetSystemTime - Time;
  Writeln(IntToStr(Time) + ' msec - Quick sort!');
  
end.

From: King of Knives
Ben! Your last 3 posts have ended with a ";)"!!!



Roflcopter :D

–Useful post here–
Radixsort looks like a fast way of sorting :D If I'm getting it right, this could be converted to a script that can sort words alphabetically? That'd be cool :p But for no use :D

(Only 4 smileys in my post :D 5 Now)

-Knives

Actually, six ;)

@mastaraymond your comparison method is not very accurate. CountSort's efficacy is based on the array size vs. allocation costs. Therefore in arrays smaller than, say 4000, quicksort is always faster. In fact, CountSort seems to have a base time of 300ms in scar. Radixsort is [almost] never faster than quicksort

Successfully compiled
Random Numbers took on average 44.55ms
QuickSort took on average 418.75ms
RadixSort took on average 1097.6ms
CountSort took on average 468.75ms
Successfully executed

procedure QuickSort(var arr: TIntegerArray; s, e: integer);
var
  cs, ce: Integer;
  pivot, swap: Variant;
begin
  cs:= s;
  ce:= e;
  pivot:= arr[(s + e) / 2];
  repeat
    while arr[cs] > pivot do cs:= cs + 1;
    while arr[ce] < pivot do ce:= ce - 1;
    if cs <= ce then
    begin
      swap:= arr[cs];
      arr[cs]:= arr[ce];
      arr[ce]:= swap;
      cs:= cs + 1;
      ce:= ce - 1;
    end;
  until cs > ce;
  if ce > s then QuickSort(arr, s, ce);
  if cs < e then QuickSort(arr, cs, e);
end;

Const
  ArrayLength = 9999; //The length of the input array
  Negatives = True; //Put in Negative numbers?
  Randoms = 9999; // The random?






  Radix = 10;  //I can't really explain.. Radix 10 is used the most.. It stands for 0,1,2,3,4,5,6,7,8,9.. And if your using negative numbers to, its -9..9

Procedure RadixSort(Integers : TIntegerArray; Digits : Integer; Negative : Boolean);
var
  Dump : Array[-Radix + 1..Radix-1] of TIntegerArray; //We store them temporary here
  Counts : Array[-Radix + 1..Radix-1] of Integer; //Counts, for the length of the Dump
  Len,Divider,I,II,III,Temporary,Counter : Integer;
  RadixMax,RadixMin : integer;
begin
  Divider := 1; //We use this, to sort all the digits time by time ;).
  Len := High(Integers);
  if Negative then
    RadixMin := -Radix + 1
  else
    RadixMin := 0;
  RadixMax := Radix - 1;
  For I := RadixMin to RadixMax do
    SetLength(Dump[i],Len + 1);
  For I := 1 to Digits do //Digits!
  begin;
    For II := RadixMin to RadixMax do
      Counts[II] := -1; //Reset the counts
    For II := 0 to Len do
    begin;
      Temporary := (Integers[II] div Divider) mod Radix // We get the single digit of the number..
      Counts[Temporary] := Counts[Temporary] + 1; //Increase the Counts ;)
      Dump[Temporary][Counts[Temporary]] := Integers[II]; //Store the whole number in in its own digit 'dump', 0 to Radix - 1.. E.G. : Dump[0][0] := Integers[II];
    end;
    Counter := -1;
    For II := RadixMin to RadixMax do
      For III := 0 to  Counts[II] do
      begin;
        Counter := Counter + 1;
        Integers[Counter] := Dump[II][III]; //Place back the orignal var, "Integers"
      end;
    Divider := Divider * Radix; //So that we go to the next Digit
  end;
end;

Procedure MySort(var Integers : TIntegerArray);
var
  Counts : Array of Integer;
  Min, Max : Integer;
  I,II,Len,CountOr : Integer;
begin;
  Len := High(integers);
  Max := Integers[0];
  Min := Integers[0];
  For I := 1 to Len do
  begin;
    if Integers[i] < Min then
      Min := Integers[i]
    else if Integers[i] > max then
      Max := Integers[i];
  end;
  CountOr := 0;
  if Min < 0 then
  begin;
    Min := -Min;
    Max := Min  + Max;
    SetLength(Counts, Max + 1);
    For I := 0 to Len do
      Inc(Counts[Integers[i] + Min]);
    For I := 0 to Max do
      For II := 1 to Counts[i] do
      begin;
        Integers[CountOr] := I - Min;
        CountOr := CountOr + 1;
      end;
  end else
  begin;
    SetLength(Counts,Max +1 );
    For I := 0 To Len do
      Inc(Counts[INtegers[i]])
    For I := Min to Max do
      For II := 1 to Counts[i] do
      begin;
        Integers[CountOr] := I;
        CountOr := CountOr + 1;
      end;
  end;
end;

Function GetDigits( Num  : Integer):Integer;
begin;
  if Num = 0 then Result := 1;
  Num := iAbs(Num);
  While Num > 0 do
  begin;
    Result := Result + 1;
    Num := Num div 10;
  end;
end;

Function GetDigitsArray ( Ints : TIntegerArray) : Integer;
var
  C,I : Integer;
  Len : Integer;
begin;
  Len := High(Ints);
  if Len < 0 then Exit;
  C := 1;
  For I := 0 to Len do
    if (Ints[i] >= C) or (Ints[i] <= -C) then
    begin;
      C := C * 10;
      Dec(I);
    end;
  Result := GetDigits(C - 1);
end;

var
  ints: TIntegerArray;
  c, i, t, runs, size, arrt: integer;
begin
  size:= 50;
  runs:= 20;
  SetLength(ints, size);
  size:= size - 1;
  arrt:= GetSystemTime;
  for c:= 1 to runs do
    for i:= 0 to size do
      ints[i]:= random(50000)-25000;
  arrt:= GetSystemTime - arrt;
  Writeln('Random Numbers took on average ' + FloatToStr(arrt/runs) + 'ms');
  t:= GetSystemTime;
  for c:= 1 to runs do
  begin
    for i:= 0 to size do
      ints[i]:= random(50000)-25000;
    QuickSort(ints,0,size);
  end;
  t:= GetSystemTime - t - arrt;
  Writeln('QuickSort took on average ' + FloatToStr(t/runs) + 'ms');
  t:= GetSystemTime;
  for c:= 1 to runs do
  begin
    for i:= 0 to size do
      ints[i]:= random(50000)-25000;
    RadixSort(ints,GetDigitsArray(ints),Negatives);
  end;
  t:= GetSystemTime - t - arrt;
  Writeln('RadixSort took on average ' + FloatToStr(t/runs) + 'ms');
  t:= GetSystemTime;
  for c:= 1 to runs do
  begin
    for i:= 0 to size do
      ints[i]:= random(50000)-25000;
    MySort(ints);
  end;
  t:= GetSystemTime - t - arrt;
  Writeln('CountSort took on average ' + FloatToStr(t/runs) + 'ms');
end.

I had to do all this crap on the AP Comp.Sci. exam, I'm pretty sure I know what I'm talking about ;)

From: BenLand100
Actually, six ;)

@mastaraymond your comparison method is not very accurate. CountSort's efficacy is based on the array size vs. allocation costs. Therefore in arrays smaller than, say 4000, quicksort is always faster. In fact, CountSort seems to have a base time of 300ms in scar. Radixsort is [almost] never faster than quicksort

Successfully compiled
Random Numbers took on average 44.55ms
QuickSort took on average 418.75ms
RadixSort took on average 1097.6ms
CountSort took on average 468.75ms
Successfully executed

I had to do all this crap on the AP Comp.Sci. exam, I'm pretty sure I know what I'm talking about ;)

You say like the same i already said in my post… ;)

"Although CountSort takes some more memory, its a quite effective algorithm for array's with small numbers.. "

When you compare small numbers, CountSort will beat everything.. But when you make those biggie random numbers, yes, it will take loads of memory. But, in scar, i never use those big numbers.. So i guess im set with CountSort, in some cases.. But ofcourse, looking to the actual Algorithm, Quicksort will win out of those 3.. Because its good overall, but if we look at special circumstances..

( I don't like recursion ^^). I bet its possible to make a non-recursion version of quicksort? Will probably be not as effective, but i just want to see it. :spot:

~Raymond

Dudes, I win:

program New;
var lol : TIntegerArray;
procedure Bogo(var ints : tintegerarray);
var
  a, i : integer;
begin
  while(true) do
  begin
    a := random(high(ints)*high(ints));
    for i := 0 to a do
      swap(ints[random(high(ints)+1)], ints[random(high(ints)+1)]);
    a := 0;
    for i := 0 to high(ints) do
      if (ints[i] > a) then
        a := ints[i];
    if a = ints[high(ints)] then exit;
  end;
end;
begin
lol := [2, 1, 3];
bogo(lol);
end.

It has extremely changing prestations, but sometimes, it'll sort a 20000 integer big array within 50ms :D Whatever, sometimes, it takes weeks to do a three integer big array :(

From: mastaraymond
( I don't like recursion ^^). I bet its possible to make a non-recursion version of quicksort? Will probably be not as effective, but i just want to see it. :spot:

Just do the same thing that you do to any recursive method to make it non recursive… add a stack :p It might actually be faster in Scar considering that scar is interpreted and function calls might take longer… Anyway, I don't want to write it because its pointless to make something non-recursive when its easier to make it recursive… Just for kicks, my algorithm for the special case of already sorted arrays can't be beaten by any algorithm known to man (and most demons):

procedure AlreadySorted(var arr: TIntegerArray);
begin
end;

;)