Radix sort

Lsd sort that uses linked lists that are implemented by programmer. Create an avail list,& take from the data read in. Not arithmetic on pointers. program must be flexible for 8 digits.
ChloemorganAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

My name is MudSystems EngineerCommented:
???
0
ChloemorganAuthor Commented:
I didn't get any comment from WhatBoy except the following???
i have to  write a program using LSD sort (radixsort). Need to create available list(mem Management). the program will use linked lists , queues. For mem. Management , i have to get a node from available pool then after using the list the memory (node ) goes back to a pool called Avail.
0
ChloemorganAuthor Commented:
i think a person would use a record to start with??? the after all numbers would be read in and the radixsort would find the least significant digit of the number and place it in the proper location in a queue. I think i would need 9 queues?
0
Amazon Web Services

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

ChloemorganAuthor Commented:
Adjusted points to 400
0
My name is MudSystems EngineerCommented:
http://www.cubic.org/~submissive/sourcerer/radix.htm

There i got this code in C++

/*
From: Andre Reinald <Andre.Reinald@vtcom.fr>
To: submissive@cubic.org

I though you might be intersted by some modifications I brought to your
code in order to improve legibility and slightly speed.

Well, my source is commented and I often wrote 4 lines where you had
only one, but the generated code is smaller and it gives more
opportunity to check intermediate steps while debugging.

By the way, I did so on a PowerMac with CodeWarrior compiler, so your
source is really portable.
*/

#include <stdlib.h>
#include <assert.h>

// complicated expression better fits as macro (or inline in C++)
#define ByteOf(x) (((x) >> bitsOffset) & 0xff)

typedef unsigned long ulong;

// replaced byte with bitsOffset to avoid *8 operation in loop
static void radix (short bitsOffset, ulong N, ulong *source, ulong *dest)
{
// suppressed the need for index as it is reported in count
        ulong count[256];
// added temp variables to simplify writing, understanding and compiler optimization job
// most of them will be allocated as registers
        ulong *cp, *sp, s, c, i;

// faster than MemSet
        cp = count;
        for (i = 256; i > 0; --i, ++cp)
                *cp = 0;

// count occurences of every byte value
        sp = source;
        for (i = N; i > 0; --i, ++sp) {
                cp = count + ByteOf (*sp);
                ++(*cp);
        }

// transform count into index by summing elements and storing into same array
        s = 0;
        cp = count;
        for (i = 256; i > 0; --i, ++cp) {
                c = *cp;
                *cp = s;
                s += c;
        }

// fill dest with the right values in the right place
        sp = source;
        for (i = N; i > 0; --i, ++sp) {
                s = *sp;
                cp = count + ByteOf (s);
                dest[*cp] = s;
                ++(*cp);
        }
}

static void radix_sort (ulong *source, ulong N)
{
// allocate heap memory to avoid the need of additional parameter
        ulong *temp = malloc (N * sizeof (ulong));
        assert (temp != NULL);

        radix (0, N, source, temp);
        radix (8, N, temp, source);
        radix (16, N, source, temp);
        radix (24, N, temp, source);

        free (temp);
}

static void make_random (ulong *data, ulong N)
{
        for ( ; N > 0; --N, ++data)
                *data = rand () | (rand () << 16);
}

static void check_order (ulong *data, ulong N)
{
// only signal errors if any (should not be)
        --N;
        for ( ; N > 0; --N, ++data)
                assert (data[0] <= data[1]);
}

// test for big number of elements
static void test_radix (ulong N)
{
        ulong *data = malloc (N * sizeof (ulong));
        assert (data != NULL);

        make_random (data, N);
        radix_sort (data, N);
        check_order (data, N);

        free (data);
}

void main (void)
{
        test_radix (500000);
}
0
ChloemorganAuthor Commented:
Thanks, but i have to have it in pascal as i can read some of C++ but i'am fairly new to this language and i think i would be for ever trying to figure it out. any ideas ,
0
HypoCommented:
Here's a pice of code I found. It's a bit modifyed from the original... (I had to make it longint compatible)

I Hope you can use it..

Program SortStuff;

Uses Crt, Dos;

const DataSize = 50;

Type
    AType = Array [1..DataSize] of Longint;
    Ptr   = ^Node;
    Node  = Record
          Info : Longint;
          Link : Ptr;
        end;
    LType = Array [0..15] of Ptr;

Var Ran     : AType;

Procedure ReadData(Var A : AType);
Var I : Integer;
begin
  For I := 1 to DataSize do A[I] := Longint(Random(65535))*Random(32767);
end;

Procedure WriteArray(A : AType);
Var I : Integer;
begin
  For I := 1 to DataSize do
    Write (A [I] : 16);
  Writeln;
end;

Procedure Insert(Var L : LType; Number : Longint; LN : Integer);
Var
  P, Q : Ptr;
