SECTION B

1. Sorting Algorithms

Sorting is an algorithm that arranges the elements of a list in a certain order.

It is a very important category of algorithms in computer science and lots of research has gone into this category because it has large usage in almost every program. Sorting can significantly reduce the complexity of a problem.

Sorting algorithms can be classified in several ways. Some of the parameters are:

· The number of comparisons:

Based on this parameter, the sorting algorithms are classified by the number of comparisons. For comparison based algorithms, best case behavior is O (n * log n) and worst case behavior O (n^2)

· The number of swaps:

Based on this parameter, the sorting algorithms are categorized by the number of swaps.

· Memory usage:

Some algorithms need O (1) or O (log n) memory to create locations for sorting the data temporarily and this is another parameter that algorithms can be categorized.

· Recursion:

Based on this parameter, sorting algorithms can be either recursive or non-recursive. There are some algorithms which use both.

· Stability,

· Adaptability.

Another method of classifying sorting algorithms is :

• Internal Sort

• External Sort

There are many sorting algorithms that are used depending on the problem, but the algorithm that I have mostly used during my studies is Shell Sort.

2. Shell Sort Algorithm

I had many projects in the past where I needed to use sorting algorithms. One of them was a project where I had a list of employees, and I needed to sort it based on employees name or their ID, start date of work etc. Given that my list did not have many elements, for sorting I have used the Shell Sort Algorithm.

Shell Sorts breaks the original list into a number of smaller sub-lists, each of which is sorted using an insertion sort. The unique way that these sub-lists are chosen is the key to the Shell Sort. Instead of breaking the list into sub-list with one after other elements, the Shell Sort uses an increment of i, to create a sub-list containing elements that are separated by i elements from each other.

To illustrate better how I used Shell sort, let’s take a list of eight employee IDs.

I start to compare items with a fixed gap, that becomes lesser on each iteration until it gets to 1.

I used an increment of four and created four virtual sub-lists of all values located at the interval of 4 positions. Here these values are {33, 14}, {31, 17}, {40, 25} and {8, 41}.

I sorted Each of these sub-lists by an insertion sort.

After this step, the elements will have this order:

Although this list is not completely sorted, something very interesting has happened. By sorting the sub-lists, I have moved the items closer to where they actually belong.

Then, I take interval of 2 and this gap generates two sub-lists: {14, 25, 33, 40}, {17, 8, 31, 41}.

I compare and swap the values, if required, in the original array. After this step, the elements will have this order:

Finally, I sort the rest of the array using an interval of value 1. Shell sort uses insertion sort to sort the array. Below is the step-by-step presentation of how sorting will take place:SECTION C

6. Performance

The basic Shell Sort algorithm is among the earliest sorting methods to be discovered

and is among the easiest to implement.

Shell Sort it is a sorting algorithm invented by Donald L. Shell (1959). This sort is a generalized version of insertion sort. It is an in-place comparison sort.

This is the first algorithm which got less than quadratic complexity among comparison sort algorithms.

Since in this algorithm insertion sort is applied in the large interval of elements and then interval reduces in a sequence, therefore the running time of Shell sort is heavily dependent on the gap sequence it uses.

• Average case complexity: O (n* log2n)

• Worst Case Space Complexity: O (n)

Shell Sort has O (n * log n) best case time. The best case is when the array is already sorted. The number of comparisons, in this case, is the length of the array.

Worst case complexity for this algorithm depends on the gap sequence. Best known: O (n * log ^ 2n).

This algorithm uses insertion sort on the large interval of elements to sort. The interval of sorting keeps on decreasing in a sequence until the interval reaches 1. These intervals are known as gap sequence.

This algorithm works quite efficiently for small and medium size array as its average time complexity is near to O (n).

Although faster than algorithms with Big O (n ^ 2), for large lists, it’s not the best solution.

Shell sort is not as efficient algorithm as some of the other fast algorithms such as merge sort, heap sort, and quicksort. But it is a simple algorithm that provides a good solution for a list of fewer than 5000 elements. The best case in Shell is when the array is already sorted in the right order because the number of comparisons is less.

The main advantage of Shell sort is that the list can be sorted for a gap greater than 1 and thus making fewer exchanges than insertion sort.

To test the time this algorithm needs to sort an array based on the number of elements, I have made a program that calculates it.

This program simply measures the time in milliseconds that the algorithm needs to sort an array.

The test arrays, are initialized with random values in the range from 0 to 1000. Each test is repeated 3 times, with different random values. The number of elements in the array starts from one thousand and increases per one thousand.

Based on the results obtained from this test and shown in the chart, it is seen that the time it takes for the algorithm to sort increases continuously with the array elements increase.

These results prove that this algorithm takes a lot of time to sort an array with many elements.

But for an array with a few elements is pretty fast because there are not many comparisons.

Taking into consideration that the code is very short and the time it takes to sort is short for a small array of elements, this algorithm has been very suitable to use in my assignments.

If we compare Shell Sort with other algorithms, it is easy to see that it has a better performance than all sorting algorithms that were discovered before it.

Obviously, after this algorithm, many other faster algorithms have been discovered, but Shell Sort remains the first which got less than quadratic complexity.

Some of the algorithms that are faster than Shell Sort are listed in the following table: