Implementing quicksort on strings

Question

I'm trying to implement the quicksort on a string of characters. The output should give me an alphabetical order version of the input, however right now it's just giving me the original input. This was an attempt trying to translate the pseudo code from Intro to Algorithm 3rd edition on Quicksort.

Any help would be greatly appreciated, thanks!

Here's the pseudo code of quicksort from the book

#include <string>
#include <iostream>
#include <stdlib.h>

using namespace std;

int partition_str(string A, int start, int finish){
    char x = A[finish], temp;
    int i = start - 1;
    for (int j = start; j <= finish -1; j++){
    if (A[j] <= x){
        i ++;
        temp = A[i]; A[i] = A[j]; A[j] = temp;
    }
    temp = A[i+1]; A[i+1] = A[finish]; A[finish] = temp;
    return i+1;
    }
   }

 string quicksort_char(string A, int start, int finish)
{
if (start < finish)
{
    start = partition_str(A, start, finish);
    quicksort_char(A, start, finish -1);
    quicksort_char(A, start+1, finish);
}
return A;
}

int main(){
    string test = "gsgkdsdkjs";
    string result = quicksort_char(test, 0, 10);
    cout << result << endl;
    return 0;
}

score 1 · Accepted Answer · edited May 23 '17 at 12:16

In the pseudocode you linked, it mentions that partition() alters subarrays in place. This insinuates that you need to pass by reference, rather than by value. Notice the ampersand (&) I add in the function signature. Your code was passing by value, so it was making a copy of the input string, rather than altering it in place. In your quicksort() function, you wrote the code expecting that A will be altered by the function.

I cleaned up your code a bit here with the intent of making it clearer and look more like the pseudocode...

#include <iostream>
#include <string>
using namespace std;

void exchange(char& a, char& b)
{
    char value_of_a = a;
    char value_of_b = b;

    a = value_of_b;
    b = value_of_a;
};

int partition(string& A, int p, int r)
{
    char x = A[r];
    int i = p-1;

    for (int j=p; j<=(r-1); ++j)
    {
        if (A[j] <= x)
        {
            i++;
            exchange(A[i], A[j]);
        }
    }
    exchange(A[i+1], A[r]);

    return i+1;
};

void quicksort(string& A, int p, int r)
{
    if (p < r)
    {
        int q = partition(A, p, r);
        quicksort(A, p, q-1);
        quicksort(A, q+1, r);
    }
};

int main()
{
    string input = "gsgkdsdkjs";

    cout << "input string: " << input << endl;

    quicksort(input, 0, input.size());

    cout << "sorted string: " << input << endl;

    return 0;
}

In your partition_str() function you pass in string A by value, which makes a copy of A rather than using the same A you passed in. It then performs some operations and returns an integer. The copy of A is then thrown away and your original A variable was never modified. This means that if you want your variable A to be changed, you must pass by reference.

Also, don't be confused by the function argument naming. Your partition_str() function signature is:

int partition_str(string A, int start, int finish)

The fact the 'string A' is defined as an argument does not mean that it is related to any other variable in your code called 'A'. It is merely a way of referring to particular argument that was passed in.

Much appreciated! The link about passing on reference was exactly what I needed! But um I am still puzzled.. how could you tell by the pseudo code that it was passing by reference of the array instead of the array itself? — Amanda Zhu, Oct 26 '16 at 22:34
I have answered this by appending to by original post. Please accept my answer if you found it useful. — vincent, Oct 27 '16 at 15:07

Implementing quicksort on strings

1 Answers1