CODEWITHSUNDEEP
c++sorting
ulak blade
ulak blade

Reputation: 2665

Insertion sort issues?

I'm just now trying out different sorting algorithms to find out how they work.

I'm looking at this one:

template< typename Iterator >
void insertion_sort( Iterator First, Iterator Last )
{
    Iterator min = First;
    for( Iterator i = First + 1; i < Last; ++i )
        if ( *i < *min )
            min = i;

    std::iter_swap( First, min );
    while( ++First < Last )
        for( Iterator j = First; *j < *(j - 1); --j )
            std::iter_swap( (j - 1), j );
}

It's the Insertion Sort and it sorts them from smallest to largest, however I have 2 issues:

  1. Reversing any comparison sign doesn't change the sort order to descending.
  2. When implementing it with my own container, it never sorts the last element. Maybe I didn't get how Begin and End should work for a container? This is how I make them:

If I have a dynamic array container that has an unsigned int size and a T* data, Begin returns an iterator that has a pointer to data[0] and End returns an iterator with a pointer to data[size - 1]. If I make end to instead return data[size], it works fine, however if the size is equal to the allocated capacity, that would overflow the buffer. So the presented insertion sort algorithm is incorrect then? I got it from this site:

http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Insertion_sort#C.2FC.2B.2B

Upvotes: 0

Views: 130

Answers (2)

Frank
Frank

Reputation: 1785

About question 1: I think it should work if you reverse all comparison signs that involve dereferenced iterators, i.e., replace

if ( *i < *min )

by

if ( *i > *min )

(one might also replace the name 'min' by 'max' then to avoid confusion), and

for( Iterator j = First; *j < *(j - 1); --j )

by

for( Iterator j = First; *j > *(j - 1); --j )

These are the comparisons that compare the actual data.

About question 2: usually, an 'end' iterator refers to the position behind the last actual item that you want to sort. Standard algorithms (such as yours) will never dereference this iterator, so no overflow will occur.

Upvotes: 3

dornhege
dornhege

Reputation: 1500

The iterators pointing to an end() are one past the last element, so that you'd usually loop through them like:

for(Iterator it = begin(); it != end(); ++it) ...

Your iterator implementation thus stops one before that last and is the culprit.

It might be a good idea not to test everything at once, i.e. a custom algorithm with custom iterators. You can use a stl container to test the algorithm and an stl algorithm to test your container.

Upvotes: 1

Related Questions