[R] what is wrong with my quicksort?

[Mark Leeds]

Hi: I looked it up in google because I couldn't remember how quicksort worked.
( i'm getting old ).

the java code is below. I didn't translate it but what you are doing
incorrectly is
calling partition recursively when you need to call the quicksort
algorithm recursively.
you'll see what I mean if you look at the java code below.

there are many links on the internet that explains why it works with
examples etc. here's one:
http://www.algolist.net/Algorithms/Sorting/Quicksort

 good luck.

#==============================================================

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 Sat, Sep 3, 2011 at 10:50 PM, Jim Holtman <jholtman at gmail.com> 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.
>