Results 1 to 20 of 20

Thread: RadixSort, a fast way of sorting array's!

  1. #1
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default RadixSort, a fast way of sorting array's!

    Well, i made some functions related to Radix Sort.. Its quite effective way of sorting things..
    Try to understand it ^^
    SCAR Code:
    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.
    Verrekte Koekwous

  2. #2
    Join Date
    Feb 2007
    Location
    Het ademt zwaar en moedeloos vannacht.
    Posts
    7,211
    Mentioned
    26 Post(s)
    Quoted
    72 Post(s)

    Default

    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? ^^
    I made a new script, check it out!.

  3. #3
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by Markus View Post
    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..
    Verrekte Koekwous

  4. #4
    Join Date
    Feb 2006
    Location
    Berkeley, CA
    Posts
    1,837
    Mentioned
    52 Post(s)
    Quoted
    60 Post(s)

    Default

    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...

    SCAR Code:
    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.

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

  5. #5
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by BenLand100 View Post
    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..
    Verrekte Koekwous

  6. #6
    Join Date
    Dec 2006
    Location
    Banville
    Posts
    3,914
    Mentioned
    12 Post(s)
    Quoted
    98 Post(s)

    Default

    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...
    The jealous temper of mankind, ever more disposed to censure than
    to praise the work of others, has constantly made the pursuit of new
    methods and systems no less perilous than the search after unknown
    lands and seas.

  7. #7
    Join Date
    Jun 2006
    Posts
    3,861
    Mentioned
    3 Post(s)
    Quoted
    1 Post(s)

    Default

    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...

  8. #8
    Join Date
    Feb 2006
    Location
    Berkeley, CA
    Posts
    1,837
    Mentioned
    52 Post(s)
    Quoted
    60 Post(s)

    Default

    Quote Originally Posted by mastaraymond View Post
    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:
    Code:
    Successfully compiled
    Random Numbers took on average 12.5ms
    QuickSort took on average 87.5ms
    RadixSort took on average 203.1ms
    Successfully executed
    Quote Originally Posted by R0b0t1 View Post
    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

  9. #9
    Join Date
    Dec 2006
    Location
    Banville
    Posts
    3,914
    Mentioned
    12 Post(s)
    Quoted
    98 Post(s)

    Default

    Wait... You were AROUND back then? Damn! Did you play fetch with a Tyrannosaurus?
    The jealous temper of mankind, ever more disposed to censure than
    to praise the work of others, has constantly made the pursuit of new
    methods and systems no less perilous than the search after unknown
    lands and seas.

  10. #10
    Join Date
    Feb 2006
    Location
    Berkeley, CA
    Posts
    1,837
    Mentioned
    52 Post(s)
    Quoted
    60 Post(s)

    Default

    Quote Originally Posted by R0b0t1 View Post
    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

  11. #11
    Join Date
    Dec 2006
    Location
    Banville
    Posts
    3,914
    Mentioned
    12 Post(s)
    Quoted
    98 Post(s)

    Default

    Oh, those things are still around? Like to get my hands on one...
    The jealous temper of mankind, ever more disposed to censure than
    to praise the work of others, has constantly made the pursuit of new
    methods and systems no less perilous than the search after unknown
    lands and seas.

  12. #12
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default

    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...
    Verrekte Koekwous

  13. #13
    Join Date
    Feb 2006
    Location
    Berkeley, CA
    Posts
    1,837
    Mentioned
    52 Post(s)
    Quoted
    60 Post(s)

    Default

    Quote Originally Posted by mastaraymond View Post
    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...
    Quote Originally Posted by Markus View Post
    Wow, Radixsort, isnt it one of the fastest sorting algorithms around?
    I was responding to that anyway

  14. #14
    Join Date
    Aug 2007
    Posts
    1,404
    Mentioned
    1 Post(s)
    Quoted
    0 Post(s)

    Default

    Ben! Your last 3 posts have ended with a ""!!!
    Quote Originally Posted by 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
    Quote Originally Posted by 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
    Quote Originally Posted by BenLand100
    I was responding to that anyway
    Roflcopter

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

    (Only 4 smileys in my post 5 Now)

    -Knives

  15. #15
    Join Date
    Feb 2007
    Location
    Het ademt zwaar en moedeloos vannacht.
    Posts
    7,211
    Mentioned
    26 Post(s)
    Quoted
    72 Post(s)

    Default

    Hey! I didn't post anything
    I made a new script, check it out!.

  16. #16
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by King of Knives View Post
    Ben! Your last 3 posts have ended with a ""!!!



    Roflcopter

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

    (Only 4 smileys in my post 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:
    SCAR Code:
    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.
    Verrekte Koekwous

  17. #17
    Join Date
    Feb 2006
    Location
    Berkeley, CA
    Posts
    1,837
    Mentioned
    52 Post(s)
    Quoted
    60 Post(s)

    Default

    Quote Originally Posted by King of Knives View Post
    Ben! Your last 3 posts have ended with a ""!!!



    Roflcopter

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

    (Only 4 smileys in my post 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
    Code:
    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

    SCAR Code:
    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

  18. #18
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by BenLand100 View Post
    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
    Code:
    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.

    ~Raymond
    Verrekte Koekwous

  19. #19
    Join Date
    Feb 2007
    Location
    Het ademt zwaar en moedeloos vannacht.
    Posts
    7,211
    Mentioned
    26 Post(s)
    Quoted
    72 Post(s)

    Default

    Dudes, I win:
    SCAR Code:
    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 Whatever, sometimes, it takes weeks to do a three integer big array
    I made a new script, check it out!.

  20. #20
    Join Date
    Feb 2006
    Location
    Berkeley, CA
    Posts
    1,837
    Mentioned
    52 Post(s)
    Quoted
    60 Post(s)

    Default

    Quote Originally Posted by mastaraymond View Post
    ( 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.
    Just do the same thing that you do to any recursive method to make it non recursive... add a stack 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):
    Code:
    procedure AlreadySorted(var arr: TIntegerArray);
    begin
    end;

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Fast Help
    By nhstarter10 in forum OSR Help
    Replies: 2
    Last Post: 12-11-2008, 12:08 AM
  2. Radix Sorting
    By R0b0t1 in forum C/C++ Help and Tutorials
    Replies: 10
    Last Post: 11-08-2008, 01:24 PM
  3. Help fast?!
    By script taker in forum OSR Help
    Replies: 4
    Last Post: 07-27-2008, 04:11 PM
  4. Need Help Fast!
    By xVendettax in forum OSR Help
    Replies: 1
    Last Post: 08-30-2007, 07:26 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •