The Basic Sorting Algorithms Computer Science Essay

In the following scientific report, the basic sorting algorithms will be discussed and examined. Timing will be done on the different sorting algorithms and experiments will be done to see which of the different sorting algorithms are the most efficient. Assumptions will be made on which sorting algorithm is the most efficient and then compare the results to see if the right assumption were made.

We will discuss the reasons why each sorting algorithm is efficient and under which conditions are efficient. A brief explanation of each sorting algorithm will be given to get the basic idea what it’s all about. Then a brief conclusion will be done to round of the scientific report

Bubble sort is probably one of the most popular and simple sorting algorithm. It is often used as a programming exercise for beginners because it is relatively easy to grasp and understand. The problem though is that it’s not very efficient, therefore bubble sort only gets used once in a blue moon. There are more efficient sorting algorithms used in real application and that will be discussed in a later stage.

It basically two steps that happen in bubble sort, which are:

It compares each pair of adjacent elements from the start of the array and, if they are not in the right order, they get swapped

If at least one swap has occurred the you repeat step one until no numbers gets swapped

Here’s a graphical example how Bubble Sort works.

Bubble sort – http://www.algolist.net/Al We going to sort an array {5, 1, 12, -5, and 16} using bubble sort.

Selection sort just like bubble sort is one of the simplest of the sorting algorithms and it works very well with small files.

The concept of this algorithm is quite simple. The array is said to be divided in two parts, a sorted part and an unsorted part. At the beginning the sorted part is empty while the unsorted part is the whole array. At every step the method/algorithm finds the smallest element in the unsorted part of the array and the ads it to the end of the sorted part of the array. When the unsorted part becomes empty the algorithm stops.

Insertion Sort just like bubble and Selection is one of the most basic and most common sorting algorithms around. This sorting algorithm is more efficient than the other to because it has fewer comparisons than the other two, but this will be discussed in more detail later on.

Think about how you sort a deck of cards. You start from the beginning and work through the deck and as you find cards that aren’t in the right order you remove them and place it in the right order, and you do the this until all the cards are in the right position and your deck is sorted This is the main idea behind Insertion sort.

The Method

Insertion sorts “breaks” up the array in two parts, sorted and unsorted. At the start the sorted part of the array only contains one element. Each step the algorithms runs, it expands the sorted part of the array by one and then places the first element of the unsorted region and places it in the right place in the sorted area. This will carry on till the whole array will be a sorted array.

The illustration on the right hand side shows step by step how insertion sort works.

Shell sort

Shell sort algorithm is one of the eldest sorting algorithms out there and was invented by D.L Shell in 1959[3]. It is quite effective and easy to comprehend. The sorting algorithm follows two standard procedures:

1. It arranges the data into a two dimensional array

2. The columns of the array will then be sorted

Once the procedure has been concluded, the resultant data sequence is placed into another two dimensional array, but with less columns. The columns are then sorted and the above procedure is repeated until a single sorted column is leftover [3].

MERGESORT

The merge sort algorithm uses divide and conquer approach. The algorithm firstly divides the data sequence into two halves, sorts the two halves and then combines them together to form a sorted set of data sequences. [4]

Figure 0-4 http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm

In the above figure it illustrates the basic merge sort process. It starts by dividing the unsorted data sequence “a” into to unsorted data sequences “b” and “c”. The data sequences “b” and “c” are then sorted with recursive calls to form b’ and c’. Once the two halves are sorted, they are combined to form a sorted data sequence namely a’ [4].

Quick sort

Quick sort is the fastest sorting algorithm when it comes to large elements in an array. Quick sort has to make use of recursion, because of the way quick sort, sorts the elements.

The way quicksort works is that there are three pointers, namely a left, right and pivot pointer, the pivot pointer is the most important one. The Left pivot will point to the most left element in the array and the right to the most right element in the list. For the pivot any number can be chosen, but its normal practice to make the first element your pivot.

The steps:

Pivot and left pointer points to the 1st element in the list and right to the last element

