Sorting Algorithms

A Quick Overview

Saturday, December 12, 2015

Sorting algorithms put elements of a list in a certain order, with most working by comparing the data being sorted. There are many different sorting algorithms and they are often classified to help you understand the advantages and limitations of each one. Some ways to classify the algorithms are by computational complexity in terms of the list's size, memory usage, recursion, stability, and the general method used for sorting. To optimize the use of algorithms that require input data to be in sorted lists, i.e. search and merge algorithms, it is necessary to use efficient sorting.

Insertion Sort

Insertion sort iterates over an unordered list of elements and assumes part of the array is sorted. For each iteration it removes one entry, finds the location it belongs in, and inserts it into a sorted part. Insertion sort repeats until no input elements remain and is good for sorting arrays that have less than 100 items.

Insertion Sort Animation Example
"Insertion-sort-example-300px" by Swfung8 - Own work. Licensed under CC BY-SA 3.0 via Commons.

Selection Sort

This algorithm works by scanning an array for the smallest unsorted item and then swapping it with the first element. Then it looks for the next smallest element and swaps it with the second element. This continues until the entire array is sorted.

Selection Sort Animation
"Selection-Sort-Animation" by Joestape89 at the English language Wikipedia. Licensed under CC BY-SA 3.0 via Commons.

Bubble Sort

The bubble sort algorithm repeatedly steps through an array by comparing adjacent items and swapping them if required. This process repeats until it makes a pass all the way through the list without swapping any items.

Bubble Sort Animation
"Bubble-sort-example-300px" by Swfung8 - Own work. Licensed under CC BY-SA 3.0 via Commons.

Merge Sort

A merge sort is another comparison based sorting algorithm and is based on the divide-and-conquer paradigm. It divides the entire dataset into subarrays, each having one element. Next it compares every two elements and swaps them if the first should come after the second. Then it merges these sublists to create new sorted sublists. This process continues until one sorted list is produced.

Merge Sort Animation
"Merge-sort-example-300px" by Swfung8 - Own work. Licensed under CC BY-SA 3.0 via Commons.

Quicksort

Quicksort is the most popular sorting algorithm and is also based on the divide-and-conquer paradigm. It picks the average element known as a "pivot" item. Then it partitions the entire dataset in half by adding items to the sublist "less than pivot" or the sublist "greater than pivot" and puts the pivot item between the two lists. It repeats this process on the left side of the list until it is comparing only two items and left side is sorted. After the left side is sorted it performs the same process on the right side and does this until the complete list is sorted.

Quicksort Animation
"Sorting quicksort anim" by en:User:RolandH. Licensed under CC BY-SA 3.0 via Commons.

Helpful Resources to Learn More About Sorting Algorithms