Make and Makefiles

Make and Makefiles

The compiler is one of the most important parts of the C programming environment. I can write Java until I'm blue in the fingers without ever having to actually USE the java compiler. Sure, it is being used in the background all the time with eclipse, but IDEs make me stupid. I don't actually learn what is happening when I click the pretty little 'run' button, I just see the output.

GNU Make is a tool that you will use constantly. It is used to generate executables and other non-source files from your source code. It does this using rules you set up in a makefile. Using the makefile, you'll be able to build and install the program you have written. So lets take a look at make files.

To set up a fairly simple example of a make file we can use the hello.c file for our C 'program.' What better example to use than Hello World.

I also included a very simple Makefile along with hello.c.
You should be able to use the commands

make hello

to build the executeable

make clean

to clean the files up

When you run make clean, it actually runs the 'clean:' target of the Makefile, which  removes the 'hello' executable.

Makefile

hello.c

That's a very simple introduction on how to make a basic Makefile. Soon, I'll write another blog post describing some of the more in depth pieces of Makefiles.

Learn C the Hard Way :: Excercise 1

Learn C The Hard Way : Excercise 0

The idea behind exercise one is to get your C development environment set up. Since I use Archlinux, my notes here will mainly focus on a Linux setup for C programming. An OSx setup could be fairly similar, but a windows one would probably differ a significant amount.

Zed Shaw, the author of the book talks about how using an Integrated Development Environment makes you a lazy programmer. Is exact quote is that "An IDE, or "Integrated Development Environment" will turn you stupid." I couldn't agree more.  While it is difficult to begin learning a new language, let alone learning to program from scratch, using an IDE will give you lazy habits. To me, the difference between using an IDE against using command line tools manually is like installing Linux via the Ubuntu installer or installing an Archlinux system from the command line. It is daunting and much more difficult to do it the manual way, but you will have a greater understanding and appreciation for what goes on beneath the surface in the future.

If you're just starting out programming on Linux, it might be a good idea to use a text editor like Gedit instead of a more difficult Vim or Emacs. Personally I love Vim. Mostly it's because I'm lazy and don't want to move my hands away from the keyboard.

As for your development tools, generally any text editor should work. The great thing about Linux is it basically IS your development environment. Since Linux uses C heavily (the  kernel is written almost entirely in C) it contains all the tools your really need to start hacking some  C code.


Useful links::
vim wiki on changing vim color schemes
http://vim.wikia.com/wiki/Switch_color_schemes

some vim plugins
http://spf13.com/post/the-15-best-vim-plugins/

download some vim plugins
http://vim.sourceforge.net/index.php

55 Lessons of C

