Sorting Algorithms

Another Data Structures assignment required me to write some sorting algorithms and then test them with a few different data structures to compare speed and efficiency of both the algorithms and the data structures.  

I really like seeing what’s really happening so I went a little further just for fun and wrote this program that visualizes these sorting algorithms.  The number of swaps being done in order to sort the data is dramatically different between the sorting algorithms.  

The algorithms:

Selection Sort
Insertion Sort
Shell Sort
Heap Sort
Merge Sort
Quick Sort
Radix Sort
Binary Insertion Sort
Shaker Sort
Brute Force Bubble Sort
Flagged Bubble Sort

Link: GFX_Sorts.zip

image

Minesweeper

A project in my data structures class stipulated that I write a text-based minesweeper game.  Naturally I got a little carried away on adding features, so it has color, sound, and mouse input.  

image

When the player clicks on a cell that’s not adjacent to a mine, there is a cascading reveal that checks all the adjacent cells and recursively reveals them until mines are encountered.  

One of my favorite features is something I inititally implemented for debugging purposes which involves the game displaying these recursive cell reveals.  When you see a large amount of colors during this process, it signifies a large amount of recursion on the call stack.

image

This version of minesweeper is modeled after the classic game that comes with windows.  If you’d like to play, here is a link.  Have fun!

Minesweeper Zip File

Binary

Binary is a number system that can be used to count. For each digit you have 2 possible numbers: 0 & 1.  This is why we refer to binary as Base 2.

Alternately, in decimal( what we commonly use ), for each digit we have 10 possible numbers: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.  We call this Base 10.

We’re used to counting in decimal because we have 10 fingers(and we’re taught that way), but computers are made up of wires and switches that turn off and on(really quickly), so computers use binary.

Counting in binary works exactly like counting in decimal(even though you might not think so at first), but that’s probably just because we might not necessarily think about how exactly it is we’ve been counting for so long.  

Most computers generally measure in bytes.  1 byte = 8 bits, or 8 digits in binary, so in a computer, the data being stored would look something like this:

00000100  10001001  11001000  10110010

Above is 4 bytes, which is a pretty commonly used standard size for storing a number in a computer.  This 4-byte binary value(if it’s being used as a signed number) has a range of –2,147,483,648 to 2,147,483,647.(signed meaning positive or negative)

So how does the computer interpret binary as a number?  Let’s do something simpler.

The following are 4 bit numbers and their decimal equivalents. 

1110  :  14

0001  :  1

1000  :  8

1100  :  12

1111  :  15

Are you seeing the pattern yet?  

Just like when we count in decimal, we start with 1 digit and count to 9; then we go to ten right?  Yes, kind-of… What we’re really doing when counting to 9 is counting the number of ones and every time we start over with counting the number of ones, we count the number of tens.  When we count past 9 tens and 9 ones, we count to 1 hundred, 0 tens, and 0 ones.  That’s 100 right?  Each digit has a name in Base 10, we start at the right with ones, then we have tens, then hundreds, thousands, and so on.  Each one of these places is a “power” ( symbol: ^ ) of 10.  To make 100 for instance, we would say that’s 1 to the power of a hundred.  

Now take a bigger number like 1,263:  it can be counted as follows:

3 times 10^0 + 6 times 10^1 + 2 times 10^2 + 1 times 10^3 =  1,263

It’s exactly the same with binary, only the number of digits grows considerably faster.  

So counting in binary looks like this:

0000  :  0

0001  :  1

0010  :  2

0011  :  3

0100  :  4

0101  :  5

0110  :  6

0111  :  7

1000  :  8 

Lets look at the 4-byte number again, if we start at the very right( and ignore multiplying by 0 ), 

00000100  10001001  11001000  10110010

1 times 2^1 + 1 times 2^5 + 1 times 2^6 + 1 times 2^8 +

1 times 2^12 + 1 times 2^15 + 1 times 2^16 +

1 times 2^17 + 1 times 2^20 + 1 times 2^24 +

1 times 2^27 = 76,138,674

And that’s how you count in binary.

I made a game.

It’s pretty basic, but it has been a fun little project to apply some of the useful concepts I’ve been learning about C++.  This specific project is really just a C project as I didn’t use any object oriented programming, but I’m already working on a more modular game engine based on this little demo.

The idea was to generate a random “star” map on startup and then move around this randomly generated map with a “ship”.  It’s possible to find planets that you can enter which will then teleport you into another randomly generated “world” map which contains portals back to space as well as money which you can collect to win the game.

One of my favorite parts was learning how to include sound in the game.  At the end, the ship will do a little dance to the music, so play to win!

hint: you only need $3750 to win.

This game will only run on windows.

Download the game from the following location:  

https://www.dropbox.com/s/txuxiayqonqsv9b/starmap%20beta.zip

Coding

Here is some pseudocode I came up with in order to display a deck of cards in a console using only ASCII characters.  It might just provide some insight as to how computers work behind the scenes.

Display deck of cards using ASCII characters

   For each row of cards to be displayed,

      

       For each top section of a single card,

          Display top left corner

          For each unit of width,

              Display top

          Display top right corner

       Proceed to new line

 

       For each rank and suit display,

          Display left

          Display rank and suit

          If rank is 10,

              Reduce remaining width to draw by 1

          For each unit of width,

              Display blank space

          Display right

       Proceed to new line

      

       For each middle section of a single card,

          For each card in the row,

              Display left

              For each unit of width,

                 Display blank space

              Display right

          Proceed to new line

      

       For each bottom section of a single card,

          Display bottom left corner

          For each unit of width,

              Display bottom

          Display bottom right corner

       Proceed to new line

The New Tetris - Main Theme (Dubstep Remix)

This is part two of a set of remixes from my all-time favorite Tetris game: The New Tetris. Not only do I think this was and is a perfect take on Tetris, but I always enjoyed and could hardly forget the music. It was so incredible that I couldn’t resist making these remixes. The original composer for The New Tetris is Neil Voss. You can hear is music on soundcloud:  https://soundcloud.com/neilvoss