Insertion sort.

[Ex]

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]

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.

[Z]

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]

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(n²) where good general-case sorting algorithms are O(n log(n)).

[Psiweapon]

Moonspeak! 

[Ex]

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.

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

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.

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.

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.

[guest509]

Moonspeak! 

  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]

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