Sorting Algorithms

Work in progress. Almost all are from Wikipidia:
Quicksort is often faster in practice than other O(n \log n) algorithms.

The steps are:

  • Pick an element, called a pivot, from the list.
  • Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  • Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
  • “Merge sort does about 39% fewer comparisons than quicksort does in the average case; merge sort always makes fewer comparisons than quicksort, except in extremely rare cases”

    Steps are:

  • Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  • Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.
  • Merge sort is highly parallelizable. The drawback is that it requires 2n locations if implemented not-in-place which is more complicated.

    Advertisements
    This entry was posted in Uncategorized. Bookmark the permalink.

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s