CODEWITHSUNDEEP
c++quicksort
Amanda Zhu
Amanda Zhu

Reputation: 75

Implementing quicksort on strings

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;
}

Upvotes: 2

Views: 870

Answers (1)

vincent
vincent

Reputation: 1390

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.

Upvotes: 1

Related Questions