Sorting a set of items in a list is a task that occurs often in computer programming. Often, a human can perform this task intuitively. However, a computer program has to follow a sequence of exact instructions to accomplish this. This sequence of instructions is called an algorithm. A sorting algorithm is a method that can be used to place a list of unordered items into an ordered sequence. The sequence of ordering is determined by a key. Various sorting algorithms exist, and they differ in terms of their efficiency and performance. Some important and well-known sorting algorithms are the bubble sort, the selection sort, the insertion sort and the quick sort.
The bubble sort algorithm works by repeatedly swapping adjacent elements that are not in order until the whole list of items is in sequence. In this way, items can be seen as bubbling up the list according to their key values.
The primary advantage of the bubble sort is that it is popular and easy to implement. Furthermore, in the bubble sort, elements are swapped in place without using additional temporary storage, so the space requirement is at a minimum. The main disadvantage of the bubble sort is the fact that it does not deal well with a list containing a huge number of items. This is because the bubble sort requires n-squared processing steps for every n number of elements to be sorted. As such, the bubble sort is mostly suitable for academic teaching but not for real-life applications.
The selection sort works by repeatedly going through the list of items, each time selecting an item according to its ordering and placing it in the correct position in the sequence.
The main advantage of the selection sort is that it performs well on a small list. Furthermore, because it is an in-place sorting algorithm, no additional temporary storage is required beyond what is needed to hold the original list. The primary disadvantage of the selection sort is its poor efficiency when dealing with a huge list of items. Similar to the bubble sort, the selection sort requires n-squared number of steps for sorting n elements. Additionally, its performance is easily influenced by the initial ordering of the items before the sorting process. Because of this, the selection sort is only suitable for a list of few elements that are in random order.
The insertion sorts repeatedly scans the list of items, each time inserting the item in the unordered sequence into its correct position.
The main advantage of the insertion sort is its simplicity. It also exhibits a good performance when dealing with a small list. The insertion sort is an in-place sorting algorithm so the space requirement is minimal. The disadvantage of the insertion sort is that it does not perform as well as other, better sorting algorithms. With n-squared steps required for every n element to be sorted, the insertion sort does not deal well with a huge list. Therefore, the insertion sort is particularly useful only when sorting a list of few items.
The quick sort works on the divide-and-conquer principle. First, it partitions the list of items into two sublists based on a pivot element. All elements in the first sublist are arranged to be smaller than the pivot, while all elements in the second sublist are arranged to be larger than the pivot. The same partitioning and arranging process is performed repeatedly on the resulting sublists until the whole list of items are sorted.
The quick sort is regarded as the best sorting algorithm. This is because of its significant advantage in terms of efficiency because it is able to deal well with a huge list of items. Because it sorts in place, no additional storage is required as well. The slight disadvantage of quick sort is that its worst-case performance is similar to average performances of the bubble, insertion or selections sorts. In general, the quick sort produces the most effective and widely used method of sorting a list of any item size.
- Thinkstock/Comstock/Getty Images