sorts and iterators

[Christopher Pisz]

I am brushing up for an upcoming interview. They let me know beforehand
that they will be asking about sorting algorithms and expect me to write
some code. They let me know I should study, so I am studying

I know the old college academic exercises where I can make a struct that
represents a node and implement my own linked list, etc. etc. I'd like
to try some custom sorts and performance time them like I would in the
real world. So, I ask myself, how would I do it in the real world?

I would most likely have some stl container or a class that implements
iterators. I am also aware the stl has a build in sort with O(nlog(n))
complexity.

So, how do I go about implementing a sort that uses iterators? I am not
really sure where to start.

I did some Googling and see stl sort requires swap and a move copy. I
believe these are new c++13 features? Can we assume I am still using the
2003 standard for now and then try again using C++13?

My current job was using really out of date tools and I haven't had the
chance yet to catch up on the new standard.

 

[Christopher Pisz]

I am brushing up for an upcoming interview. They let me know beforehand
that they will be asking about sorting algorithms and expect me to write
some code. They let me know I should study, so I am studying

I know the old college academic exercises where I can make a struct that
represents a node and implement my own linked list, etc. etc. I'd like
to try some custom sorts and performance time them like I would in the
real world. So, I ask myself, how would I do it in the real world?

I would most likely have some stl container or a class that implements
iterators. I am also aware the stl has a build in sort with O(nlog(n))
complexity.

So, how do I go about implementing a sort that uses iterators? I am not
really sure where to start.

I did some Googling and see stl sort requires swap and a move copy. I
believe these are new c++13 features? Can we assume I am still using the
2003 standard for now and then try again using C++13?

My current job was using really out of date tools and I haven't had the
chance yet to catch up on the new standard.

I gave it a shot and came up with the following code. std::swap appears
to actually be swapping the iterators instead of the values of the
iterators. The loop goes on forever. I am not sure I understand the use
of std::swap anymore. What should I do different? I want to swap the
contents of the element, but keep the iterator pointing to the same
position.


#include <algorithm>
#include <iostream>
#include <vector>

//-------------------------------------------------------------------------------
/// Bubble Sort
/// Complexity O(n^2)
template<typename iterator>
void BubbleSort(iterator begin, iterator end)
{
// Nothing to do when container is empty
if( begin == end )
{
return;
}

iterator previous = begin;

iterator current = previous;
++current;

for(; current != end; ++current)
{
std::cout << "Current: " << *current;
std::cout << " Previous: " << *previous << " " << std::endl;

if( *current < *previous )
{
// This appears to swap the internal pointer and actually
swap the iterators instead of the values?
std::swap(current, previous);
}

std::cout << "sCurrent: " << *current;
std::cout << " sPrevious: " << *previous << " " << std::endl;

previous = current;
}
}

//------------------------------------------------------------------------------
/// Test driver
int main()
{
typedef std::vector<unsigned int> Collection;
Collection collection;

collection.push_back(5);
collection.push_back(2);
collection.push_back(4);
collection.push_back(1);
collection.push_back(3);
/*
// Using STL sort
std::sort(collection.begin(), collection.end());

for(Collection::const_iterator it = collection.begin(); it !=
collection.end(); ++it)
{
std::cout << ' ' << *it;
}
std::cout << '\n';
*/
// Bubble sort
BubbleSort(collection.begin(), collection.end());


system("pause");
return 0;
}

 

[osmium]

I am brushing up for an upcoming interview. They let me know beforehand
that they will be asking about sorting algorithms and expect me to write
some code. They let me know I should study, so I am studying

I know the old college academic exercises where I can make a struct that
represents a node and implement my own linked list, etc. etc. I'd like to
try some custom sorts and performance time them like I would in the real
world. So, I ask myself, how would I do it in the real world?

I would most likely have some stl container or a class that implements
iterators. I am also aware the stl has a build in sort with O(nlog(n))
complexity.

So, how do I go about implementing a sort that uses iterators? I am not
really sure where to start.

I did some Googling and see stl sort requires swap and a move copy. I
believe these are new c++13 features? Can we assume I am still using the
2003 standard for now and then try again using C++13?

My current job was using really out of date tools and I haven't had the
chance yet to catch up on the new standard.

