current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 1 down vote favorite
1

This will determine if a string is unique or not using quicksort, so that it should take \$O(nlogn)\$ time and not \$O(n^2)\$ time.

I will call the test function code from main.

This runs successfully, but when I try to write a randomized partition, it will fail. I have written that code separately.

FindUniqueCharInString.h

#define MAX 15
class FindUniqueCharInString
{
public:
    FindUniqueCharInString(void);
    ~FindUniqueCharInString(void);
    void test();

private:
    void swap(int index1, int index2);
    void quickSort(int start, int end);
    int partition(int start, int end);

    char arr[15];
};

FindUniqueCharInString.cpp

#include "FindUniqueCharInString.h"
#include <iostream>

using std::cout;
using std::endl;

FindUniqueCharInString::FindUniqueCharInString(void)
{
    char *tempArr = "SOMESTRING";

    strcpy(arr,tempArr);
}

FindUniqueCharInString::~FindUniqueCharInString(void)
{
}

void FindUniqueCharInString::test()
{
    quickSort(0,strlen(arr));

    for(int i = 0;i<strlen(arr);i++)
    {
        cout<<arr[i] << " ";
    }

    cout<<endl;

    bool isUnique = true;
    for(int i = 0;i<strlen(arr) - 1;i++)
    {
        if(arr[i] == arr[i+1])
            isUnique = false;
    }

    if(isUnique)
        cout<<"Unique" <<endl;
    else
        cout<<"Not unique"<<endl;

}