Fellow hackers, I am embarking on a read through of Zed Shaw's Learn C the Hard Way. While I'm working through the book (and it's 55 exercises) I will be tracking my progress through the book. Starting with the first exercise.

A little background on my programming experience and why I want to learn C. I was a computer science major in college and learned C++ in school. I've dabbled with different languages from time to time and mainly use Java now due to my job as a Software Engineer. Java is a powerful language, but I find myself not really knowing what is going on behind the scenes. That coupled with a desire to get into Linux Kernel programming has lead me to a decision of learning C the hard way - by getting my hands dirty with Vim and the command line.

Kernel Race

Like a lot of programmers, I run off of two different machines. I have both a desktop and a laptop. My desktop was one built for gaming about two and a half years ago. At the time I thought it was the speediest of machines, which wasn't entirely true. It's still a fairly beefy machine though. My laptop has fairly "similar" specs and has been a pretty decent dev machine as well. The interesting part is that for my Desktop I went AMD, and for my laptop I went Intel.

It's kind of difficult to compare the two processors I am going to pit against each other. AMD has always had more processing power, but less cache. Intel has always had less processing power, a little bit more cache and hyperthreading. This should be an interesting comparison.

System	Maker	Proc Model	Clock Speed	Num Cores (Physical/Virtual)	Memory
Custom Desktop	AMD	Phenom II x4 955 BE	3.2 GHz	4/4	8 Gb
Lenovo T420	Intel	Core i5 2520M	2.5 (3.2) GHz	2/4	8 Gb

Operating System Specs

System	Linux Distro
Custom Desktop	Ubuntu 12.04 Standard install
Lenovo T420	ArchLinux with DWM

Let's see how they compare! For my test I compiled the linux kernel version 3.6.0 using the default config that came with my Ubuntu 12.04 install on my desktop.

Interestingly, after the first test the kernel compile times were relatively similar. I thought that the desktop would waste my laptop, but the times were very close.

LENOVO T420 :: Core i5 2520M
=-=-=-=-=-=-=-=-=-=-=
real 29m7.789s
user 101m37.572s
sys 7m35.954s

DESKTOP :: PHENOM II x4 955 BE
=-=-=-=-=-=-=-=-=-=
real 28m26.318s
user 74m27.363s
sys 7m1.530s

Review :: Linux Mint Debian Edition 201204 with MATE

I had been using Ubuntu Linux for several years when they released the Unity interface, and like many Linux enthusiasts I was put off by the "mobile" centric view Ubuntu had adopted. After being finding myself without a distro, home I settled into the comfortable familiarity of Linux Mint. It is build off of Ubuntu so it was a logical next step after giving up Ubuntu. I used Mint for a while and eventually made it to ArchLinux and now I have found myself wandering back to Linux Mint, but with a pleasantly surprising twist of Debian.  

Linux Mint, an Old Familiar Friend

Linux Mint Debian edition has almost everything I am looking for in a distro. The familiarity of debian commands from my Ubuntu days, the rolling distribution updates of Debian (and ArchLinux) plus my the nostalgic window manager that I never could give up - MATE (a Gnome 2 fork) . After having two weeks of using LMDE as my primary distribution on my Lenovo T420, I have been very pleasantly surprised. MATE has the stability and programs that Gnome 2 had, although it takes a bit of getting used to since the applications have different names.

Performance

Overall I have been very impressed by the performance of LMDE and MATE. Compared to the latest version of Ubuntu and Gnome 3 in general, the memory usage of LMDE is lower. My setup which I use as my my development station rarely uses more than 1.5 GB of RAM and usually hovers around 675 MB when I'm doing normal internet browsing. The availability of graphics drivers isn't quite as nice as Ubuntu or other version of Linux Mint which will display a notification if proprietary drivers are available. The same drivers are available for LMDE, you just have to install them yourself through the command line or synaptic package manager. For those of you who have a hybrid graphics card like Nvidia Optimus, LMDE works surprisingly well with bumlebee to run everyday programs through the Intel integrated graphics and switch to the Nvidia chip for more power.

MATE

Mate is the desktop manager of LMDE. After Gnome stopped supporting Gnome 2, the MATE project picked up where Gnome left off and began forking the existing Desktop Manager and application suite that came with it. They tweaked it into something called MATE. Besides the names of applications, you won't notice much of a difference between MATE and Gnome 2, which is absolutely fantastic. I grew up on Gnome 2 and haven't been the same sine I was forced off of it. The developers on the MATE project have done a great job bringing the useability back to the desktop. If you happen to have the opposite opinion that I do, LMDE comes with Linux Mint's Cinnamon desktop installed as well. It is as simple as selecting a different session from the login menu to add a bit of spice (pun intented) into your mint.

Battery Life

The length of your battery life depends greatly on the version of the kernel you are running (to find this run the command uname -r). LMDE currently has kernel version 3.2 which has brought some great improvements since early kernel versions. Out of several distros I have had installed on my laptop recently, LMDE has the longest battery life by at least an hour. If you are running a debian based system and want to take advantage of the latest and greatest kernel, take a look at my tutorial and compiling the kernel on Debian based systems.

Applications

LMDE comes with Linux Mints standard applications and philosophy on a distribution. The Linux Mint creators believe that a distribution should just work, which means they include almost everything you need out of the box.  The main applications are:

• Firefox for web browsing
• Pidgin for instant messaging
• Xchat for IRC
• The LibreOffice suite for documents
• Pluma (a gedit continuation) for text edititing
• Banshee for music

And much much more. One of the best things about Linux Mint is that if you are missing some application you would like to install, the Software Manager is only a few clicks away on the start menu.

Updating

Yes, updating the system has its very own section. My absolute favorite thing about LMDE is the Debian-based rolling release. This means that unlike Ubuntu where you have to upgrade EVERYTHING in your system to get the next version, you simply roll everything together. Basically once you install LMDE, you won't have to upgrade to another version again just to get the latest and greatest updates. This is a fantastic approach to software updates. It remains painless and easy to upgrade.

Summary

If you are just getting into linux, Linux Mint Debian Edition may not be the best choice for you. It takes more command fu in the console and knowledge of linux in general than running the standard version of Linux Mint. If you are more experienced LMDE is a fantastic desktop that brings the performance and stability of the Gnome 2 desktop back from the grave. The rolling release update style keeps takes the headache of major release upgrades away and replaces it with simple and normal updates. LMDE comes out of the box ready with flash and other codecs for listening to music and has a great repository of applications should you need anything else. I still haven't decided which distro is the right one for me, but Linux Mint Debian Edition has passed my stress test and checklist for my main Operating System. Thanks for reading and happy hacking!

Fixing minecraft with DWM and Arch Linux

In DWM minecraft doesn't work correctly, due to Java not recognizing DWM as a window manager, minecraft will appear something like this.

The fix is quite easy. Install the wname package using pacman and set the window manager name to something java will recognize.

# pacman -S wmname

# wmname LG3D

This is not a permanent change, so it is a good idea to add it to your .xinitrc file in your home directory

Geek Code

What is the geek code?

The geek code gives geeks a way to tell other geeks where their experiences and interests are. It's basically a programmatic way to sum yourself up by code. It is worth checking out.

For those of you who have never heard of the geek code, here is a link: http://www.geekcode.com/geek.html

My geek code.

For those of you who wish to see what my geek code looks like.

------BEGIN GEEK CODE BLOCK------
Version: 3.1
GCS/M/MU d- s++:-- a-- C+++(++++)$ UL+++ P+ L+++>$ E--- W++ N? o? K- w++ !O !M V? PS+++ PE+ Y+ PGP> t 5 x+ R+ tv+ b++ DI+ D++ G++ e++> h r+++ y+++
------END GEEK CODE BLOCK------

Linux Dual Monitor Script

As some of you may know, I run am running Arch Linux on my Lenovo T420. Being a programmer, I often use a second monitor. It took me a little while to figure out how to get this auto-configured on boot in Arch, but I've come up with the following script.



This script will autodetect if you have a secondary monitor (in my case VGA1) connected to your laptop. And set it up your screens accordingly using xrandr.

To get it to run at boot, I simply include it in my .xinitrc file in my home directory.

Feel free to use the script, although you may have to change the screens accordingly.

Top picks from the Ludum Dare game programming competition

If you don't know what the Ludum Dare game development competition is, you should definitely go check it out. It is free and anyone can join. You get 48 hours to create a game and then post it on their site. People can create accounts on the site and then vote for their favorite games.

I made a list of some of my favorites after paging through the submissions for a couple hours. (there are 891 entries currently)


Alone in the Gloom - hulahulahest

It is the dawn of the 20th century. A Cambridge scholar and explorer has led a team to the depths of the South American jungle to investigate a newly discovered temple complex claimed to predate the Olmec by several centuries, showing evidence of stonework thought beyond the capabilities of preclassical Mesoamerican masonry. As they begin to explore the strange temple, our professor accidentally falls into a pit and is separated from the group. All alone, he must find his way back to the surface, and maybe score some fascinating pieces of research data while he is at it...

This is a fun little game with some decent graphics.  You play as a gentleman with a monocle who is investigating a temple. There are keys and small puzzles that you have to solve your way through in order to get out. The graphics were very "SNES Zelda" - esque and were fairly pleasing. Overall it was a decent game with good gameplay. It actually has a story which is more than a lot of the submissions in this competition can say.


WEIRDLY ALONE. - xilefian

You work for Nicholas Snowwe, the most famous art collector in the country. He has purchased an old museum that has had no visitors for over ten years. Inside is a fresco by the painter Harld Forche. Find it for me.

This retro looking game looks like it came straight off one of the original gameboys. As you make your way through the museum, you run into different obstacles that require different items to get past them (logs can be burned with your lighter.) One tip: press z to sprint in the direction you are facing, otherwise it will take you ages to move anywhere.

A Gravekeeper - downsider

 ...a Gravekeeper who enters a crypt one night after hearing stories about a treasure inside

Although it doesn't have any sound, A Gravekeeper was a fun game to play through. It is a short platformer with good graphics and fairly solid game play. Basically you are dropped into a crypt and as you continue through you eventually find a gem and the cave starts collapsing. You eventually find you're way to the end of the cave and you win. Short and sweet. It doesn't offer much in terms of gameplay as the level is quite short, but it looks amazing and could really be expanded well.

Dungeons of Solitude - Knighty

Your only friend has wandered into the Dungeons of Solitude and has not returned. Can you survive the dangers of this place alone to find your friend?

This game was very well done. It is very reminiscent of a NES or SNES dungeon crawler. As you make your way through the dungeon, you find items (sword, throwing knives etc.)  that will be used to make it through to the next level. The sounds was a nice addition to the game, although there is no music the sound effects were well done.  The enemies who look like balls of goop were a nice addition. And generally just move towards you after they are aggroed. It was an enjoyable game to play that gets quite difficult as you progress through the levels.

Shaped - sendmorepeople

 A game from a two-man team about being alone, looking for others, and being shaped along the way.

This game is easily one of my favorites. The kind of like one of those match the shape games for kids except on steroids. In Shaped you start as the shape in the picture, your goal is to find the shape that matches you. You aren't left to searching though, as you can press E to send out a sort of tracer that will find your friend. Once you find your friend you simply bump into him and are tasked with finding the next one. Carefully make your way to the next shape without bumping into the others!

An all around great game that is simple and easy to play. The music in the background is superb and the gameplay is unique and relaxing.

Minicraft - Notch

 The goal of the game is to kill the only other sentient being in the world, making sure you'll be alone forever.

Game:
Although Notch created a great game, it would have been nice to see something branching away from Minecraft.Overall Minicraft is a fun little adventure with much the same feel as Minecraft. You can cut down trees to get wood and craft things at your crafting table. It is enjoyable to play and very similar to minecraft. Watch out for the zombies!

Source:
The real plus to minicraft is the code that Notch wrote. The source code is freely available on the Ludum Dare website.
The code for Minicraft is very well done. You can tell that Notch is a brilliant programmer. I had the opportunity to watch his live feed on twitch.tv during the competition. As a Java programmer, it was amazing to see the amount of skill and focus he was able to conjure up during the event. Notch's code is a great example of Java game code. If you are a Java programmer looking to get into game development but don't know where to start. I would suggest using Notch's code as a starting point.

T420 - Remap Back / Forward Keys

My Lenovo T420 has two keys above the arrow keys that I almost never use. By default they are forward and backward keys for browsing the internet. I decided to remap them to End and Home. This isn't too difficult.

To do this simply use the following terminal commands:
use xev to find the keycode for the key you would like to change the mapping of
use this link to find what you want the key to actually do
Use xmodmap to map the two together.

xmodmap -e 'keycode 167=End KP_1 KP_1 End'
xmodmap -e 'keycode 166=Home KP_7 KP_7 Home'

LWJGL Setup with Eclipse

I recently decided to try my hand at some game programming and decided to try and use the Light Weight Java Game Library (LWJGL)

It took me a little while to figure out how to get it set up in eclipse. Here is how.
Download lwjgl.zip from here

One you've created a new project in eclipse, add the .jar files like you normally would by right clicking on the project -> properties. Click on the Java Build Path tab and then Libraries. Add the jar files by clicking on the "Add Jars..." button.
The next step is what through me off. Make sure you click on the arrow next to lwjgl.jar and fill in the native library location to point you toward the native files that came with lwjgl (.so files in linux and .dll files for windows)

Hopefully this helps!

Building the Linux Kernel on Debian Based Systems

So you want to build the Linux kernel from scratch, but don't know where to start?
Wikipedia describes the Linux kernel as

The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software.

If you are using a debian based system like Ubuntu or Linux Mint, building your own kernel isn't very difficult. I put together a short tutorial to that is fairly easy to follow and should make the process less painful.

Prerequisites:
In order to download, build, and install a custom kernel you will need the following packages installed.
1. Git - a fast, scalable, distributed revision control system with an
unusually rich command set that provides both high-level operations and
full access to internals.
2. kernel-package - a package used to make kernel compilation more automated and less painful.
3. fakeroot - runs in a command environment at pretends to have root privileges for file manipulation. Useful for creating archives with files inside that have root permissions.
4. buid-essential - contains an informational list of packages which are considered essential for building Debian packages. This package also depends on the packages on that list, to make it easy to have the build-essential packages installed.
5. ncurses-dev

sudo apt-get install git-core kernel-package fakeroot build-essential ncurses-dev

1. Change to the home directory

cd ~

2. Clone the mainline kernel git tree

git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git

3. CD to the linux directory

cd linux

4. Copy the kernel config from your existing kernel using uname -r for your currently loaded kernel

cp /boot/config-'uname -r' .config

5. Update the config file. The default answer to these questions will suffice.

make oldconfig

yes "" | make oldconfig to accept the defaults

6. Clean the kernel source directory

make-kpkg clean

7. Build the linux-image and linux-header .deb files. This is where the actual work takes place. It could take some time. On my machine with an i5 processor it took 15 - 30 minutes.
The concurrency level of this piece can be set manually. Basically it lets you allocate how many processors you would like to utilize in making the kernel image

CONCURRENCY_LEVEL=`getconf _NPROCESSORS_ONLN` fakeroot make-kpkg --initrd --append-to-version=-custom kernel_image kernel_headers

8. Change the directory level one up and install the two .deb packeges created<blockquote>

sudo dpkg -i linux-image-<insert custom kernel name here>.deb

sudo dpkg -i linux-headers-<insert custom headers name here>.deb

9. Make the kernel bootable

cd /lib/modules

sudo update-initramfs -c -k <insert kernel module name here>

10. Make sure grub recognizes your custom kernel when you reboot.

sudo update-grub

You're done! Reboot and see if it worked.

Links:
Summary of Linus's Kernel on Git

Linux - Scripts for hardware

Toggle Volume

    <keybind key="XF86AudioLowerVolume">
     <action name="Execute"><execute>ossmix vmix0-outvol -q -- -1</execute></action>
      </keybind>
    <keybind key="XF86AudioRaiseVolume">
       <action name="Execute"><execute>ossmix vmix0-outvol +1 -q</execute></action>
    </keybind>

Linux - Script to Toggle Touchpad

Short script to toggle the touchpad on/off in Linux.
Comes in real handy if you want to map it to a keybinding in openbox.

#!/bin/bash
if [ $(synclient -l | grep TouchpadOff | awk '{print $3}') == 1 ] ; then
synclient touchpadoff=0;
else
synclient touchpadoff=1;
fi

In openbox I mapped this to my fn + f8 key (the default button to toggle the touchpad on my T420)
I added the following to ~/.config/openbox/rc.xml

<keybind key="XF86TouchpadToggle">
<action name="Execute">
<startupnotify>
<enabled>true</enabled>
<name>toggletouchpad</name>
</startupnotify>
<command></command>~/bin/toggletouchpad.sh
</action>

If you aren't sure what the key presses are that you want to use, there is a program called "xev" that will tell you the xevents keybindings, mousebindings etc. to the actions you are doing.

Lenovo T420 - Linux - Toggle Touchpad

Here is a helpful little script that toggles the touchpad on or off in Linux.

#!/bin/bash
# My first script
SYNSTATE=$(synclient -l | grep TouchpadOff | awk '{ print $3 }')

# change to the other state
if [ $SYNSTATE -eq 0 ]
then
synclient touchpadoff=1
notify-send "Touchpad" "disabled"
elif [ $SYNSTATE -eq 1 ]
then
synclient touchpadoff=0
notify-send "Touchpad" "enabled"
else
notify-send "Error" "Couldn't get Touchpad status from synclient"
exit 1
fi
exit 0

Thinkpad T420 and Arch Linux

I finally got Archlinux installed on my T420 without much of a headache.

Hardware and General Notes:
I turned off the Nvidia card (I have optimus on this laptop) and I am currently running with only the integrated Intel HD 3000 card. I used the xf86-video-intel driver for the card and everything works great. Sometime in the future I'm going to try to get Bumblebee working.

Sleep is working great.

I haven't tested the webcam or microphone.



thinkpad-acpi:
thinkpad-acpi gives you all kinds of nifty tools to use for controlling different aspects of the Thinkpad series laptops.

This comes default with most kernels (it comes with Arch anyway.) To enable it edit /etc/rc.conf with your favorite text editor and under the MODULES section add the following:

MODULES=(thinkpad-acpi)

Now (probably after a restart) you should be able to control some of your thinkpad's hardware. One of my favorite things is controlling the thinklight through the command line using the following commands:

echo 255 > /sys/class/leds/tpacpi\:\:thinklight/brightness

echo 0 > /sys/class/leds/tpacpi\:\:thinklight/brightness

This will toggle the thinklight on and off. There are all sorts of uses for this in bash scripts etc. There is a nice plugin for pidgin that uses the Thinklight and flashes whenever someone sends you an IM. A nice little addon.

Thinkpad T420

I recently ordered a new Thinkpad t420 off of Lenovo's website. I figured it was about time to replace my Asus eeepc with an actual notebook, something that I could actually use for programming. I wanted something durable that would last a while, and of course something that could handle Linux well. I opted for the t420 and took advantage of some of Lenovo's black friday deals.

It shipped out on Dec. 2 and should arrive by Dec. 8.

Specs:

CPU:
Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz
GPU:
Intel Corporation 2nd Generation Core Processor Family Integrated Graphics Controller (rev 09) nVidia Corporation Device 1057 (rev a1)
Audio:
ALSA Timer Device
Audio:
ThinkPad Console Audio Control
Audio:
HDA Intel PCH (CONEXANT Analog)
Audio:
HDA Intel PCH(HDA Intel ALSA hardware specific Device)
Audio:
HDA Intel PCH
Network:
Loopback device Interface
Network:
RTL8188CE 802.11b/g/n WiFi Adapter
Network:
82579LM Gigabit Network Connection


I haven't heard the best of things on Lenovo's shipping, but we will see what it looks like. Currently the shipping information is as follows
EDIT:
Wow, the t420 had quite the trip from hong kong! Final shipping times.
Tri-City, IN, United States 12/08/2011 12:46 P.M. Delivered
12/08/2011 4:15 A.M. Out For Delivery
12/08/2011 3:42 A.M. Arrival Scan
Indianapolis, IN, United States 12/08/2011 1:42 A.M. Departure Scan
Indianapolis, IN, United States 12/07/2011 6:45 P.M. Arrival Scan
Louisville, KY, United States 12/07/2011 3:41 P.M. Departure Scan
12/07/2011 2:35 P.M. Import Scan
12/07/2011 2:00 P.M. Arrival Scan
Anchorage, AK, United States 12/06/2011 11:50 P.M. Departure Scan
12/06/2011 1:48 P.M. Arrival Scan
Chek Lap Kok, Hong Kong 12/06/2011 9:27 P.M. Departure Scan
Chek Lap Kok, Hong Kong 12/03/2011 8:30 A.M. Origin Scan
Hong Kong 12/02/2011 7:04 A.M. Order Processed: Ready for UPS

Nvidia Optimus and Linux - Notes

I have a Lenovo Thinkpad t420 coming in the mail soon. I opted for the version with the Nvidia Optimus technology which switches between an Nvidia 4200m (?) graphics card and the Intel HD 3000 integrated graphics. The Linux support for Optimus isn't entirely there, but I've found a couple interesting fixes.

Basically you can either (from the BIOS) turn off the Nvidia card completely or turn off the Intel HD Graphics completely.
A better option (in my opinion) is the Ironhide project which allows you to launch applications using the Nvidia card and uses the Intel HD Graphics for everything else.

Basically I'm keeping some notes in the bottom of this post and will write a tutorial and review later for Linux on the t420 with Optimus.
Notes:
Ironhide for Ubuntu
Ironhide
Ubuntu Forums Ironhide how-to
Ironhide PPA Ubuntu

Archlinux AUR search for "Bumblebee" : http://aur.archlinux.org/packages.php?O=0&K=bumblebee&do_Search=Go

General Thinkpad / Notebook tips and scripts
Thinkwiki Thinklight
ArchWiki - T420
CPU Frequency Scaling

Bubblesort a Linked List

Sometimes when you're programming you just need to sort an array. You could use a built in function like any old schmuck; or you could whip out a shiny sorting algorithm and show off a little bit. Ok, so in all reality using a built in sorting function is most likely more efficient than building your own, but it is important to know what is going on behind the built in abstraction layer.

Today I am going to look at the bubblesort sorting algorithm. The main aspects I will be looking at are the Big-O analysis and general benchmarking.

Before I start I should give a basic summary of what big-O notation is and why it is used. Big-O notation is a way that computer scientists and mathematicians express the limits of a certain algorithm. Basically they show how an algorithm reacts to large data sets.

If you would like to read more, Wikipedia has a great article found here.
big-O

BubbleSort
Bubblesort is a simple "exchanging" algorithm. It starts at the first element of the data set and compares it to the second, if the first is greater it swaps them. It will then compare the second element to the third and so on until it reaches the end of the set. At this point we know that the last element is the largest element. The algorithm will then start at the first two elements of the set again and compare until it reaches the element before the end of the list (since we already decided that was the largest.) This pattern continues until the list is sorted.

As you may have guessed, this is not a very efficient algorithm for sorting a large data set. Bubblesort is rarely used due to this fact, however it does offer several small advantages - it uses a relatively small amount of code and can reach decent efficiency with an almost sorted data set.

Here is the code to the bubbleSort method I came up with. It requires the files LinkedList.java and ArrayFromFile.java which I posted about a week ago. The real meat of the program is in the method bubbleSort(LinkedList list). The main method is only there for testing purposes.

download a zip file with all the files you need to run the program

Code:

Bubblesort Stats:
Big-O best case: n
Big-O average case: n^2
Big-O worst case: n^2
Benchmark (100 elements in the collection): 7844 milliseconds (about 7.8 seconds)
This benchmark will likely be something completely different for you since it will be run on a different machine.

Linked List

Linked lists are important topics in computer science. The theory behind them is something that computer science students learn in classes like data structures and algorithms. I have created a linked list for you to study. It is fairly simple, but has the necessary methods to expand to it with a BubbleSort algorithm etc.

The following picture explains the idea behind a linked list.

Basically you have a list of these things called Nodes that are linked together. Each node is a bucket of sorts that contains a piece of data. A Linked List is a group of these buckets strung together one at a time. The head bucket is linked to the 2nd bucket, the 2nd bucket is linked to the 3rd and so on until you get to the tail bucket which isn't linked to anything.

Currently I am implementing the following methods on the linked list:
-addAtHead(Object) - creates a node and adds it to the beginning of the linked list as the head Node
-addAtTail(Object) - creates a node and adds appends it to the end of the list as the tail Node
-addAtIndex(Object) - creates a node with Object as its data and adds the node at the index
-addAtIndex(Node) - adds the node at the index
-deleteAtIndex(int index) - deletes the node at the index
-switchWithNext(int index) - switches the current index with the one right after it. This is used by the bubble sorting algorithm.
-printList() - prints out the whole LinkedLIst
-find(Node) - returns index
-find(index) - returns Node
-getSize

To Do:
-Sorting by different algorithms(bubble sort, selection sort etc.)