Posts tagged: computer science

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

Lottery Simulator

Back in the first programming course I took at the university level (intro to java) I got to thinking about the lottery. I ended up writing a simple program that did the following:

  1. Read in 6 numbers provided by the user (between 1 and 49, as per the lottery in my province).
  2. Have the program pick 6 numbers at random and compare them to my pick.
  3. Loop until the program matches my pick and return the number of loops.

I didn’t have a point in the exercise, I just wanted to see if I could do it. At that point it was one of the more complicated things I had accomplished and I’d done it for myself, not for grades (which made it more awarding).

I’ve lost the source code for that program, but I’d recently become interested in that simulation, again. I’ve rewritten it in C and made it scalable with the pool of numbers to pick from (ie, 49) as well as the quantity of numbers to pick (ie, 6).

I’m interested in finding the average number of games to play, chance of winning a lottery based on pool size and pick size. In the standard lottery in Canada the pool size is 49 and the player picks 6 numbers. It’s a suckers’ tax. I’ll let you in on a secret. So far, the average number of games needed to play in order to win that lottery is 13.5 million games. Like, for example, when Coke tells you that you have a 1 in 6 chance of winning another bottle of Coke I am telling you that you have a 1 in 13,500,000 chance of winning the lottery. (edit: I’m aware that this is accomplished with the function n choose k that we learn in calculus. Googling 49 choose 6 gives the result 13,983,816)

I’ll get more into that later. Expect a “Science” page to open up here in the next little while with a portal to the simulation. So far I’ve written the code to run the stats, process them into mean, minimum and maximum values, and to plot the data and save them as nice images. The program also compiles the results into it’s own html page for easy viewing. About all that’s left now is to have the program index the pages and link them together for easier navigation.

And of course, the source code will be made available to all.

Staypressed theme by Themocracy