sorts and iterators

Discussion in 'C++' started by Christopher Pisz, Jun 30, 2013.

  1. 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, Jun 30, 2013
    #1
    1. Advertising

  2. On 6/30/2013 10:50 AM, Christopher Pisz wrote:
    > 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;
    }
    Christopher Pisz, Jun 30, 2013
    #2
    1. Advertising

  3. Christopher Pisz

    osmium Guest

    "Christopher Pisz" wrote:

    >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.
    osmium, Jun 30, 2013
    #3
  4. On 6/30/2013 11:54 AM, osmium wrote:
    > "Christopher Pisz" wrote:
    >
    >> 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.
    >
    >


    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.
    Christopher Pisz, Jun 30, 2013
    #4
  5. Christopher Pisz

    Öö Tiib Guest

    On Sunday, 30 June 2013 18:50:25 UTC+3, Christopher wrote:
    > 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.
    Öö Tiib, Jun 30, 2013
    #5
  6. On 6/30/2013 12:46 PM, Paavo Helde wrote:
    > Christopher Pisz<> wrote in
    > news:kqpmvl$hsd$:
    >
    >> On 6/30/2013 10:50 AM, Christopher Pisz wrote:
    >>> I am brushing up for an upcoming interview. They let me know
    >>> beforehand that they will be asking about sorting algorithms and

    >
    >> 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.

    >
    > 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.
    Christopher Pisz, Jun 30, 2013
    #6
  7. Christopher Pisz

    Öö Tiib Guest

    On Sunday, 30 June 2013 21:15:36 UTC+3, Christopher wrote:
    > 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.
    Öö Tiib, Jun 30, 2013
    #7
  8. On 6/30/2013 2:00 PM, Öö Tiib wrote:
    > On Sunday, 30 June 2013 21:15:36 UTC+3, Christopher wrote:
    >> 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.


    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, Jun 30, 2013
    #8
  9. Re: Quicksort done. Can I get a check on it?

    On 6/30/2013 1:15 PM, Christopher Pisz wrote:
    > 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;
    }
    Christopher Pisz, Jul 1, 2013
    #9
  10. Christopher Pisz

    Öö Tiib Guest

    On Sunday, 30 June 2013 22:17:52 UTC+3, Christopher wrote:
    > On 6/30/2013 2:00 PM, Öö Tiib wrote:
    > > On Sunday, 30 June 2013 21:15:36 UTC+3, Christopher wrote:
    > >> 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.

    >
    > 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.
    Öö Tiib, Jul 1, 2013
    #10
  11. Christopher Pisz

    Ike Naar Guest

    Re: Quicksort done. Can I get a check on it?

    On 2013-06-30, Christopher Pisz <> wrote:
    > 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.
    Ike Naar, Jul 1, 2013
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    475
    Kai-Uwe Bux
    May 8, 2005
  2. Srikanth Mandava
    Replies:
    1
    Views:
    378
    Michael Hudson
    Feb 19, 2004
  3. CMOS
    Replies:
    1
    Views:
    309
    Jack Klein
    Aug 29, 2006
  4. , India
    Replies:
    10
    Views:
    1,055
    James Kanze
    Aug 8, 2009
  5. Replies:
    6
    Views:
    534
    Tim Rentsch
    Mar 23, 2010
Loading...

Share This Page