Sorting

Comparison and Benchmarking of Sorting Algorithms using Java

This is my graduation project for Council Rock High School South and Middle Bucks Institute of Technology

Name	Bubble Sort	Double Bubble Sort	Insertion Sort	Comb Sort	Selection Sort	Quick Sort
Applet Displaying Algorithm
Full Source of Each Applet	Bubble Sort	Double Bubble Sort	Insertion Sort	Comb Sort	Selection Sort	Quick Sort
Description of Algorithm	Bubble Sort	Double Bubble Sort	Insertion Sort	Comb Sort	Selection Sort	Quick Sort

I was unable to make quick sort refresh the drawing while inside of the algorithm due to its recursive nature.

Introduction:
My graduation project was built to create an online repository of knowledge on the topic of sorting algorithms. The plans for this repository include java applets of various sorting algorithms. Also, I will include the source code for each applet on the web page for people to view. I will also describe how each of them work.

Research:
I researched a great deal to find as many search algorithms as possible. For my research I first turned to the internet. I found a website with over 20 different algorithms on it. The list of algorithms was a good place to start from but it didn’t explain how each of them worked. It gave me a good idea about the wide variety of sorting algorithms.
Next I turned to my father’s personal library of computer programming books. He had a book called The Art of Programming, Volume 3: Sorting and Searching. The entire book is dedicated to sorting algorithms. It explains each in great detail. It also provides code examples of how each algorithm would work.
I used the class’s reference book, Java 2: A Beginners Guide, to guide me through the programming of the applets. I used it to learn the syntax of Java so I could create the programs. Also it contains the quick sort algorithm already coded in java.
For specific information on applet coding I had to turn to another book. I used Java 2: Game Programming. This was one of the most difficult things for the project as I have never had any experience with applet coding before. It was one of the things I had to learn to create this project.

Future Development
There are several areas where I could improve the website in the future. Since Computer Science is an ongoing field of research there will inevitably be new and original sorting algorithms. In the future as new algorithms are discovered I could make applets to show how each works. This would further my goal of making a repository of sorting algorithm knowledge. I also could run each algorithm hundreds of times to find an average time per run to find the efficiency of each algorithm. I would use this information to find which algorithm is the best. A graph could be made for each algorithm for increasing sets of data. Ultimately, I could overlap the different graphs and find the best algorithm for varying data set sizes.
Another way to help people to look for information on sorting algorithms would be to have a page for each algorithm. In addition to the page with the source code for the applet, I could have a link to a page describing how the code works. Some are simple and will not need much explanation, but others will be more lengthy. This will be in addition to any comments I put in the source code. These are just a few ideas I have to for future development to my website.

Conclusion
I have learned a lot more doing this project then I had expected from when I started in November, 2003. Sorting algorithms is a much larger field of study then I had expected. I expanded my knowledge in areas such as applet coding and the timing mechanism using Java. I hope that in the future, someone else in dire need of information on the topic will stumble on my website through Google and reference me in his report.

Bubble Sort
This is the simplest of all sorts. Since it is so simple though, it usually is the least efficient sort. When sorting, it goes though the list one step at a time. It compares the first value with the second value. If the second value is lower then the first, it reverses the order of the two values. Then it moves to compare value 2 and 3. It then repeats going through the entire data set until no switches are made on one complete pass.

Double Bubble Sort
Double bubble sort is very similar to bubble sort. Instead of passing through the information in only one direction, it alternates the direction each pass through the data set. For example, at first it will ascend through the data until it reaches then end. Then it will descend until it reaches the beginning. It repeats this until there are no switches made on one complete pass.

Insertion Sort Insertion sort is very different from the bubble sort methods. It takes the next value in the list of data and then finds where it fits in with the data that is already sorted. Let’s say that the data already sorted is 12,45,67,83 and the next number is 32. It squeezes the number between 12 and 45. It steps upwards like this until it reaches the end of the data.

Comb Sort
Comb sort is similar to bubble sort besides one major difference. The difference is that instead of comparing adjacent values, it compares values separated by a certain number. Just like how the teeth on a comb are separated. Each pass through the data the “teeth” on the comb get closer. It keeps on going through the data until there are no switches in one complete pass.

Selection Sort
Selection sort is probably the closest thing to what a real human would do when it sorts things. It makes one pass through the data and finds the lowest value in the data set. It then puts that in the beginning. Then it makes another pass through the data and finds the new lowest value. It then puts that after the first value. It keeps doing this until the number of moved data is the same as the data set size, until there is no more unsorted data.

Quick Sort
    Quick sort is a very unique sorting algorithm. It takes the first number and finds all numbers smaller then it below it and all numbers larger then it above it. It continues to separate the data like this until there is only one number that is smaller and/or bigger then it. To explain:
At first        It picks 45 as a separator    Then it picks 73 as a separator
45                13                13
13       45                45
73        73                52
52        52                73
98        98                98