Article 35 - Programming Sorting Algorithms

There are many algorithms for sorting, which includes quick sort, merge sort, bucket sort, selection sort, insertion sort, and bubblesort. I will even dive a little into external sorting.

Quick Sort

Quick sort reduces the number of sorts by trying to partition the number of elements to sort into two equal sections during each recursion. Though, in some cases, the partitions may be skewed such that all the elements lie on one side. This gives us a worse case of O(N^2) run time, but the expected runtime is O(NlogN).

During each recursive call, a partition is chosen (randomly, statistically, or through numeric analysis) and the current list to sort is split into two groups. One group contains values less than, while the other group contains elements greater than or equal to the partitioned value. Then a recursive call is invoke on each list.

At the base case, when there are three elements, a simply comparison is used. Once the recursive calls return, a sorted list is returned. In each recursive call, it is assumed that the list to sort is reduced by half.

Merge Sort

This sort is extremely popular, because it produces expected and worse case running time of O(NlogN).

Given a list to sort, we repeatedly divide the list in half during each recursive call and invoke merge sort on each of the two list. At the base case, we simply return the current element.

After each recursive call returns (still within the current recursion), a merging of the two sorted separate list is performed. This is done by comparing the two list and taking in order the smallest from each list until it is sorted. This list is returned for the previous recursion to use, repeatedly.

Bucket Sort

This is one of the fastest sorts available, if the list has a small finite range of values. For example, sorting based on the ages of a group of people.

This type of sort partitions the group into buckets, normally by some integer value. Then a sort using some fast sorts such as quick sort or merge sort is used to sort a smaller list of numbers in each buckets.

It is expected that the running time is O(N), which is linear.

Selection Sort

This is not a heavily used sort due to its weaker running time of O(N^2).

In this sort, a pointer is used to iterate through the entire list. For each element that the pointer is currently at, another iteration through the rest of the list is used to scan for the smallest number. Then, a swap is performed. The sort algorithm repeats this for each element in the list.

An interesting factor is that the part of the list that was already visited by the pointer is already sorted. This can be useful for applications that do not have to wait for the entire list to be sorted before using.

Insertion Sort

This is often times better than selection sort. It works, somewhat, backwardsly compared to selection sort.

Like selection sort, there is a pointer that iterates through the entire list. For each iteration, the pointer checks the if the current element is smaller than the previously element, if it is, swap them, continue until we find an element smaller.

The running time is O(N^2), but in the best case, O(N), that is when the list is already sorted.

Bubble Sort

This is a terrible sorting algorithm. Its runtime is O(N^2), always.

With this sort, each element is swapped with the next element if it is larger. This is repeated N times. For example, if the largest element is the first element, we need to shift this largest element to the end, which requires N swaps.

External Sort

External sort is very similar to merge sort. In fact, it relies on the ideas that define merge sort. Instead of sorting in memory, sorting is performed using disk operations.

There are three primary procedures. First we perform individual sorting in n batches, where each batch of elements fit in memory. We sort these and save them back to disk.

Then we perform merge sort by loading every two batches and writing them to a buffer. Thus, every two batches should be sorted.

Finally, we repeat the merging of the batches for every four batches, eight batches, and so forth, until the the list is sorted.

Comments (14)

Posted by anonymous - miumiu ?????? at Friday, January 25, 2013 12:20 PM

Wanna try online shopping? Here are stylish but gorgeous ?????? ?? in perfect quality.
miumiu ?????? http://miumiusale5.webnode.jp/

Posted by anonymous - ?????? ?? at Friday, January 25, 2013 4:04 PM

Get ready to find some exciting new fashion (?????? ???) for yourself.
?????? ?? http://www.monclersaleinfo.jp/

Posted by anonymous - ?????? at Friday, February 1, 2013 10:22 AM

find miumiu,chloe,prada in the fashion style and low price. More other products can be found here in website. ?????? http://www.tiffany1837-jp.com/

Posted by anonymous - chloe at Tuesday, February 5, 2013 1:36 PM

find miumiu,chloe,prada ,Following a few latest visits here, even so, is becoming more and more chic. chloe http://www.chloe-mall.net/

Posted by anonymous - amazing site at Saturday, March 2, 2013 6:59 PM

Ba1FsL Great, thanks for sharing this post.Really thank you! Fantastic.

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.