The problem is that your approach is O(n^2) and it's possible to solve the problem in O(n log(n)). I actually ran a few tests yesterday and found that using std::sort to sort the range first and then remove duplicate trivially is the fastest. Using the STL heap_sort is about 1.5 times slower but has the same growth characteristics.
hehe... I'm just a beginner.Quote:
Originally posted by Yves M
The problem is that your approach is O(n^2) and it's possible to solve the problem in O(n log(n)). I actually ran a few tests yesterday and found that using std::sort to sort the range first and then remove duplicate trivially is the fastest. Using the STL heap_sort is about 1.5 times slower but has the same growth characteristics.
That's way over my head. I'll take your word for it. ;)
Get a book on algorithms and data structures :) The reference is by Knuth (D. E. Knuth, The Art of Computer Programming) but there are quite a few other ones that are good. I used Robert Sedgewick's Algorithms in Pascal, but it's also available for C. It's a bit easier to read than Knuth ;)
If you are serious about programming, then you should read one of those books ;) Reading "Writing a Windows XP program in C++ in four steps for dummys" is ok, but it won't teach you much about programming ;)
Hello gurus, you have here a very interesting topic.
Let me join in :)
Please check my code below. My approach is similar with selection sort algorithm. So, what is the "run time" of selection sort algo, again? I forgot, but at least it is better than 0(n^2).
Simple. ;)Code:char input[] = "the quick brown fox jumps over the lazy dog.";
int len = strlen(input);
int end = 1;
for(int k = 1; k < len; k++)
{
for(int j = 0; j < end; j++) // check duplication of str[k] from str[0] to str[end]
{
if(input[j] == input[k])
break; // a duplicate is found.
}
if(j == end) // check if no duplicate char is found
{
input[end] = input[k]; // append the unique character
end++; // increment the "end" pointer (for the next candidate)
}
}
input[end] = 0; // terminate the string. now the output.
Owen
Interesting idea :) Unfortunately selection sort is also O(n^2). The reason is pretty simple. You have two nested loops, each of which can go potentially from 1 (or 0) to len.Quote:
Originally posted by owenrb
So, what is the "run time" of selection sort algo, again? I forgot, but at least it is better than 0(n^2).
The orst case for your algorithm is actually if the input consists of all distinct characters.
Thanks for the book recommendations. :D
This is a series of books written in the late '60s and early '70s. It was absoulutely definitive at the time. Nothing significant has changed in computing since then.Quote:
D. E. Knuth, The Art of Computer Programming
Just faster and bigger, otherwise the same.