[R] what is wrong with my quicksort?

peter dalgaard pdalgd at gmail.com
Sun Sep 4 20:09:19 CEST 2011


On Sep 4, 2011, at 13:18 , warc 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.
> 

Well, then print out x, j, and pivot just before hitting that test (i.e., before the loop and at the end of it).

With sample() in the code, you will naturally get different results at each run. 

It's your problem, so your debugging, but I'd wager that nothing is keeping j from hitting zero if you sample a pivot equal to min(x).


> 
> 
> 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.

-- 
Peter Dalgaard, Professor,
Center for Statistics, Copenhagen Business School
Solbjerg Plads 3, 2000 Frederiksberg, Denmark
Phone: (+45)38153501
Email: pd.mes at cbs.dk  Priv: PDalgd at gmail.com
"Døden skal tape!" --- Nordahl Grieg



More information about the R-help mailing list