void FindUniqueCharInString::swap(int index1, int index2)
{
    if(arr[index1] != arr[index2])
    {
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

void FindUniqueCharInString::quickSort(int start, int end)
{
    if(start >= end)
        return;

    int p = partition(start,end);
    quickSort(start, p - 1);
    quickSort(p + 1,end);
}

int FindUniqueCharInString::partition(int start, int end)
{
    int pivot = arr[end - 1];
    int t = start;

    for(int i = start; i< end-1; i++)
    {
        if(arr[i] <= pivot)
        {
            swap(i,t);
            t++;
        }
    }

    swap(t,end - 1); //swap index and pivot pos

    return t;
}

Randomize partition function:

int FindUniqueCharInString::partition(int start, int end)
{
    int m = start + (end - start)/2;
    int pivot = arr[m];
    int t = start;

    swap(m,end -1); //putting pivot element to end

    for(int i = start; i< end-1; i++)
    {
        if(arr[i] <= pivot)
        {
            swap(i,t);
            t++;
        }
    }

    swap(t,end - 1); //swap index and pivot pos

    return t;
}
share|improve this question
    
Can you include a failing test case? I tried to comment but could not since I joined only recently. – user2371765 Oct 4 '16 at 16:31
    
@user2371765 same example I have taken in running program is failing for randomized partition. – Pranit Kothari Oct 4 '16 at 16:38
    
Aren't questions about code with errors off-topic? @Jamal? – Zeta Oct 4 '16 at 18:04
    
@Zeta: Yes, but I didn't close this one right away. I was hesitant since some code was written separately. Feel free to flag-to-close if you wish. – Jamal♦ Oct 4 '16 at 18:16
up vote 2 down vote accepted

First, the problem with partitioning (unfortunately, the "working" code works by accident). You correctly setup the algorithm for end be a one-off index. It means that for the left subarray p is its end. However you call it with p - 1, and a valid last character doesn't participate in partitioning. Fix is simple:

    quickSort(start, p);

  • #define MAX 15. I don't see any use of MAX

  • FindUniqueCharInString suggests that the class is there to find unique characters. Turns out that it doesn't find anything, but instead it tests for character uniqueness. You need to rename it to reflect its purpose (hint: if you can't find a good name, most likely a class has no purpose, and a free function will do the same just fine).

  • An utility method like test() shouldn't print anything, but return its results. In this case, it should return a bool, for example

    for(int i = 0;i<strlen(arr) - 1;i++)
{
    if(arr[i] == arr[i+1]) {
        return false;
    }
}
return true;

  • Always use curly braces, even for one-liners.

  • Of course the code will fail badly if the input string is longer than 15 characters. Consider using std::vector instead of hardcoded array.

share|improve this answer
    
Thanks for answer. It solved my problem. Thought I do not understand problem with p-1, shouldn't I skip pivot element because it is already at sorted position. Please look at thumbnail of video I am following for quicksort (tinyurl.com/j92wsmb), it uses p-1 and p+1 to skip pivot. May be I have made some other terrible mistake, but just to clarify. – Pranit Kothari Oct 5 '16 at 2:15
    
@PranitKothari p does skip pivot! p-1 (unwantedly) skips one extra element. p-1 works if the end parameter denotes last valid element. In your setup it denotes first invalid one. – vnp Oct 5 '16 at 3:15
up vote 6 down vote

Complexity

If the intent was to meet an \$O(N log N)\$ requirement, you've technically failed--quicksort has an expected complexity proportional to N log N, but big-O deals strictly with the worst-case complexity--and worst-case complexity of quicksort is \$O(N^2)\$.

Class Design

One of the old basic ideas of how to do object-oriented design is to start by writing down a one-page (or less) description of what the program is supposed to do. You then pick out the nouns that form the major themes in that description. Those are your classes.

The point of that is to note that most classes should normally represent nouns1. Things that exist. Objects. In a typical case they should not represent verbs.

In this case, however, you have one primary class--and its name is a verb, not a noun. This leads to a lot of question over whether it makes sense for this class to be a class, or whether we have kind of a conglomeration of "stuff" thrown together into something that says it's a class, but isn't doesn't form a particularly coherent...thing.

Standard Containers

Good uses for C style arrays in C++ are quite rare. Your arr doesn't strike me as one of them. If you really need a fixed-size array, you should probably use std::array instead. Otherwise, you're probably best off using std::vector.

Standard Algorithms

The standard library already has algorithms to handle the job at hand. Most code should just use st::sort followed by std::unique, rather than attempting to craft the same on your own.

Self-defeating design

Right now, you've limited the collection size to only 15 elements. For such a small size, a simpler sorting algorithm (e.g., insertion sort) will almost always be at least a little faster than a quicksort. In short, combining the elements you have in the way you have just doesn't make sense.

Use of strlen

If you insist on using strlen at all, you shouldn't call it in the condition of a for loop, like:

for (int i=0; i<strlen(foo); i++)

A few compilers know how to optimize this by hoisting the call to strlen out of the loop, but most don't. With those compilers, this loop will have \$O(N^2)\$ complexity instead of the O(N) you probably want/expect.

Note that if you used std::vector or std::string for your storage, this wouldn't be a problem. Unlike strlen, both these guarantee that you can find the size with \$O(1)\$ complexity instead of \$O(N)\$.

Side Effect-ridden code

Most of your functions implicitly modify FindUniqueCharInString::arr. It's generally much better to avoid this when possible--and it's pretty trivial in most of these cases. Just for a trivial example, right now your swap is passed to integers, i and j, and it swaps arr[i] with arr[j]. It would be much better to pass (for example) pointers or references to the contents, so the modifications are explicit:

swap(i, j); // ambiguous, implicit side effects on `arr`

swap(arr[i], arr[j]); // clear, effect on `arr` is obvious.

Summary

At least in my opinion, the other issues pale compared to just making good use of the standard library. 

std::string arr {"SOMESTRING"};
std::sort(arr.begin(), arr.end());
auto end = std::unique(arr.begin(), arr.end());

// show the unique characters    
std::copy(arr.begin(), end, std::ostream_iterator<char>(std::cout, "\n"));

1. The primary exception to this is function objects--i.e., classes that act mostly like a function, including overloading operator() to do whatever it is they do

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.