C++ Quicksort array of string pointers

Question

I'm not sure what's wrong, but this isn't sorting right.

This is the implementation:

int quickSort(std::string **arr, int left, int right)
{
    static int swaps;
    int i = left, j = right;
    std::string *tmp;
    std::string pivot = *arr[(left + right) / 2]; //middle element
    //partition
    while( i <= j ) {
        while ((*arr[i]).compare(pivot) < 0) {
            i++;
        }
        while ((*arr[j]).compare(pivot) < 0) {
            j--;
        }
        if ( i <= j ) {
            swaps++;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    //recursion
    if ( left < j ) {
        quickSort(arr, left, j);
    }
    if ( i < right ) {
        quickSort(arr, i, right);
    }
    return swaps;
}

arr is an array of string pointers. Each index points to a string, in this instance, the strings are all names. The method is definitely making swaps, I just can't make any sense of what it's doing exactly.

For example, given these initial values:

Pointer    Value
0055B5D8 - JAMES
0055B3F8 - JOHN
0055C808 - ROBERT
0055C8A8 - MICHAEL
0055CB88 - WILLIAM
0055CC28 - DAVID
0055CCC8 - RICHARD
0055CD68 - CHARLES
0055CE08 - JOSEPH
0055CEA8 - THOMAS

My quickSort method consistently moves them into this order:

Pointer    Value
0055C8A8 - MICHAEL
0055B5D8 - JAMES
0055C808 - ROBERT
0055B3F8 - JOHN
0055CB88 - WILLIAM
0055CEA8 - THOMAS
0055CE08 - JOSEPH
0055CD68 - CHARLES
0055CCC8 - RICHARD
0055CC28 - DAVID

The "unsorted" list has pointers in ascending order, given that I'm allocating all these one immediately after another to build the initial array. But the "sorted" list doesn't seem sorted at all.

For clarity, the goal is to alphabetize the list of names.

Shouldn't the second while loop be while ((*arr[j]).compare(pivot) > 0)? You want to keep the items that are greater than the pivot on the right side. — MasterOfBinary
– MasterOfBinary, Commented Nov 12, 2013 at 0:50
If you have no reason not to use vectors, get rid of std::string **arr and make it std::vector<std::string*>& strings at least. — LihO
– LihO, Commented Nov 12, 2013 at 0:52

paddy · Accepted Answer · 2013-11-12 00:51:02Z

6

You're using the same comparison for both sides of the pivot. That means you're allowing smaller values to stay on the right-hand side. You need to modify as follows:

    while ((*arr[i]).compare(pivot) < 0) {
        i++;
    }

    while ((*arr[j]).compare(pivot) > 0) {    // <----
        j--;
    }

This is a classic copy-paste error. Be careful when duplicating a section of code instead of writing it from scratch. Your brain is very easily tricked into thinking you changed all the important bits.

answered Nov 12, 2013 at 0:51

paddy

63.7k7 gold badges68 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

nhgrif Over a year ago

wut... lol thanks. Can't believe how long I've been looking at this.

Collectives™ on Stack Overflow

C++ Quicksort array of string pointers

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related