User Name Password Register
DaniWeb IT Discussion Community
All
What is DaniWeb IT Discussion Community?
You're currently browsing the C# section within the Software Development category of DaniWeb, a massive community of 397,816 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,592 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our C# advertiser:
Views: 2514 | Replies: 4
Reply
Join Date: Mar 2007
Posts: 25
Reputation: shsh_shah is an unknown quantity at this point 
Rep Power: 2
Solved Threads: 0
shsh_shah shsh_shah is offline Offline
Light Poster

Array Index Problem in Quick Sort

  #1  
Mar 27th, 2007
Hi,
I have problem when i get an array using I get "Array Index Out of Bound" in QuickS function
getArray(int [] arr)
for (i = 0; i < arr.Length; i++)
               {

                   String val = Console.ReadLine();
                   arr[i] = Convert.ToInt32(val);
                }

public static void quicks(int lo, int hi, int[] arr)
       {
           int i = lo;
           hi = arr.Length;
           int j = hi;
           int pivot;
           pivot = arr[(lo + hi) / 2];

           if (lo >= hi)
           {
               return;
           }
           Console.WriteLine(pivot);

               do
               {
                   while (arr[i] < pivot)
                   i++;
                   while (arr[j] > pivot) // when it comes here it says Array
                                         //  out of bound problem
                   j--;

                   if (i < j)
                   {
                   int temp = a[i];
                   a[i] = a[j];
                   a[j] = temp;
                   }

           } while(i < j ); // end of do condition

           if (lo < j) quicks(lo, j,arr);
           if (i < hi) quicks(i, hi,arr);

Please help me in correcting quicksort function
AddThis Social Bookmark Button
Reply With Quote  
Join Date: Mar 2007
Posts: 2
Reputation: jslicer is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 0
jslicer jslicer is offline Offline
Newbie Poster

Re: Array Index Problem in Quick Sort

  #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  
Join Date: Mar 2007
Posts: 25
Reputation: shsh_shah is an unknown quantity at this point 
Rep Power: 2
Solved Threads: 0
shsh_shah shsh_shah is offline Offline
Light Poster

Re: Array Index Problem in Quick Sort

  #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

public static void quicks(int [] arr,int lo, int hi)
        {
            int i = lo;
            int temp;
            int j = hi;
            int pivot;
            pivot = arr[(lo + hi) / 2];

            if (i >= j)
            {
                return;
            }

                while (i < j)
                {
                    while (i<j && arr[i] < pivot)
                    {
                        i++;
                    }
                    while (i<j && arr[j] >= pivot)
                    {
                        j--;
                    }
                    
                    if (i < j)
                    {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    }
                
                }  // end of do condition

            if (j < i)
            {
                temp = j;
                j = i;
                i = temp;
            }
          
 // i took these two below recursive functions from web and i am also getting problem now in below functions Error="System.StackOverFlowException"
// Can you help me in this and also if tell me what they do
          if (lo<j)  quicks(arr,lo, j);
          if(i<hi)   quicks(arr,j,hi);


        } // end of QuickS

        public static void quicks(int[] arr)
        {
            quicks(arr, 0, arr.Length - 1);
        }


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

Re: Array Index Problem in Quick Sort

  #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 12:30 pm. Reason: reformatting
Reply With Quote  
Join Date: Mar 2007
Posts: 25
Reputation: shsh_shah is an unknown quantity at this point 
Rep Power: 2
Solved Threads: 0
shsh_shah shsh_shah is offline Offline
Light Poster

Re: Array Index Problem in Quick Sort

  #5  
Mar 28th, 2007
Thanks a million jslicer. It worked for me. You are the star.
Reply With Quote  
Reply

Only community members can participate in forum threads. You must register or log in to contribute.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

 

DaniWeb C# Marketplace
Thread Tools Display Modes

Similar Threads
Other Threads in the C# Forum

All times are GMT -4. The time now is 6:36 am.
Forum system based on vBulletin Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
©2003 - 2008 DaniWeb® LLC