quicksort

Hi, i've tried to get my quicksort to work, but i think because i have been looking at it for so long i cant see the problem with it so if someone can spot my mistake that would be great! it will run but it wont sort the array, i hve tried looking for code on the net but copuld not find any.

Code:

---

int parttition(int myArray[],int first, int last);
void quicksort(int myArray[],int first, int last); 
void quick( int size)
{
       
int        *myArray;       
myArray = (int *) malloc (size * sizeof(int));       
myArray= new int [size];
int x;
        srand((unsigned)time(0));
        for (x=0;x<size;x++)       
{               
          int random_integer = rand()/25;               
          printf("%d\n",myArray[x]=random_integer);       
}
int first,last;
        first=0;
        last=size-1;
        quicksort( myArray, first,  last);
        for (x=0;x<size;x++)
        {
                printf("%d\n",myArray[x]);       
                }
}

  int parttition(int myArray[],int first, int last)
{
        int pivot,i,s;
        pivot=myArray[last];
        i=first;
        s=last-1;
        int temp1=0,temp2=0,temp3=0;
        while( i<=last)       
                {
                if (( myArray[i]>pivot))
        {
        temp1= myArray[i];               
}       
        i++;       
}
        while(s>=0)       
                {
                if ( myArray[s]<pivot)
                {
                        temp2= myArray[s];
                }
                s--;
        }
                if ( s<i+1)
                {
                        myArray[s]=temp1;
                        myArray[i-1]=temp2; 
                }
                else
                {
                        return first;
                }
                temp3=pivot;
                pivot=temp1;
                myArray[i-1]=myArray[last];
        }

 void quicksort(int myArray[],int first, int last)
{
        int pivot=0;
        if (first<last)
        {
                        pivot=parttition(myArray,first, last);                                        quicksort(myArray,first, pivot-1);
                        quicksort(myArray,pivot+1, last);
        }
}

---

If you want somebody to look at your code, you should firstly indent it properly. It would also help if the program would be complete (with main, and includes). Something like that.

Code:

---

#include <cstdlib>
#include <cstdio>
#include <ctime>

int parttition(int myArray[],int first, int last);
void quicksort(int myArray[],int first, int last); 
void quick( int size)
{
    int        *myArray;       
    myArray = (int *) malloc (size * sizeof(int));       
    myArray= new int [size];
    int x;
    srand((unsigned)time(0));
    for (x=0;x<size;x++)       
    {               
        int random_integer = rand()/25;               
        printf("&#37;d\n",myArray[x]=random_integer);       
    }
    int first,last;
    first=0;
    last=size-1;
    quicksort( myArray, first, last);
    for (x=0;x<size;x++)
    {
        printf("%d\n",myArray[x]);       
    }
}

int parttition(int myArray[],int first, int last)
{
    int pivot,i,s;
    pivot=myArray[last];
    i=first;
    s=last-1;
    int temp1=0,temp2=0,temp3=0;
    while( i<=last)       
    {
        if (( myArray[i]>pivot))
        {
            temp1= myArray[i];               
        }       
        i++;       
    }
    while(s>=0)       
    {
        if ( myArray[s]<pivot)
        {
            temp2= myArray[s];
        }
        s--;
    }
    if ( s<i+1)
    {
        myArray[s]=temp1;
        myArray[i-1]=temp2; 
    }
    else
    {
        return first;
    }
    temp3=pivot;
    pivot=temp1;
    myArray[i-1]=myArray[last];
}

void quicksort(int myArray[],int first, int last)
{
    int pivot=0;
    if (first<last)
    {
        pivot=parttition(myArray,first, last);                                       
        quicksort(myArray,first, pivot-1);
        quicksort(myArray,pivot+1, last);
    }
}

int main()
{
    quick(10);
}

---

Now when I run this I get a runtime crash.

When I turn on warnings, I get this for parttition: "Warning: control reaches end of non-void function" (you don't return anything).

Not sure about the algorithm. Usually you determine a pivot value, then you start iterating from both ends and swap pairs of items where one is less than the pivot and the other is more than the pivot (in wrong order). Those two iterators should meet somewhere and the new partition would be at the meeting place (values in the first part are all smaller than values in the second part).

It's hard to say, given that formatting, what anything is doing. My Hat of Guessing thinks you're using i in the while (s>=0) loop as meaningful, when it's leftover from the previous loop and will always equal last+1 (so it's not even in your array). But I might have missed a brace or whatever.

