Data Structures

Binary Search

Binary Search Binary search relies on a divide and conquer strategy to find a value within an already-sorted collection. The algorithm is deceptively simple. Pretend I was thinking of...

Binary Search Tree

A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any...

Merge sort

Merge-sort is based on the divide-and-conquer paradigm. It involves the following three steps: Divide the array into two (or more) subarrays Sort each subarray (Conquer) Merge them into one...

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than...

Selection Sort

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse...

Bubble Sort

Bubble Sort The algorithm works by comparing each item in the list with the item next to it, and swapping them if required. In other words, the largest element...

Bucket Sort

Bucket Sort Suppose we need to sort an array of positive integers {3,11,2,9,1,5}. A bucket sort works as follows: create an array of size 11. Then, go through the...

Sorting

Sorting is ordering a list of objects. We can distinguish two types of sorting. If the number of objects is small enough to fits into the main memory, sorting...

Asymptotic Notations

The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on machine specific constants, and doesn’t require algorithms to be implemented...