The pivot pointer will now compare the object that it’s pointing at with the one that the right pivot is pointing at.

If the right pointer objects are smaller than the pivot then the two objects swap, it is important to note that the pivot will always point to one number, so if that number moves so does the pivot, the right and left pivot stays in its respectable place.

If the right pointer object is not smaller that pivot, the right pivot will just move left until a smaller one is found

Once the pivot swaps with the right pivot , the pivot and the right pointer will point to the same object, therefore the right pivot will not move anymore now the left pointer will move one right

The left pointer and the pivot will now compare, and it the left pointer object is bigger than the pivot object then it will swap, and the pivot will now join the left pointer. This will then let the right pointer move one left

This will carry on until all three pointers point to the same object, this means that the object is in its perfect position, to the left of this object no number will be bigger than it and to the left no number would be smaller.

Once it found the first object in its perfect place, it will then move to the left hand side of that object

It will follow all the above steps with the left side.

One’s the left side is all sorted it will then go to right side of our first perfect number and sort the right hand side with the same procedure

(To see a Illustrative example see Appendix A)

Sorting Algorithms

Figure -Sorting Algorithm

Figure 1 above shows us the relationship of time (ms) and the number of objects the sorting algorithm has to sort. There are 5 sorting algorithms measured in this experiment namely Bubble sort, Insertion Sort, Selection Sort, Double Insertion and Double Selection sort. As can be noticed from the graph above s that all five sorting algorithms has the same trend but some just increases more than the other and sometimes by quite a substantial amount. First thing noticeable is that if we sort little objects, let’s say less than 2000 objects, then it does not matter what algorithm we use all of them are at about the 0ms mark. Only when we get to about the 10000 objects mark, then only the sorting algorithms really shows who the best is.

As we can see from the graph is that Bubble Sort is the least sorting Algorithm and is basically just used to explain the sorting procedure to new comers to the programming language. Bubble selection and Double selection are very similar when it comes to efficiency. The most efficient sorting algorithm by far is the Insertion Sorts. As can be seen by figure 1 Double insertion is the most efficient and it all works on how the sorting algorithm sorts the array which is discussed in the abstract portion of this report.

Experimental Procedures

What was needed to run the experiment

The apparatuses needed for his experiment where a Computer, Visual studio C#, and a user that has been tutored for Sorting algorithms

How experiment was executed

Code where write for each sorting algorithm in a method in a specific program. A new timing class was created, to have something to time how fast or slow the different sorting algorithms gets sorted. Then the method for each 5 sorting algorithms gets executed and run five times to get an average, to eliminate errors that might have been caused. After all the data has been recorded, a graph was plotted [1] . This graph was then evaluated

Problems that arise

The main problem that happened was, each time the programme ran the results weren’t always constant. And if the programme was not a dedicated programme (i.e. the only programme running at the time) then the values went haywire. This problem was fixed by forcing the visual studio to run a garbage collector and collect all the garbage, to make sure that when programme runs all the processing power is used for the programme so the times will be more accurate.

Conclusion

In this report five different sorting algorithms where discussed. Each one was investigated and briefly explained how they work, and why each one is efficient in their own right. As the experiment when on it was noticed that some sorting algorithms are less efficient than other’s and that had all to do with how each sorting algorithm works.

When figure-1 was examined, it was concluded that Bubble sort was the least efficient of the different sorting algorithms and that Double insertion Sort was the most efficient of all the sorting algorithms.

From this we can conclude that Bubble sort is best used just to explain or introduce the sorting algorithm to a new student. As soon as you want to have an efficient sorting algorithm the Double will be the best because less time will be spent to sort the objects in the array

References

http://wiki.answershttp://www.c.happycodings.com/Sorting_Searching/code17.html

http://stackoverflow.com/questions/832765/whats-a-bubble-sort

http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm

http://www.algolist.net/Algorithms/Sorting/Bubble_sort

http://www.algolist.net/Algorithms/Sorting/Selection_sort

http://www.algolist.net/Algorithms/Sorting/Insertion_sort