I wish I had more time, I am really rushed today. ISTM you are studying the
wrong thing. Sorts are quick sort, bubble sort, Shell sort, radix sort, et
al. An iterator is just a clumsy, annoying array. You are fussing with the
latter - the question as I read your story is about the former. It would be
nice, at this point, to listen *carefully* to their instructions to you.

 

[Christopher Pisz]

I wish I had more time, I am really rushed today. ISTM you are studying the
wrong thing. Sorts are quick sort, bubble sort, Shell sort, radix sort, et
al. An iterator is just a clumsy, annoying array. You are fussing with the
latter - the question as I read your story is about the former. It would be
nice, at this point, to listen *carefully* to their instructions to you.

Well, I already know about sorts on paper. I want to be able to code
them up. I never really understand the driving force for these types of
questions in interviews though. I mean, look at why I I can't code it up
right now; Well, because for 10 years I've been using std::sort. It has
complexity O(log(n)). Am I going to do better than that? No. So, I will
never implement my own sort. Thus, I ask myself, why do so many
interviews ask these types of academic questions? Great! I proved that I
know how to do something I will never do on the job...I might be wrong,
after all, we used to say that in math class as a youngster too.

At any rate, I want to go the extra mile and work through them. I do not
want to program my own container like we do in these academic scenarios:

struct Node
{
Node * next;
unsigned int value;
};


I've done that a billion times. I want to learn how to perform
algorithms using iterators. This will be useful to me later. I know how
to write a predicate as a functor, etc. I can see use for making
templated algorithms that take iterators that do other things aside from
sorting.

 

[Öö Tiib]

I am brushing up for an upcoming interview. They let me know beforehand
that they will be asking about sorting algorithms and expect me to write
some code. They let me know I should study, so I am studying

There are lot of sorting algorithms for various purposes and it may
be interesting to play with them (most of the variety feels to be
result of such playing) but unless there are serious performance
considerations one should use std::sort.

I know the old college academic exercises where I can make a struct that
represents a node and implement my own linked list, etc. etc. I'd like
to try some custom sorts and performance time them like I would in the
real world. So, I ask myself, how would I do it in the real world?

Most of them are published in places like Wikipedia. Implementing and
trying and tweaking and comparing them all ... reserve months.

I would most likely have some stl container or a class that implements
iterators. I am also aware the stl has a build in sort with O(nlog(n))
complexity.

Not only that but standard library also has couple of constantly sorted containers in it.

So, how do I go about implementing a sort that uses iterators? I am not
really sure where to start.

It feels that you are aware of standard library but still in difficulties
with it. First lean to use it, then start to write your own templates.

I did some Googling and see stl sort requires swap and a move copy. I
believe these are new c++13 features? Can we assume I am still using the
2003 standard for now and then try again using C++13?

std::sort has been in standard library from C++98. Most recent standard
is C++11. Fixes are planned to be C++14. Do not read random crap that
Google tosses at you, read good books. Wikipedia is also often accurate.

My current job was using really out of date tools and I haven't had the
chance yet to catch up on the new standard.

How old? 1998 was decade and half ago. If you want to swap pointed by
iterator objects then write 'std::swap(*a,*b)' not 'std::swap(a,b)'.
But I agree what Osmium said, you should learn sorting algorithms and not
generic programming with templates.

 

[Christopher Pisz]

If you are going to be asked about sorting, then you should study sorting
algorithms, not iterators or swapping or whatever, as others have already
told you. I guess you are expected to be able to implement all major
sorting algorithms on a numeric array, using either indexes or pointers,
and that's it. The quicksort algorithm is the most important one.

About your problem with iterators - it seems like you forgot to dereference
your iterators, but as said, messing with iterators will just distract you.

hth
Paavo

Ok, Ok. I was just having fun and trying to learn more. Perhaps I'll
make a whole different topic for it. People are focused on the
interview, while I am not.

Like I said. I really don't understand why some of these interviews are
so academic. What is the interviewer going to know about me when I
implement a merge sort in C? I'll never have to do it again and any Joe
Bob can memorize Wikipedia, so I question what types of people I'll get
to work with if the interview is purely academic.

