[R] what is wrong with my quicksort?
Mark Leeds
markleeds2 at gmail.com
Sun Sep 4 21:53:31 CEST 2011
Hi: I sent this yesterday but it must be out there in hyperspace
somewhere because
it never appeared on the R-list. Also, I had to look quicksort up
because it's been too long.
Anyway, your code looks similar to the java code at
http://www.algolist.net/Algorithms/Sorting/Quicksort.
and I show it below.
The difference is that you are calling partition recursively while the
code below
calls quicksort recursively. that probably makes a difference but I
didn't test it.
hopefully that's the problem. good luck.
# quicksort Java code
#================================================================
int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
return i;
}
void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
On Sun, Sep 4, 2011 at 7:18 AM, warc <conny-clauss at gmx.de> wrote:
> the error message I get is:
>
> Error in while (x[j] >= pivot) { : Argument has length 0
>
> so either pivot or x[j] is NULL.
> and it somestimes happens the first time the program enters the recursion,
> sometimes the 6. or anywhere inbetween.
>
>
>
> jholtman wrote:
>>
>> have you tried to debug it yourself. All you said is that 'it went
>> wrong'. that is not a very clear statement of the problem. If I were to
>> start looking at it, I would put some print statements in it to see what
>> is happening on eachpath and with each set of data. Have you tried this?
>>
>> Sent from my iPad
>>
>> On Sep 3, 2011, at 21:51, warc <conny-clauss at gmx.de> wrote:
>>
>>> Hey guys,
>>> I tried to program quicksort like this but somethings wrong.
>>>
>>> please help
>>>
>>>
>>>
>>>> partition <- function(x, links, rechts){
>>>>
>>>> i <- links
>>>> j <- rechts
>>>> t <- 0
>>>> pivot <- sample(x[i:j],1)
>>>>
>>>> while(i <= j){
>>>>
>>>> while(x[i] <= pivot){
>>>> i = i+1}
>>>>
>>>> while(x[j] >= pivot){
>>>> j = j-1}
>>>>
>>>> if( i <= j){
>>>>
>>>> t = x[i]
>>>> x[i] = x[j]
>>>> x[j] = t
>>>>
>>>> i=i+1
>>>> j=j-1
>>>>
>>>> }
>>>> print(pivot)
>>>>
>>>>
>>>> }
>>>> #Rekursion
>>>>
>>>> if(links < j){
>>>> partition(x, links, j)}
>>>> if(i < rechts){
>>>> partition(x, i, rechts)}
>>>>
>>>> return(x)
>>>> }
>>>>
>>>>
>>>> quicksort <- function(x){
>>>>
>>>>
>>>>
>>>> partition(x, 1, length(x))
>>>> }
>>>
>>>
>>>
>>> thx
>>>
>>> --
>>> View this message in context:
>>> http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3788681.html
>>> Sent from the R help mailing list archive at Nabble.com.
>>>
>>> ______________________________________________
>>> R-help at r-project.org mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide
>>> http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.
>>
>> ______________________________________________
>> R-help at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide
>> http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
>>
>
>
> --
> View this message in context: http://r.789695.n4.nabble.com/what-is-wrong-with-my-quicksort-tp3788681p3789080.html
> Sent from the R help mailing list archive at Nabble.com.
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>
More information about the R-help
mailing list