one part i forgot to mention was that when i debug the program it carshes and tell me ther was a stack overflow and points to the partiotn function. but i have tried numerous things to solve the overflow but i cant figure out how to

The first big problem is that the pivot function doesn't return anything.

Secondly the logic looks definately wrong. What your code apparently does:
a) loop from start to end. The last value larger than pivot gets stored in a temporary.
b) loop from end to start. The first value smaller than pivot gets stored in another temporary.
c) Assign one temporary to array index -1 (s < 0 when the previous loop finishes) and the other towards the end.
d) Do some random assignments and quit function without returning anything.

I think you should start over with the partition function.

Being one of the sorting exports on here I'd have to say that your "parttition" function doesn't partition. (oh and you spelt it wrong)

The partitioning step of quicksort involves two loops nested within an outer loop:
1. One inner loop searches forwards (initially from the start) searching for the first item that is less than the pivot.
2. The other inner loop searched backwards (initially from the end) for the first item that is greater than the pivot.
3. If you end up finding that your searches caught up to each other then you now exit the outer loop as there are no more items on the wrong side of the pivot.
4. Or now that you have found two items that are both on the wrong sides of the pivot you swap them and continue with the outer loop.

You don't have an outer loop!

i'm still haveing problems with my partition function, i have changed it complelty but it is still not working, can any one help me please?

Code:

---

void parttition(int myArray[],int first, int last)
{

        int pivot,f,l;
        pivot=myArray[last];
        f=first;
        l=last-1;int temp=0,temp1=0;
        int x;bool state1=false,state2=false,state3=false;
        while( f<l)
        {

                while((state1==false)&&(f<last))
                {
                        if (myArray[f]>pivot)
                        {
                                f++;
                        }
                        else
                        {
                                state1=true;
                        }
                }

                while((state2==false)&&(l>first))
                {
                        if (myArray[l]<pivot)
                        {
                                l--;
                        }
                        else
                        {
                                state2=true;
                        }
                }
                printf("\n%d\n",myArray[f]);
                printf("%d\n",myArray[l]);
                if (l<f)
                {
                        temp=myArray[f];
                        myArray[f]=myArray[l];
                        myArray[l]=temp;
                        state3=true;
                        if ((myArray[f]>pivot)&&(state3==true))
                        {
                                temp1=myArray[f];
                                myArray[f]=myArray[last];
                                myArray[last]=temp1;       
                        }
                }
                else
                {
                        if ((myArray[l]>pivot)&&(state3==true))
                        {
                                temp1=myArray[l];
                                myArray[l]=myArray[last];
                                myArray[last]=temp1;
                        }
                }
                printf("\n%d\n",myArray[f]);
                printf("%d\n",myArray[l]);
                int x;
                                printf("\n");
                for (x=0;x<3;x++)
                {
                        printf("%d\n",myArray[x]);
                }       
                parttition(myArray,first, l);
                parttition(myArray,f, last);


        }       


}

---

Quote:

---

Originally Posted by WelshGrandSlam

Code:

---

                while((state1==false)&&(f<last))
                {
                        if (myArray[f]>pivot)

---

---

This should be the other way 'round, shouldn't it? You want to skip ahead if your left array element is less than the pivot, and flag it for swapping if its greater. This way all the elements larger than the pivot end up on the right-hand side. (I realize upon looking back that iMalc disagrees with me, which worries me greatly.)

Sorry you're right tabstop. I had it back-to-front, which would be for sorting descending. I need to work on my proof-reading.
Sorry if I also put WelshGrandSlam wrong.
It looks like you're doing the entire sort from the partition function now, since you're put the recursive calls in there. It's fine writing the whole thing as one function, but you can't really call it partition any more.
Also you definitely shouldn't have the recursive calls inside the outer loop. It'll probably work but it will be far far slower than bubble sort.
You're probably over-thinking it a bit too. My inner loops look like this:

Code:

---

            do ++i; while (a[i] < tempItem);
            do --j; while (tempItem < a[j]);

---