But sure, I've memorized what bubble sort, merge sort, radix sort, etc.
all are, how they work, and how to write them in psuedocode tons of
times past. Then I brain dumped it all afterward. I am not too worried
about that. It is all review. I still couldn't implement them in real
code, because I've never, in my entire career, had to. Who does? I use
the STL and the algorithms in it. If I saw some custom implementation
doing a sort, I'd really question it in production code.

So, I'll try a few using plain old array and come back if I get stuck.

 

[Öö Tiib]

Like I said. I really don't understand why some of these interviews are
so academic. What is the interviewer going to know about me when I
implement a merge sort in C? I'll never have to do it again and any Joe
Bob can memorize Wikipedia, so I question what types of people I'll get
to work with if the interview is purely academic.

There are people whose mindset you do not understand in charge
*everywhere*. That is good. Most interesting is to work under rule of
geniuses, they think three steps farther than you so you will be half
useful slum for them forever. Their weakness is their obsession of being
always right, but careful when using it, remember, they are three steps
ahead of you. Average people are lot more comfortable to deal with. If
you are not skilled then opportunity to learn to attract them and to
manipulate with them is good place from where to start.

If I saw some custom implementation doing a sort, I'd really question
it in production code.

Why? The design of a container or data type contained may be such
that std::sort is quite far from optimal. That may not matter if that sort
is done rarely and may be crucial if it is done often.

 

[Christopher Pisz]

There are people whose mindset you do not understand in charge
*everywhere*. That is good. Most interesting is to work under rule of
geniuses, they think three steps farther than you so you will be half
useful slum for them forever. Their weakness is their obsession of being
always right, but careful when using it, remember, they are three steps
ahead of you. Average people are lot more comfortable to deal with. If
you are not skilled then opportunity to learn to attract them and to
manipulate with them is good place from where to start.

Why? The design of a container or data type contained may be such
that std::sort is quite far from optimal. That may not matter if that sort
is done rarely and may be crucial if it is done often.

Real world experience thus far tells me that 9 times out of 10:

1) An individual is less likely to provide a solution that is more
optimal than one cooked up by a committee, and under the constraints of
standardization.

2) An individual is far more likely to create defects then in a little
used solution than a widely used standard solution is going to contain.

3) An individual, in my work experience, hardly _ever_, actually runs a
performance test to verify that whatever neat little trick they had in
mind actually made a significant impact.

However, it is not a concrete rule. I simply _question_ a custom
implementation that does a task that a provided implementation already
does. I have found 1 case out of thousands that it was legit thus far.

Not in the spirit of argument, but in that of curiosity, can you provide
a theoretical example where "The design of a container or data type
contained may be such that std::sort is quite far from optimal" might
hold true, so that I can understand better?

 

[Christopher Pisz]

So, I'll try a few using plain old array and come back if I get stuck.

I think I've implemented a Quicksort after much Googling. I based it
upon someone elses and walked through it on paper a few times. I am not
too certain this meets the criteria. In debugging it, it seems to sort
the given collection upon the first frame of recursion, yet it keeps
calling itself anyway. When it does call itself again, it just goes
through the checks and calls itself again, and goes through the
checks... So I had a stack 5 deep or an equal number of calls as there
were elements. Perhaps I am confused. Should there not be a way to
determing, "Hey we are sorted!, all done!" I cannot claim to follow it
completely. It is one of those fuzzy implementations that is sinking in.

Here is what I have:

//-------------------------------------------------------------------------------
#include <algorithm>
#include <iostream>
#include <vector>

//-------------------------------------------------------------------------------
/// Quick Sort
/// Choose a pivot point and remove it from the collection
/// For each element in the collection, if it is less than the pivot
than add it to another collection 'less', otherwise add it to another
collection 'greater'
/// Perform quicksort recursively on 'less' and 'greater' and
concatentate the results as 'less' 'pivot' 'greater'
/// Best Case Complexity O(nlogn)
/// Average Complexity O(nlogn)
/// Worst Case Complexity O(n^2)

size_t QuickSortPartition(unsigned int * collection, size_t beginIndex,
size_t endIndex)
{
unsigned int pivotValue = collection[beginIndex];
size_t pivotIndex = beginIndex;

while( pivotIndex < endIndex )
{
while( pivotValue < collection[endIndex] &&
endIndex > pivotIndex )
{
--endIndex;
}

std::swap(collection[pivotIndex], collection[endIndex]);

while( pivotValue >= collection[pivotIndex] &&
pivotIndex < endIndex )
{
++pivotIndex;
}

std::swap(collection[endIndex], collection[pivotIndex]);
}

return pivotIndex;
}

