Array Index Problem in Quick Sort

[shsh_shah]

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

[jslicer]

Remove "hi = arr.Length;" and pass in arr.Length-1 as the hi parameter on your first call to the function.

[shsh_shah]

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.

[jslicer]

I prefer to remove the tail recursion and have a while loop take care of the case where i < hi as such:

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);
}

now, unless you have a massively huge array (say, 2^20 or thereabouts), you shouldn't have any recursive stack overflow issues.

[shsh_shah]

Thanks a million jslicer. It worked for me. You are the star.