Problem with sorting strings using Radix Sort

[gamer1127]

Hello. I'm having a problem with the codes I used to sort the strings from the text file using Radix Sort. I always get the IndexOutOfRange exception.

Here is the code that causes the exception:


int N = arrayOfLastNames.Length;
for (int a = 0; a < arrayOfLastNames.Length; a++)
{
int W = arrayOfLastNames[a].Length;
Console.WriteLine("{0}", W);

string[] temp = new string[arrayOfLastNames.Length];
for (int d = W - 1; d >= 0; d--)
{
int[] count = new int[50];
for (int i = 0; i < N; i++)
{
count[arrayOfLastNames[i][d] + 1]++; //the part that causes the exception
}
for (int k = 1; k < 256; k++)
{
count[k] += count[k - 1];
}
for (int i = 0; i < N; i++)
{
temp[count[arrayOfLastNames[i][d]]++] = arrayOfLastNames[i];
}
for (int i = 0; i < N; i++)
{
arrayOfLastNames[i] = temp[i];

Console.WriteLine("{0}", arrayOfLastNames[i]);
}
}
}


Can someone please help me? I really need to finish this before saturday because it's the passing date. I have exams tomorrow until this coming monday. If I solve this problem today I'll be able to finish it until tomorrow because i'll be doing one more procedure tomorrow and that's the binary search. So please help me.

[monalin]

Try running it through a debugger and finding out where its throwing the error. Post the stack trace here and i'll show you what to do with it. Then next time you have this problem you can solve it for yourself :)

[gamer1127]

Uhm..Is that the call stack? If that's it here it is:

> VehicleRegistration.exe!VehicleRegistration.Program.SortByLastName(ref string[] arrayOfLastNames = {Dimensions:[30]}, ref string[] arrayOfFirstNames = {Dimensions:[30]}, ref string[] arrayOfPlateNum = {Dimensions:[30]}, ref string[] arrayOfType = {Dimensions:[30]}, ref string[] arrayOfYear = {Dimensions:[30]}) Line 297 C#
VehicleRegistration.exe!VehicleRegistration.Program.Main(string[] args = {Dimensions:[0]}) Line 47 + 0x17 bytes C#
[External Code]

[monalin]

No stack trace is when an error is thrown. Call stack is a little different.

Stack Trace


[Exception: Exception of type 'System.Exception' was thrown.]
ContestManager.CacheFetchContest(Int32 contestId) in c:\Inetpub\www\picks\App_Code\Contest\ContestManager.cs:40
ContestManager.GetContest(Int32 contestId) in c:\Inetpub\www\picks\App_Code\Contest\ContestManager.cs:862
Control.Page_Load(Object sender, EventArgs e) in c:\Inetpub\www\picks\Control.aspx.cs:33
System.Web.Util.CalliHelper.EventArgFunctionCaller(IntPtr fp, Object o, Object t, EventArgs e) +25
System.Web.Util.CalliEventHandlerDelegateProxy.Callback(Object sender, EventArgs e) +42
System.Web.UI.Control.OnLoad(EventArgs e) +132
System.Web.UI.Control.LoadRecursive() +66
System.Web.UI.Page.ProcessRequestMain(Boolean includeStagesBeforeAsyncPoint, Boolean includeStagesAfterAsyncPoint) +2428


You can get the stack trace from the little window that pops up when an exception is thrown.

[gamer1127]

Ah..ok..I found it..


System.IndexOutOfRangeException was unhandled
Message="Index was outside the bounds of the array."
Source="VehicleRegistration"
StackTrace:
at VehicleRegistration.Program.SortByLastName(String[]& arrayOfLastNames, String[]& arrayOfFirstNames, String[]& arrayOfPlateNum, String[]& arrayOfType, String[]& arrayOfYear) in E:\IT111P\Case Problem\Vehicle Registration\VehicleRegistration\VehicleRegistration\Program.cs:line 297
at VehicleRegistration.Program.Main(String[] args) in E:\IT111P\Case Problem\Vehicle Registration\VehicleRegistration\VehicleRegistration\Program.cs:line 47
at System.AppDomain._nExecuteAssembly(Assembly assembly, String[] args)
at System.AppDomain.ExecuteAssembly(String assemblyFile, Evidence assemblySecurity, String[] args)
at Microsoft.VisualStudio.HostingProcess.HostProc.RunUsersAssembly()
at System.Threading.ThreadHelper.ThreadStart_Context(Object state)
at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
at System.Threading.ThreadHelper.ThreadStart()

[monalin]

Ok so according to this stack track your program errored out on line 297.

at VehicleRegistration.Program.SortByLastName(String[]& arrayOfLastNames, String[]& arrayOfFirstNames, String[]& arrayOfPlateNum, String[]& arrayOfType, String[]& arrayOfYear) in E:\IT111P\Case Problem\Vehicle Registration\VehicleRegistration\VehicleRegistration\Program.cs:line 297

And like you said you're getting a "IndexOutOfRangeException" this can only mean one thing, you have lets say 10 items in an array and you're trying to access the 11th item, which doesn't exist.


count[arrayOfLastNames[i][d] + 1]++; //the part that causes the exception


Maybe its the + 1 at the end? Why is that there?

[gamer1127]

count[arrayOfLastNames[i][d] + 1]++; //the part that causes the exception

Maybe its the + 1 at the end? Why is that there?


Originally that is in java code:


count[arrayOfLastNames[i].charAt(d) + 1]++;


I was told to use an indexer so i can use the code in sharp

by the way, I only got the whole code from the net so I just editted and placed some codes that I think is appropriate for the code.

[monalin]

Well part of your problem is this...


int[] count = new int[50];


This array isn't large enough. Where are you getting the value of 50 from. This needs to be the highest ASCII value for a character in the list of names + 1.

[monalin]

If I were you i'd take a look at this.

http://www.codeproject.com/KB/recipes/RadixSort.aspx

I don't think you're current algorithm is right.

[gamer1127]

Do I have to get the ASCII code before using the code in the link you gave me? Because I already tried the code there but before using that I first got their ASCII code before passing the string to the sorter. and the result that I got is not the one I wanted.

[gamer1127]

If I get the ASCII codes first then pass it to the radix sort this is what it shows me:


SHOW DATABASE: SORTING BY LAST NAME

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

97

97

97

110

110

111

111

111

114

115

115

115

117

122

122



What should I do for it to be able to sort strings?

[monalin]

Well i just fixed that version up to work with strings. It's possible to do but you have to switch a few things around.

Instead of passing an array of ints through the function pass an array of strings.
Setting the value to each digit in the number set it to each character's ASCII value.
Make the function work in the reverse order for example. If you have the three names sort them from column 1 to column 6.

B r i a n
C h r i s
A n d r e w
6 5 4 3 2 1

When you reach column 6 exit the sorting function after it finishes sorting that column in SortedArray right before it returns the RadixSortAux.