void QuickSort(unsigned int * collection, size_t beginIndex, size_t
endIndex)
{
// Nothing to do when container is empty or only has one element
if( beginIndex >= endIndex )
{
return;
}

size_t pivotIndex = QuickSortPartition(collection, beginIndex,
endIndex);

if( pivotIndex > beginIndex)
{
QuickSort(collection, beginIndex, pivotIndex - 1);
}

if( pivotIndex < endIndex )
{
QuickSort(collection, pivotIndex + 1, endIndex);
}
}

//------------------------------------------------------------------------------
void Display(unsigned int * begin, size_t size)
{
for(size_t index = 0; index < size; ++index, ++begin)
{
std::cout << ' ' << *begin;
}
std::cout << '\n';
}

//------------------------------------------------------------------------------
/// Test driver
int main()
{
unsigned int collection[] = {5,2,4,1,3};

// Quick sort
QuickSort(collection, 0, sizeof(collection) / sizeof(unsigned int)
- 1);
Display(collection, sizeof(collection) / sizeof(unsigned int));

system("pause");
return 0;
}

 

[Öö Tiib]

Real world experience thus far tells me that 9 times out of 10:

1) An individual is less likely to provide a solution that is more
optimal than one cooked up by a committee, and under the constraints of
standardization.

There are tools like profilers and performance analysis frameworks.

2) An individual is far more likely to create defects then in a little
used solution than a widely used standard solution is going to contain.

There are tools, unit-tests and testing frameworks.

3) An individual, in my work experience, hardly _ever_, actually runs a
performance test to verify that whatever neat little trick they had in
mind actually made a significant impact.

There are different individuals and collectives. In reality everything
we see is done by mere individuals. You may even sometimes see their
names in standard library implementation if they aren't uselessly modest.
There are no gods. Just aim to be that 1 from 10 or what you had there.
It is actually not that difficult if you try hard enough.

Sorting is so popular topic that you can probably even get a fan-made
specialized experimentation framework (made with love) for few bucks.
Just find out where such a fan lurks and ask nicely.

However, it is not a concrete rule. I simply _question_ a custom
implementation that does a task that a provided implementation already
does. I have found 1 case out of thousands that it was legit thus far.

Each undone work search for hero who can face it. Just be visibly one
and it comes itself to you.

Not in the spirit of argument, but in that of curiosity, can you provide
a theoretical example where "The design of a container or data type
contained may be such that std::sort is quite far from optimal" might
hold true, so that I can understand better?

Oh I'll happily. That may even help you to understand why they are
interested of someone who is familiar with sorting. std::sort is
often Introsort, but you got to see yourself from <algorithm> when
it matters. It is fine *almost* always ... but ... sometimes we *may*
need some edge over it:

When you expect the container to be mostly almost sorted then you may
want to take advantage of that (Smoothsort). When the key of sorting is
part of object representable as integer value then you may want to
take advantage of that (Radix sort, Counting sort). When moving the
elements is expensive (for example when the goal is to sort the contents
of a very large file) then you want to minimize the moves (several ways).
When you have resources to parallelize the process of sorting then you may
want to take advantage of that (some algorithms are better
parallelizable). Some containers have (internally) caps in them and
some algorithms can take advantage of such caps. etc. etc.

 

[Ike Naar]

On 6/30/2013 1:15 PM, Christopher Pisz wrote:
void QuickSort(unsigned int * collection, size_t beginIndex, size_t
endIndex)
{
// Nothing to do when container is empty or only has one element
if( beginIndex >= endIndex )
{
return;
}

The comment is not consistent with the code.
Note that the algorithm uses half-open intervals where
the begin index is inclusive, and the end index is exclusive,
so QuickSort(array, begin, end) sorts the array segment
array[i : begin <= i < end], that is, array[begin .. end-1].

The condition (beginIndex >= endIndex) only checks whether the
array segment is empty; for an array segment containing one element,
(beginIndex < endIndex) because (beginIndex+1 == endIndex) in this case.