In this weeks article I'm going to be covering several common sorting algorithms. Sorting algorithms are a great example of using a variety of approaches to solve a problem as well as a great topic for discussing time complexity. Having knowledge of multiple sorting methods is also helpful because each can best best depending on the scenario, there is no clear best algorithm.
In this article I'm going to cover:
- Bubble Sort
- Insertion Sort
- Merge Sort
- Quick Sort
Helper Methods
A common theme we are going to be using in our algorithms is comparing two different elements in an array and swapping their locations. To follow the DRY (don't repeat yourself) principle of coding lets put these in helper methods.
Not that we can easily access these methods let's start sorting.
Bubble Sort
The bubble sort is a great introductory sorting algorithm due to its simplicity. It works in a way that many humans would go about sorting.
The bubble sort compares every pair of adjacent elements, arranging them in ascending order. Similar to how you would go about organizing a hand of playing cards. The origin of the name comes from the image of larger values rising to the top of the array like a bubble floating to the surface of water.
Runtime: O(n^2) to O(n)
Insertion Sort
As the name implies for the insertion sort we are going to be inserting each element from an array into out output array. To do this we'll compare the first and second element of our array and decide if the second should be inserted before or after the first. Then we compare the third element to the second and first, etc.
Runtime: O(n^2) to O(n)
Merge Sort
Merge sorting is a method that utilizes the divide and conquer method. It starts by dividing the original until every element is separated. From there it merges the small arrays so the elements are in order.
For the implementation of this method we use two separate functions. The first method recursively divides the given array, the second sorts them.
Runtime: O(n^2) to O(nlogn)
Quick Sort
Quick sort is one of the most popular sorting methods and also utilizes the divide and conquer method. The algorithm creates two smaller arrays, and then picks an index from the array. It then compares the rest of the elements to the chosen element and places smaller elements on the left and larger elements on the right. This is done recursively until the sorting is done.
Runtime: O(nlogn)
I plan on continuing to dive into sorting algorithms and hope to touch on selection sorting, bucket sorting, heap sorting, counting sorting, and radix sorting.
Thanks for reading! You can find the code for this post here.
Oldest comments (0)