begin
  New(P);
  P^.Info := Number;
  P^.Link := Nil;
  Q := L[LN];
  if Q = Nil then
    L[LN] := P
  else begin
   While Q^.Link <> Nil do Q := Q^.Link;
    Q^.Link := P;
   end;
end;


Procedure Refill (Var A : AType; Var L : LType);
Var
  I,J  : integer;
  P    : Ptr;
begin
  J := 1;
  For I := 0 to 15 do begin
    P := L[I];
    While P <> Nil do begin
      A[J] := P^.Info;
      P := P^.Link;
      Inc(J);
    end;
  end;
  For I := 0 to 15 do L [I] := Nil;
end;

Procedure RadixSort (Var A : AType);
Var
  L        : LType;
  I,ListNo : integer;
  RadixNo,
  Number   : Longint;
begin
  For I := 0 to 15 do L[I] := Nil;
  RadixNo := 0;
  While RadixNo <= 28 do begin
    I := 1;
    While I <= DataSize do begin
      Number := A[I];
      ListNo := Number div (1 shl RadixNo) and 15;
      Insert (L, Number, ListNo);
      inc(I);
    end;
    Refill (A, L);
    Inc(RadixNo,4);
  end;
end;

begin
    Randomize;
    clrscr;
    ReadData (Ran);
    Writeln ('Unsorted : ');
    WriteArray (Ran);
    Readkey;
    RadixSort (Ran);
    Writeln ('Sorted   : ');
    WriteArray(Ran);
    Readkey;
end.


0
ChloemorganAuthor Commented:
This is pretty close to what i'am looking for. A few things i don't understand , do have this program commented ? What is the this
Number div (1 shl RadixNo) and 15;
Is it some kind of a pascal operator? Maybe a shift of move??
     
0
vikiingCommented:
"shl" and "shr" are "shift left" and "shift right" Pascal operators respectively; they shift a number left or right the specified number of times:

(1 shl RadixNo)  moves that binary 1 to the left, as many times as RadixNo indicates.

div operator is the integer division.

Finally, an and/or/not/xor operations applied on integer quantities work directly in a binary basis. Thus, "30 and 3" yields 2, because

30 (in binary)  111110
 3 (in binary)  000011

A logic AND applied to both values gives, as a result, the only bit both values have in common: 000010, this is, decimal 2. (0 and "any value" ==> 0  , 1 and 1 ==> 1)


0
ChloemorganAuthor Commented:
thanks, but i see a problem, i'anm not allowed to use arithmetic on ptr's. I have to creat my own mem. management, not all sure what this means. ??
avail:=link[p]  etc.
0
ChloemorganAuthor Commented:
create a linked list using two 1darrays ; one for data - for links;
create linked list using array for memory management - not
pascal pointer facilities; ente n numbers into the list; take the numbers one at a time out of the list and return node to available
memory; but numbers thru radix sort  then put the numbers back
into the linked list ( better yet use linked list of Queues)
0
My name is MudSystems EngineerCommented:
>>i'am not allowed to use arithmetic on ptr's...

Yes you can... unless this is a homework??? and the teacher of yours is a dork...
0
ChloemorganAuthor Commented:
Not home work , but the person who is teaching me this stuff is a dork!
I think he has got me more confused then a fox in a chicken house.
0
My name is MudSystems EngineerCommented:
Guess i could have helped you, but the main reaseon is that i don't undersatand what the heck you want... probably becouse i need an example and/or my poor english...
0
My name is MudSystems EngineerCommented:
>>...create linked list using array...

This for example... ??? ??? ??? if you want a linked list [which are created on the fly] why do you need an array???

I can tell you how to use a linked list, by the way if you plan to used in a sort algorithm it is better if you do a double linked list... and that too i know how... it just the same thing... guess...
0
ChloemorganAuthor Commented:
wo 1 d arrays - one holds the data the other holds the
links to the used nodes and the ones not used; avail keeps track
of the next available memory location;
ie  ex;   avail = 3 -3 points to 4 and points to nil (list of avail memory)
every things else is used;
yes please send me
Does this help at all, i think the what is mentioned above will work. The hell with these arrays
0
My name is MudSystems EngineerCommented:
Maybe this can help you out... i guess, is a bubble short with double link...

Program BubbleSort;
Uses
  Crt;
Type
  PointerToList = ^List;
  List = Record
    Value: Integer;
    PrevItem: PointerToList;
    NextItem: PointerToList;
  End;
Var
  Start,Previous,Current,Finish: PointerToList;
  mValue: Integer;

{ Function to count the number of items in the list.}
Function Count_Items: Integer;
Var
  I: Integer;
Begin
  Current:=Start;
  I:=0;
  While Current <> Nil Do
    Begin
      I:=I+1;
      Current:=Current^.NextItem;
    End;
  Count_Items:=I;
End;

