Algorithm Research – Quicksort Essay Example

To measure or classify an algorithm according to these two criteria, we measure the algorithm’s computational complexity. The computational complexity of a sorting algorithm is it’s worst, average and best behavior.

Sorting algorithms are generally classified by their computational complexity of element comparisons, against the size of the list. This is represented with what is known as ‘Big O notation’, for example where the ideal behavior is O(n), most algorithm’s behavior is O(nlogn), and bad behavior is O (n). O(n) behavior means that a sorting algorithm would take ten times longer to sort a list of one hundred elements, than it would to sort a list of one thousand elements. O(n) behavior is quadratic behavior, and this would take one hundred times longer to sort a list of one hundred elements, than it would to sort a list of one thousand elements.

In Big O notation, the ‘O’ symbol is an asymptotic upper bound, or the greatest element in a subset of another, partly ordered set. The ‘n’ is the size of the list being sorted. The popular sorting algorithms are dived into two classes, O(n), which are generally slower but simpler, and O(nlogn) which are faster but more complicated. The Quicksort algorithm is of the O(nlogn) class, and makes O(nlogn) comparisons on average.

In worst case scenarios, Quicksort makes O(n) comparisons. In a very simplistic explanation, The Quicksort algorithm sorts a list of data in three steps. These three steps are listed below:

1. Select a ‘Pivot’. The pivot is an element from the list.
2. Reorder the list by putting all elements with values that are less than the pivot, before the pivot; and all elements with values
   

greater than the pivot after the pivot.Elements with values equal to the pivot can go either way. After the list has been reordered in such a way, the pivot will be in its final position, this operation is known as the ‘partition operation’.

The Quicksort algorithm is a comparison sort. Comparison sorts compare the values of elements in a set of data by a single abstract comparison operation, which is most often a ‘less than or equal to’ operation. The Quicksort algorithm is not a stable sorting algorithm.In a stable sorting algorithm, if two elements have equal values, they will maintain their relative order when the list is sorted.

The Quicksort is also massively recursive. “Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way” [http://en. wikipedia.org/wiki/Recursion].

Sorting algorithms can also be classified by the amount of memory space a computer will need to sort the algorithm.The simplest form of the Quicksort algorithm, while being fast, requires (n) extra storage space, which is comparatively not very good. There is however, a more complicated version of Quicksort that uses an in-place partition algorithm. An in-place algorithm is one that doesn’t require extra space to sort the array with sub arrays and such. Instead it swaps the elements around inside the original array and thereby only needing the space of the original array, plus a small amount of working

space for local variables etc as all sorts do.

The in-place version can sort a list using O(nlogn) space on average. The Quicksort algorithm uses what is known as a ‘Divide and conquer’ strategy to sort lists of data. Using the ‘divide and conquer’ strategy, “we must divide the problem into two smaller sub-problems, solve each of them recursively, and then meld the two partial solutions into one solution to the full problem” [http://www2. toki. or.id/book/AlgDesignManual/BOOK/BOOK2/NODE53. HTML]. Another point of interest for the Quicksort sorting algorithm, is that is can easily be parallelized.In computer science, “a parallel algorithm, as opposed to a traditional sequential algorithm, is one which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result” [http://en.wikipedia. org/wiki/Parallel_algorithm].

This means when running on a system with multiple processors, Quicksort can split its sub-set’s to be sorted by individual processors and greatly speed up the time in which it sorts the set of elements.In summary, Quicksort is a comparison sort that is massively recursive, not stable and easily parallelized. Quicksort makes O(nlogn) comparisons on average and at worst makes O(n?) comparisons. Quicksort is one of the fastest sorting algorithms and a very popular choice for sorting sets of data, generally only competing with other sorts for their better worst case behaviors e. g. Heapsort and Mergesort, or when a stable sort is needed eg. Mergesort.