Author Topic: Insertion sort.  (Read 8902 times)

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Insertion sort.
« on: July 28, 2011, 03:51:55 AM »
I've been using insertion sort a lot for my current project, primarily because it's really simple to implement. I thought I might share it here for those who haven't heard of it. It is really simple to use, and good for small linked lists like all of us have in our roguelikes. Anyway, here it is in C++:

Code: [Select]
void Sort()
{
int i;
int j;
vector<string> Names;
string Name;
for(i=0;i<Names.size();i++)
{
Name=Names[i];
for(j=i;j>-1;j--)
{
if(Names[i]>Names[j])//Switch this for ascending versus descending.
{
Names.erase(Names.begin()+i);
Names.insert(Names.begin()+j+1,Name);
break;
}
else if(j==0)
{
Names.erase(Names.begin()+i);
Names.insert(Names.begin(),Name);
break;
}
}
}
}
Viola! Two loops, and the list is 100% sorted. Here's how it works:

The list is walked from left (0) to right (size of list). At each location, the list to the left is assumed to be sorted, and to the right is assumed to be unsorted. For each element, we take it from it's current unsorted position, and walk backward over the sorted list to find the element's correct location. We then insert the element in it's correct location on the left, and continue our journey to the right.



Single pass, requires no additional list storage, runs in O(n) in already sorted arrays, and easy to implement! Enjoy.

PS: Don't use it on lists of 1000+, unless they're already partially ordered.

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: Insertion sort.
« Reply #1 on: July 28, 2011, 08:01:55 AM »
Sharing code is always welcome here.

I personally would use Name.sort() with probably a operator> overriding  somewhere and then traverse the list to see where to insert it.

Cheers.

Edit: My above answer was for std::list, not std::vector, oops. Really who ever used std::list anyway? Replace Name.sort() with std::sort(Names.begin(), Names.end()); actually shown below in Z's post.
« Last Edit: August 17, 2011, 07:43:11 AM by corremn »
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: Insertion sort.
« Reply #2 on: July 28, 2011, 02:10:13 PM »
1.  Why do you call these "linked lists"? Vectors are not linked lists. This algorithm would not work efficiently for linked lists.

2. For sorting a vector<string> Names wy not just use sort(Names.begin(), Names.end()) which is already implemented in STL and efficient? (You can also use sort(a.begin(), a.end(), compare); and define a function bool compare(const T& a, const T& b) { return a<b; } )

The only bad thing I see about that is that it performs a bit worse on an array that is almost sorted already.

3. If you cannot use STL sort for some reason, and care about the time used to implement stuff rather than efficiency (or you know that the array is almost sorted already), the following is shorter:

Code: [Select]
  int i = 1;
  while(i < (int) Names.size())
    if(i && Names[i] < Names[i-1]) swap(Names[i], Names[i-1]), i--;
    else i++;

It is even faster in some situations.

Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
Re: Insertion sort.
« Reply #3 on: July 28, 2011, 05:18:02 PM »
For the record, this is not the algorithm I learned as Insertion Sort.  When I was studying CS this  algorithm was called Bidirectional Bubble Sort.  

That said, it does appear to implement what Wikipedia calls Insertion Sort. 

And, yeah, probably not the best thing to use on any large-ish data sets.  Like its cousin Bubble Sort, It's O(n2) where good general-case sorting algorithms are O(n log(n)).

« Last Edit: July 28, 2011, 05:31:30 PM by Bear »

Psiweapon

  • Rogueliker
  • ***
  • Posts: 334
  • Karma: +0/-0
  • Im in ur rougeliekz, pixelling ur tielz!
    • View Profile
    • I Lovemaking Tiles
Re: Insertion sort.
« Reply #4 on: July 29, 2011, 03:29:32 PM »
Moonspeak!  :o
The invisible hand is a lie, the fiendish dogma of the market cultists. Lest the apostasy grows strong, their blood god will devour each and everyone, pious and infidel alike.

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Insertion sort.
« Reply #5 on: July 31, 2011, 02:12:45 AM »
1.  Why do you call these "linked lists"? Vectors are not linked lists. This algorithm would not work efficiently for linked lists.
Sorry, vectors are much better for this than linked lists, due to being dynamic arrays. This is really an algorithm that works best when the data can be accessed from an array of some sort, rather than a linked list.
Quote
2. For sorting a vector<string> Names wy not just use sort(Names.begin(), Names.end()) which is already implemented in STL and efficient? (You can also use sort(a.begin(), a.end(), compare); and define a function bool compare(const T& a, const T& b) { return a<b; } )
Of course, using sort is always better (provided that the list is legitimately unsorted), but it requires that what you're sorting implement the operator < or that you implement a comparison function. This is actually probably the easiest way to go, but I never seem to want to bother implementing the operator or writing a comparison function. Really, though, this is probably the best way to go..
Quote
3. If you cannot use STL sort for some reason, and care about the time used to implement stuff rather than efficiency (or you know that the array is almost sorted already), the following is shorter:

Code: [Select]
 int i = 1;
  while(i < (int) Names.size())
    if(i && Names[i] < Names[i-1]) swap(Names[i], Names[i-1]), i--;
    else i++;

It is even faster in some situations.

That's a really nice algorithm! I love how small it is. I never thought to allow i to decrement all the way to 0 if needed. Very cool! I'll have to use this one in the future.

Quote from: Bear
For the record, this is not the algorithm I learned as Insertion Sort.  When I was studying CS this  algorithm was called Bidirectional Bubble Sort.  
Bidirectional bubble sort gets all the way to the end of the list sorting forward, and then sorts from the end backwards to the start, going back and fourth until the list is sorted (swapping only neighbors), according to wikipedia.
Quote
And, yeah, probably not the best thing to use on any large-ish data sets.  Like its cousin Bubble Sort, It's O(n2) where good general-case sorting algorithms are O(n log(n)).
The algorithm I gave actually runs at O(n) if the list is sorted, and very close to that if the list is only slightly unsorted, but yes, it does get to O(n^2) unfortunately. :(
« Last Edit: July 31, 2011, 02:21:25 AM by Elig »

guest509

  • Guest
Re: Insertion sort.
« Reply #6 on: August 16, 2011, 02:36:12 PM »
Moonspeak!  :o

  Lol Psi! This is sorting code. Like for taking a bunch of numbers and putting them in order from smallest to largest. You get into it about your 2nd or 3rd term of computer science. I think they are using linked lists (they are like an array but can be made bigger or smaller during run time, they have no set size...usually). If I remember right making linked lists was what my last test was on during my first year of college computer science.
  Can you believe I got all the way through 2 years of computer engineering but ditched it...now I'm a failing attorney haunting forum sites and using Gamemaker. What a world....

Ari Rahikkala

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 64
  • Karma: +0/-0
    • View Profile
    • Email
Re: Insertion sort.
« Reply #7 on: August 22, 2011, 09:47:08 AM »
Yeah, the way this is written it's only fast for vectors and not lists, or might not work on lists at all, depending on whether your list class has an operator[]. STL's lists don't. The iterator they provide by default isn't a RandomAccessIterator either though, so STL's sort can't sort STL's lists either. But that's why STL's list class provides a sort method of its own :).

And Elig, if you can't be bothered to write comparators, the solution is obvious: Use Haskell ;). (seriously, you just write "deriving (Eq, Ord)" and boom, you've got a full set of equality and order comparators for your datatype. It's incredibly convenient.)