C++

Forum

 
Quick Sort dosen't work!

cpcp (17)
do you know why?
it's about generic pointers, and I need to sort points by Y:
Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
void qs (void *&arr, int left, int right, void (*swap) (void *p1, void *p2),
        int (*cmp)(void *p1, void *p2), void * (*get) (void *arr,int i))
{
    cout<<"-> "; print_p(arr,5,'2'); cout<<endl;
    int i=left, j=right;
    void *pivot=get(arr,(i+j)/2);
    while (i<=j)
    {
        while (cmp(get(arr,i),pivot)==SMALL)
            i++;
        while (cmp(get(arr,j),pivot)==1)
            j--;
        if (i<=j)
        {
         swap(get(arr,i),get(arr,j));
         i++;
         j--;
        }
    }
    if (left<j)
        qs(arr,left,j,swap,cmp,get);
    if (i<right)
        qs(arr,i,right,swap,cmp,get);
}

I tried to compare 5 points but this function didn't sort the points.

Here is the output:

1
2
3
4
5
6
7
 
-> (2.32, 23) (-21, 23) (-65, 34) (34, -11) (21, -22)

-> (2.32, 23) (-21, 23) (21, -22) (34, -11) (-65, 34) 

-> (21, -22) (-21, 23) (2.32, 23) (34, -11) (-65, 34) 

(21, -22) (-21, 23) (2.32, 23) (34, -11) (-65, 34)

the first line is the points at the enter order. the last line show you the result...

If you have more Q or you want to see other functions at the program tell me and I will post.

Thank you!

Here are the specific functions:

//The function compare two points by "y".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
int comp_py(void *p1, void *p2)
{
    double p1x=get_x(*((struct Point*)p1)),
           p2x=get_x(*((struct Point*)p2)),
           p1y=get_y(*((struct Point*)p1)),
           p2y=get_y(*((struct Point*)p2));
    if (p1y>p2y)
        return 1;
    else
        if (p1y==p2y)
        {
            if (p1x>p2x)
                return 1;
            else if (p1x<p2x)
                return SMALL;
            else return 0;
            return 0;
        }
        else
            return SMALL;
}

the swap function: //This function swaps between two points.

1
2
3
4
5
6
7
8
9
10
11
 
void swap_p(void *p1, void *p2)
{
    struct Point temp=*((struct Point*)p1);
    *((struct Point*)p1)=*((struct Point*)p2);
    *((struct Point*)p2)=temp;
}

void* get_p(void *arr, int i)
{
    return ((struct Point*)arr)+i;
}

Here is the calling to the function:

qs(arr,0,size-1,swap_p,comp_py,get_p);
if you want more things - jest ask for them and I will post...
Last edited on
cire (8284)
Why would you write a C++ program this way? C, I could understand.. C++?

Your sorting algorithm is incorrect. It is not a faithful implementation of the quicksort algorithm.

See: http://en.wikipedia.org/wiki/Quicksort
Topic archived. No new replies allowed.