Less known than others presented here sorting algorithms, but quite interesting one for how it pre-processes the data. Comb Sort is basically an improved bubble sort, which allows it to run in O(n log n) time in average cases. Unfortunately, the worst case is still O(n2). The main idea behind the Comb Sort is to … Continue reading Comb Sort
Category: algorithms
Insertion Sort
Another elementary but interesting sorting algorithm. Its time complexity is O(n2), so every time the size of an array to be sorted is doubled, the efforts quadruple. Insertion sort starts from index 1 by remembering its value and comparing to the value under index 1 - 1. If the value under previous index is less … Continue reading Insertion Sort
Bubble Sort
Bubble sort is a really simple sorting algorithm, that has O(n2) time complexity. Its name comes from the fact that, if you would imagine an array to be sorted standing vertically, then (depending on the direction of sorting) the smallest or the biggest values would always bubble up one by one, until the whole array … Continue reading Bubble Sort
Problem: Find all pairs
This is a simple but interesting problem, which can be easily solved with O(n2) time complexity, but it demands to reverse your logic to solve it in O(n) time. Problem: Let's say, there is an array arr=[1, 2, 3, 4, 6, 7, 8, 2, 5] Now we need to find all pairs of numbers, which … Continue reading Problem: Find all pairs
Merge Sort
Merge sort is similar to quick sort as it makes use of recursion and Divide and Conquer technique. It complexity is O(n log n) as the pivot point is always in the middle. The main idea behind merge sort is to keep breaking down the problem until we reach such small units that by the … Continue reading Merge Sort
Quick Sort
Quick sort is making use of recursion so if you are not familiar with recursion, I recommend going through my Introduction to recursion post. This algorithm also makes use of a technique which is called Divide and Conquer. The basic idea behind it is, instead of dealing with an instance of a problem at its … Continue reading Quick Sort
Introduction To Recursion
Recursion occurs when something is defined in terms of itself. Recursion has applications in many disciplines, but what we focus on here is application in Computer Science. So for our purposes we define a recursion when a function calls itself. Many algorithms make use of recursion, so it is good the get the grip on … Continue reading Introduction To Recursion
Selection Sort
Selection sort is quite simple, but because is simple is then easy to understand. It's complexity is O(n2) so it's not very suitable for production quality code and there are (obviously) other faster sorting algorithms, but it's good to get a grip of it and treat it as an introduction to sorting algorithms. Basically this … Continue reading Selection Sort
Difference Array
Today I am going to introduce you to a pretty cool algorithm, which would allow you to update multiple ranges in an array in O(n) time ! Let's say you got an array, and you need to update ranges of it with given values. So as an input you would receive a two dimensional array … Continue reading Difference Array
EasyAlgorithms 