Please support our C# advertiser: Programming Forums
Views: 2826 | Replies: 4
 |
•
•
Join Date: Mar 2007
Posts: 25
Reputation: 
Rep Power: 2
Solved Threads: 0
Light Poster
Hi,
I have problem when i get an array using I get "Array Index Out of Bound" in QuickS function
Please help me in correcting quicksort function
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
•
•
Join Date: Mar 2007
Posts: 2
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
Remove "hi = arr.Length;" and pass in arr.Length-1 as the hi parameter on your first call to the function.
•
•
Join Date: Mar 2007
Posts: 25
Reputation:
Rep Power: 2
Solved Threads: 0
Light Poster
•
•
•
•
Originally Posted by jslicer 
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.
•
•
Join Date: Mar 2007
Posts: 2
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
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.
[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
|
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
Linear Mode