{ Procedure to add items into the list }
Procedure AddItem (Newvalue: Integer);
Begin
  {Check If this is the first time the structure is going to be created}
  If Current = NIL Then
    Begin
      New(Current); {Get memory for the data}
      With Current^ do  {Fill in the data}
        Begin
          Value:=NewValue;
          NextItem:=NIL; {Since there are any more Up this points NIL}
          PrevItem:=NIL  {Since there are any more Down this points NIL}
        End;
      Start:=Current;
      Finish:=Current
    End
  Else  {Now this is not the first time}
    Begin
      New(Finish);
      Finish^.PrevItem:=Current; {Current <- Finish}
      Finish^.NextItem:=NIL;     {Finish -> Nil}
      Current^.NextItem:=Finish; {Current -> Finish}
      Current:=Finish;       {Current:=Finish}
      With Current^ do  {Fill in the data}
        Begin
          Value:=NewValue;
        End
    End
End;

{ Procedure to sort the list using the bubble sort method }
Procedure Sort_List;
Var
  Index1,Index2: Integer;
  MaxNum: Integer;

  Procedure ChangePlaces(Var Prev,Curr: PointerToList);
  Var
    Temp: Integer;
  Begin
    Temp:=Prev^.Value;
    Prev^.Value:=Curr^.Value;
    Curr^.Value:=Temp;
  End;

Begin
  MaxNum:=Count_Items;
  Previous:=Start;
  Current:=Finish;
  For Index1:=1 To MaxNum-1 Do
    Begin
      For Index2:=MaxNum DownTo Index1+1 Do
        Begin
          If Previous^.Value > Current^.Value Then
            ChangePlaces(Previous,Current);
          Current:=Current^.PrevItem;
        End;
      Previous:=Previous^.NextItem;
      Current:=Finish;
    End
End;

{ Procedure to print the list }
Procedure Print_List;
Begin
  Current:=Start;
  While Current <> Nil Do
    Begin
      Write(Current^.Value,'  ');
      Current:=Current^.NextItem;
    End
End;

Procedure Dispose_All;
Begin
  Current:=Start;
  While Current^.NextItem <> Nil Do
    Begin
      Previous:=Current;
      Current:=Current^.NextItem;
      If Previous <> Nil Then
        Dispose(Previous);
    End;
  Dispose(Current);
End;

{ The main program }
Begin
  ClrScr;
  Start := Nil;
  { Adding items to the list }
  Repeat
    Write (' Enter a Number : ');
    Readln (mValue);
    If mValue <> 0 Then
      AddItem (mValue);
  Until mValue = 0;
  { Sorting the list }
  Sort_List;
  { Printing the list }
  Print_List;
  Dispose_All;
End.
0
ChloemorganAuthor Commented:
I love it... wow! The only think is i need it to except a 8 digit number, i changed value to longint but it didn't seemed to help.
0
My name is MudSystems EngineerCommented:
>>...The only think is i need it to except a 8...


An Integer is 16 bits long...
A LongInt is 32 bits long...
A Byte is 8 bits long...
A ShortInt is 8 bits long...
A Char is 8 bits long...
0
ChloemorganAuthor Commented:
Yes, i just didn't all my integer.. to longint. Program is excellent. Your the best. Do i just click on this accept comment as answer.
0
My name is MudSystems EngineerCommented:
I guess...
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
ChloemorganAuthor Commented:
thanks so much for all your work ,it is greatly appreciated. Now i will sit down and do a walkthrough and learn this so i can teach others. Once again thanks.
0
ChloemorganAuthor Commented:
excellent help. I would recommend whatboy to everyone who needs help.
0
My name is MudSystems EngineerCommented:
Would you be bother if i ask you a simple question that is kind like bothering me???

are you a male or female???...
0
My name is MudSystems EngineerCommented:
Thanks, glad to help.
0
ChloemorganAuthor Commented:
female
0
ChloemorganAuthor Commented:
You are very polite , i'am glad i have met you. We will have to chat sometime.
0
My name is MudSystems EngineerCommented:
oh, i might knew that, guess that's what was bothering... by the way... i appreciate the posible recomendations, but no thanks, here there are a lot of others members that might have a better solution than mine, and i might say that that will put me in a position i don't want, like i say i'm glad to help you out, and flatter, but that's what we do here help each other...
0
My name is MudSystems EngineerCommented:
if you get confused by:
  oh, i might knew that, guess that's what was bothering...

then you must ignored, please... is a thing i can't explain...
0
My name is MudSystems EngineerCommented:
oh damn it, i think i'm getting my self in a weird position... oh well guess is my english, well bye, see you later [or talk to you later.... maybe type to you later]...
0
ChloemorganAuthor Commented:
great, have to go to bed soon as it is 2:30 in the morning here.  Canada
0
My name is MudSystems EngineerCommented:
Same here... Mexico...

pleasant dreams... I'm "Working"...
0
ChloemorganAuthor Commented:
okay, don't work to hard
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Pascal

From novice to tech pro — start learning today.