Posts tagged: source

Open Sourcery

Recently I came across a gem of a site on the interwebs. I found 1889ca (Is it just called 1889? Maybe 1889 books?). It’s the home of some great stories, very much in the same light as Cory Doctorow’s works. But there’s a twist. These are children’s books. Not all of them (keep the little ones away from the Steam Duck series), but the majority are aimed at the “sub teenager” age range.

Recently, and much to my surprise, MCM, the man behind the site, launched an open source project: TorrentBoy. I felt like this was something I had to take part in. Who wouldn’t love to help drive the evolution of a wise-cracking boy who turns into a super-hero by tapping into the latent power that engulfs all of Earth’s inhabitants? I know I would!

So when MCM asked for the Twitter-Public’s opinion on which CMS (Content Management System) we’d recommend, preferably one built like a wiki, I just had to suggest the use of PmWiki. I like PmWiki. The documentation accompanying it is great. And, Lo! Check out the TorrentBoy site now! I wasn’t expecting to be able to contribute the way that I had, but I did.

So I’m not sure if this is a public awareness call for bored geeks out there who wish to contribute to an open source project (much like TorrentBoy, or any other project). If you want to help contribute to a project, you can. You’re not about to get your head torn off like you might if you play QuakeLive (people who play Quake can be scary mean!).

Sorting – An Introduction

If I recall correctly, sorting is a subject touched upon in the first year of a computer science (or computer information systems) student’s curriculum. The professor doesn’t go into too much depth with sorting, as there is much to get into. The professor wouldn’t normally focus on algorithm complexity (Big-O notation) or discussing data structures or recursion. Rather, the professor might merely mention sorting algorithms, name a few and probably show how bubble sort works.

If I were a professor, and I’m not so the world has that going for it, I’d reveal bubble sort to the class via pseudo-code. The class would get a homework assignment (keeping in mind this is a first year course). The assignment: convert the pseudo-code into a working program. But this isn’t about what I’d do if I were teaching a class, this is about helping you if you are ever presented with this assignment!

The following pseudo-code has been borrowed from wikipedia.

procedure bubbleSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 1 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped
end procedure

That might look a little more complicated than you (or I) would like but with a little practice stuff like that turns into something that can be easily read.

This is what that pseudo-code turns into (and probably what you came here for in the first place) :

int Bubblesort(int arr[], int length) {
  int hold=0;
  int i=0;
  int keepSorting=0;
  do {
     keepSorting = 0;
     for(i=0;i<length;i++) {
        if (arr[i] > arr[i+1]) {
           hold = arr[i+1];
           arr[i+1] = arr[i];
           arr[i] = hold;
           keepSorting = 1;
        }
     }
  } while (keepSorting);
  return 1;
}

That’s C code, not too different from the Java that a professor might use in a first year course. The boolean from the pseudo-code has been replaced with an integer. Bubblesort is fed an array as well as the length of the array. The variable hold is just a temporary variable to help in swapping side-by-side indexes in the array. Anyway, that will get your homework done.

Two other very common sorting algorithms are Insertion sort and Quick sort. You’ll learn a little more about them in the next article on sorting.

One more thing. Here’s a quick comparison of the three sorting algorithms and how long it takes each of them to sort a bunch of unsorted numbers.

Sort Time Comparison

Staypressed theme by Themocracy