C# RSS C# RSS

Array Index Problem in Quick Sort

Please support our C# advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Mar 2007
Posts: 29
Reputation: shsh_shah is an unknown quantity at this point 
Solved Threads: 0
shsh_shah shsh_shah is offline Offline
Light Poster

Array Index Problem in Quick Sort

 
0
  #1
Mar 27th, 2007
Hi,
I have problem when i get an array using I get "Array Index Out of Bound" in QuickS function
C# Syntax (Toggle Plain Text) 
  1. getArray(int [] arr)
  2. for (i = 0; i < arr.Length; i++)
  3.                {
  4.  
  5.                    String val = Console.ReadLine();
  6.                    arr[i] = Convert.ToInt32(val);
  7.                 }
  8.  
  9. public static void quicks(int lo, int hi, int[] arr)
  10.        {
  11.            int i = lo;
  12.            hi = arr.Length;
  13.            int j = hi;
  14.            int pivot;
  15.            pivot = arr[(lo + hi) / 2];
  16.  
  17.            if (lo >= hi)
  18.            {
  19.                return;
  20.            }
  21.            Console.WriteLine(pivot);
  22.  
  23.                do
  24.                {
  25.                    while (arr[i] < pivot)
  26.                    i++;
  27.                    while (arr[j] > pivot) // when it comes here it says Array
  28.                                          //  out of bound problem
  29.                    j--;
  30.  
  31.                    if (i < j)
  32.                    {
  33.                    int temp = a[i];
  34.                    a[i] = a[j];
  35.                    a[j] = temp;
  36.                    }
  37.  
  38.            } while(i < j ); // end of do condition
  39.  
  40.            if (lo < j) quicks(lo, j,arr);
  41.            if (i < hi) quicks(i, hi,arr);
Please help me in correcting quicksort function
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 2
Reputation: jslicer is an unknown quantity at this point 
Solved Threads: 0
jslicer jslicer is offline Offline
Newbie Poster

Re: Array Index Problem in Quick Sort

 
0
  #2
Mar 27th, 2007
Remove "hi = arr.Length;" and pass in arr.Length-1 as the hi parameter on your first call to the function.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 29
Reputation: shsh_shah is an unknown quantity at this point 
Solved Threads: 0
shsh_shah shsh_shah is offline Offline
Light Poster

Re: Array Index Problem in Quick Sort

 
0
  #3
Mar 27th, 2007
•
•
•
•
Originally Posted by jslicer View Post
Remove "hi = arr.Length;" and pass in arr.Length-1 as the hi parameter on your first call to the function.
Hi Thanks for help i have changed small bit code

C# Syntax (Toggle Plain Text) 
  1. public static void quicks(int [] arr,int lo, int hi)
  2.         {
  3.             int i = lo;
  4.             int temp;
  5.             int j = hi;
  6.             int pivot;
  7.             pivot = arr[(lo + hi) / 2];
  8.  
  9.             if (i >= j)
  10.             {
  11.                 return;
  12.             }
  13.  
  14.                 while (i < j)
  15.                 {
  16.                     while (i<j && arr[i] < pivot)
  17.                     {
  18.                         i++;
  19.                     }
  20.                     while (i<j && arr[j] >= pivot)
  21.                     {
  22.                         j--;
  23.                     }
  24.  
  25.                     if (i < j)
  26.                     {
  27.                     temp = a[i];
  28.                     a[i] = a[j];
  29.                     a[j] = temp;
  30.                     }
  31.  
  32.                 }  // end of do condition
  33.  
  34.             if (j < i)
  35.             {
  36.                 temp = j;
  37.                 j = i;
  38.                 i = temp;
  39.             }
  40.  
  41.  // i took these two below recursive functions from web and i am also getting problem now in below functions Error="System.StackOverFlowException"
  42. // Can you help me in this and also if tell me what they do
  43.           if (lo<j)  quicks(arr,lo, j);
  44.           if(i<hi)   quicks(arr,j,hi);
  45.  
  46.  
  47.         } // end of QuickS
  48.  
  49.         public static void quicks(int[] arr)
  50.         {
  51.             quicks(arr, 0, arr.Length - 1);
  52.         }


Thanks for quick response. Plz help small bit more.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 2
Reputation: jslicer is an unknown quantity at this point 
Solved Threads: 0
jslicer jslicer is offline Offline
Newbie Poster

Re: Array Index Problem in Quick Sort

 
0
  #4
Mar 27th, 2007
I prefer to remove the tail recursion and have a while loop take care of the case where i < hi as such:

[html]private static void quicks(int [] arr, int lo, int hi)
{
int i;

do
{
i = lo;

int j = hi;
int pivot = arr[(lo + hi) / 2];

do
{
while (arr[i] < pivot)
{
i++;
}
while (arr[j] > pivot)
{
j--;
}
if (i <= j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
} while (i <= j);
if (lo < j)
{
quicks(arr, lo, j);
}
lo = i;
} while (i < hi);
}[/html]
now, unless you have a massively huge array (say, 2^20 or thereabouts), you shouldn't have any recursive stack overflow issues.
Last edited by jslicer; Mar 27th, 2007 at 1:30 pm. Reason: reformatting
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2007
Posts: 29
Reputation: shsh_shah is an unknown quantity at this point 
Solved Threads: 0
shsh_shah shsh_shah is offline Offline
Light Poster

Re: Array Index Problem in Quick Sort

 
0
  #5
Mar 28th, 2007
Thanks a million jslicer. It worked for me. You are the star.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C# Forum
Thread Tools Search this Thread



.net access algorithm array barchart bitmap box broadcast c# check checkbox client combobox control conversion csharp custom cyclethruopenforms data database datagrid datagridview dataset date/time datetime degrees development draganddrop drawing encryption enum event excel file filename finalyearproject form format forms function gdi+ getoutlookcontactusinfcsvfile gis globalization gtk httpwebrequest image index input install installer java label list listbox mandelbrot math mono mouseclick mysql operator panel path photoshop picturebox pixelinversion post programming radians regex remoting richtextbox save server silverlight sleep socket sql sql-server statistics stream string table text textbox thread time timer timespan update usercontrol users validate validation visualstudio webbrowser windows winforms wpf xml
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC