What is linear data structure and what are common operations to perform on it?
What is an average case complexity of Bubble Sort?
What examples of greedy algorithms do you know?
What are some examples of divide and conquer algorithms?
What are some examples of dynamic programming algorithms?
Why we need to do algorithm analysis?
What is the difference between Linear Search and Binary Search?
What is asymptotic analysis of an algorithm?
Name some approaches to develop algorithms
What is Circular Queue and why will you use one?
Why is Insertion sort better than Quick sort for small list of elements?
Tell me something about Insertion sort?
List some advantages of Insertion Sort
How Insertion sort and Selection sorts are different?
What is Merge Sort and how it works?
Is there ever a good reason to use Insertion Sort?
Is there any advantages of Bubble Sort?
What is Tim Sort and how would you compare it with Quick Sort?
Why is Quick Sort better than Merge Sort?
What is stability in sorting algorithms and why is it important?
Data structure availability may vary by programming languages. Commonly available data structures are:
- list,
- arrays,
- stack,
- queues,
- graph,
- tree etc.
A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
Linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. Linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list.
- Worst-case performance
O(n) - Best-case performance
O(1) - Average performance
O(n) - Worst-case space complexity
O(1)iterative
In theory other search algorithms may be faster than linear search (for instance binary search), in practice even on medium-sized arrays (around 100 items or less) it might be infeasible to use anything else.
Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output.
A linear data-structure has sequentially arranged data items. The next item can be located in the next memory address. It is stored and accessed in a sequential manner. Array and list are example of linear data structure.
The following operations are commonly performed on any data-structure:
- Insertion − adding a data item
- Deletion − removing a data item
- Traversal − accessing and/or printing all data items
- Searching − finding a particular data item
- Sorting − arranging data items in a pre-defined sequence
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
Bubble sort has a worst-case and average complexity of О(n2), where n is the number of items being sorted. Most practical sorting algorithms have substantially better worst-case or average complexity, often O(n log n). Therefore, bubble sort is not a practical sorting algorithm.
The below given problems find their solution using greedy algorithm approach:
- Travelling Salesman Problem
- Prim's Minimal Spanning Tree Algorithm
- Kruskal's Minimal Spanning Tree Algorithm
- Dijkstra's Minimal Spanning Tree Algorithm
- Graph - Map Coloring
- Graph - Vertex Cover
- Knapsack Problem
- Job Scheduling Problem
The below given problems find their solution using divide and conquer algorithm approach:
- Merge Sort
- Quick Sort
- Binary Search
- Strassen's Matrix Multiplication
- Closest pair (points)
The below given problems find their solution using divide and conquer algorithm approach:
- Fibonacci number series
- Knapsack problem
- Tower of Hanoi
- All pair shortest path by Floyd-Warshall
- Shortest path by Dijkstra
- Project scheduling
In data-structure, stack is an Abstract Data Type (ADT) used to store and retrieve values in Last In First Out (LIFO) method.
Stacks follows LIFO method and addition and retrieval of a data item takes only Ο(n) time. Stacks are used where we need to access data in the reverse order or their arrival. Stacks are used commonly in recursive function calls, expression parsing, depth first traversal of graphs etc.
The below operations can be performed on a stack:
- push() − adds an item to stack
- pop() − removes the top stack item
- peek() − gives value of top item without removing it
- isempty() − checks if stack is empty
- isfull() − checks if stack is full
Queue is an abstract data structure (ADS), somewhat similar to stack. In contrast to stack, queue is opened at both end. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out (FIFO) methodology, i.e., the data item stored first will be accessed first.
As queues follows FIFO method, they are used when we need to work on data-items in exact sequence of their arrival. Every operating system maintains queues of various processes. Priority queues and breadth first traversal of graphs are some examples of queues.
The below operations can be performed on a queue:
- enqueue() − adds an item to rear of the queue
- dequeue() − removes the item from front of the queue
- peek() − gives value of front item without removing it
- isempty() − checks if stack is empty
- isfull() − checks if stack is full
Selection sort is in-place sorting technique. It divides the data set into two sub-lists: sorted and unsorted. Then it selects the minimum element from unsorted sub-list and places it into the sorted list. This iterates unless all the elements from unsorted sub-list are consumed into sorted sub-list.
A problem can be solved in more than one ways. So, many solution algorithms can be derived for a given problem. We analyze available algorithms to find and implement the best suitable algorithm.
An algorithm are generally analyzed on two factors − time and space. That is, how much execution time and how much extra space required by the algorithm.
-
A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an
O(n)search - the time taken to search the list gets bigger at the same rate as the list does. -
A binary search is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you're looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc. In complexity terms this is an
O(log n)search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation.
Comparing the two:
- Binary search requires the input data to be sorted; linear search doesn't
- Binary search requires an ordering comparison; linear search only requires equality comparisons
- Binary search has complexity
O(log n); linear search has complexity O(n) - Binary search requires random access to the data; linear search only requires sequential access (this can be very important - it means a linear search can stream data of arbitrary size)
Asymptotic analysis of an algorithm, refers to defining the mathematical boundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case and worst case scenario of an algorithm.
Asymptotic analysis can provide three levels of mathematical binding of execution time of an algorithm:
- Best case is represented by Ω(n) notation.
- Worst case is represented by Ο(n) notation.
- Average case is represented by Θ(n) notation.
There are three commonly used approaches to develop algorithms:
- Greedy Approach − finding solution by choosing next best option
- Divide and Conquer − diving the problem to a minimum possible sub-problem and solving them independently
- Dynamic Programming − diving the problem to a minimum possible sub-problem and solving them combinedly
Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called Ring Buffer. Circular queue avoids the wastage of space in a regular queue implementation using arrays.
Insertion Sort is faster for small n because Quick Sort has extra overhead from the recursive function calls. Insertion sort is also more stable than Quick sort and requires less memory.
Insertion sort divides the list into two sub-list, sorted and unsorted. It takes one element at time and finds it appropriate location in sorted sub-list and insert there. The output after insertion is a sorted sub-list. It iteratively works on all the elements of unsorted sub-list and inserts them to sorted sub-list in order.
Consider:
5, 9, 13, 4, 1, 6 // the only sorted part is the first item
5, 9, 13, 4, 1, 6 // 9 > 5 so we don't move it
5, 9, 13, 4, 1, 6 // 13 > 9 we don't move it
4, 5, 9, 13, 1, 6 // compare all to 4, until we reach the head
1, 4, 5, 9, 13, 6 // compare all to 1, until we reach the head
1, 4, 5, 6, 9, 13 // first smaller item is 5, place 6 before itAnd code:
function insertionSort (items) {
for (var i = 0; i < items.length; i++) {
let value = items[i]
// store the current item value so it can be placed right
for (var j = i - 1; j > -1 && items[j] > value; j--) {
// loop through the items in the sorted array (the items from the current to the beginning)
// copy each item to the next one
items[j + 1] = items[j]
}
// the last item we've reached should now hold the value of the currently sorted item
items[j + 1] = value
}
return list
}
const list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
console.log(insertionSort(list)) // [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]insertion sort provides several advantages:
- Simple implementation
- Efficient for (quite) small data sets, much like other quadratic sorting algorithms
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
- Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position
- Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it
Both insertion sort and selection sort have an outer loop (over every index), and an inner loop (over a subset of indices). Each pass of the inner loop expands the sorted region by one element, at the expense of the unsorted region, until it runs out of unsorted elements.
The difference is in what the inner loop does:
- In selection sort, the inner loop is over the unsorted elements. Each pass selects one element, and moves it to its final location (at the current end of the sorted region).
- In insertion sort, each pass of the inner loop iterates over the sorted elements. Sorted elements are displaced until the loop finds the correct place to insert the next unsorted element.
So, in a selection sort, sorted elements are found in output order, and stay put once they are found. Conversely, in an insertion sort, the unsorted elements stay put until consumed in input order, while elements of the sorted region keep getting moved around.
As far as swapping is concerned: selection sort does one swap per pass of the inner loop. Insertion sort typically saves the element to be inserted as temp before the inner loop, leaving room for the inner loop to shift sorted elements up by one, then copies temp to the insertion point afterwards.
Merge sort is one of the commonly used sorting algorithms in computer science. It is used by Firefox and Safari in their implementation of Array.prototype.sort() (remember how JavaScript behaves differently in different browsers?). It has good performance, it’s easy to implement and understand.
Merge sort is sorting algorithm based on divide and conquer programming approach. It keeps on dividing the list into smaller sub-list until all sub-list has only 1 element. And then it merges them in a sorted way until all sub-lists are consumed. It has run-time complexity of Ο(n log n) and it needs Ο(n) auxiliary space.
Consider:
// Split the array into halves and merge them recursively
function mergeSort (arr) {
if (arr.length === 1) {
// return once we hit an array with a single item
return arr
}
const middle = Math.floor(arr.length / 2) // get the middle item of the array rounded down
const left = arr.slice(0, middle) // items on the left side
const right = arr.slice(middle) // items on the right side
return merge(
mergeSort(left),
mergeSort(right)
)
}
// compare the arrays item by item and return the concatenated result
function merge (left, right) {
let result = []
let indexLeft = 0
let indexRight = 0
while (indexLeft < left.length && indexRight < right.length) {
if (left[indexLeft] < right[indexRight]) {
result.push(left[indexLeft])
indexLeft++
} else {
result.push(right[indexRight])
indexRight++
}
}
return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight))
}
const list = [2, 5, 1, 3, 7, 2, 3, 8, 6, 3]
console.log(mergeSort(list)) // [ 1, 2, 2, 3, 3, 3, 5, 6, 7, 8 ]Quick sort uses divide and conquer approach. It divides the list in smaller partitions using pivot. The values which are smaller than the pivot are arranged in the left partition and greater values are arranged in the right partition. Each partition is recursively sorted using quick sort.
Consider:
- Step-1: You have to pick a pivot. This could be randomly selected or the middle one. Here we select the last element of the array.
- Step-2: Put all the items smaller than the pivot value to the left and larger than the pivot value to the right.
- Step-3:Repeat the step-2 for both left and right side of the pivot (pick a pivot, put all item smaller than the pivot to the left and larger on the right)
function quickSort(arr, left, right){
var len = arr.length,
pivot,
partitionIndex;
if (left < right){
pivot = right;
partitionIndex = partition(arr, pivot, left, right);
//sort left and right
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
function partition(arr, pivot, left, right){
var pivotValue = arr[pivot],
partitionIndex = left;
for(var i = left; i < right; i++){
if(arr[i] < pivotValue){
swap(arr, i, partitionIndex);
partitionIndex++;
}
}
swap(arr, right, partitionIndex);
return partitionIndex;
}
function swap(arr, i, j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
quickSort([11,8,14,3,6,2,7],0,6);
//[2, 3, 6, 7, 8, 11, 14]
Shell sort can be said a variant of insertion sort. Shell sort divides the list into smaller sublist based on some gap variable and then each sub-list is sorted using insertion sort. In best cases, it can perform up to Ο(n log n). For a value of gap equals to 1, this algorithm is equal to insertion sort.
Consider:
// array to sort
var array = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8];
// gaps
var gaps = [701, 301, 132, 57, 23, 10, 4, 1];
function shellsort(array) {
for(var g = 0; g < gaps.length; g++) {
var gap = gaps[g];
for(var i = gap; i < array.length; i++) {
var temp = array[i];
for(var j = i; j >= gap && array[j - gap] > temp; j -= gap) {
array[j] = array[j - gap];
}
array[j] = temp;
}
}
return array;
}
console.log(shellsort(array)); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]An important concept in analysis of algorithms is asymptotic analysis. In the case of two algorithms with different asymptotic running times, such as one O(n^2) and one O(nlogn) as is the case with insertion sort and quicksort respectively, it is not definite that one is faster than the other.
Although Insertion Sort is one of the elementary sorting algorithms with O(n^2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).
For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.
The only significant advantage that bubble sort has over most other algorithms, even quicksort (but not insertion sort), is that the ability to detect that the list is sorted efficiently is built into the algorithm.
When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex.
Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.
function bucketSort(array, k) is
buckets ← new array of k empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[getBucket(array[i])]
for i = 0 to k - 1 do
nextSort(buckets[i]);
return the concatenation of buckets[0], ...., buckets[k-1]Different functions (getBucket) can be used to translate the range of elements in array to k buckets.
The complexity of bucket sort isn’t constant depending on the input. However in the average case the complexity of the algorithm is O(n + k) where n is the length of the input sequence, while k is the number of buckets.
The problem is that its worst-case performance is O(n^2) which makes it as slow as bubble sort.
Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.
TimSort is highly optimisation Merge Sort, it is stable and faster than old Merge Sort. When comparing with Quick Sort, it has two advantages:
- It is very fast for nearly sorted data sequence (including reverse sorted data)
- The worst case is still
O(n log n).
If you need stable sort, try Tim Sort, otherwise start with Quick Sort.
Quicksort has O(n^2) worst-case runtime and O(n log n) average case runtime. However, it’s superior to merge sort in many scenarios because many factors influence an algorithm’s runtime, and, when taking them all together, quicksort wins out.
accepted Quicksort has O(n2) worst-case runtime and O(nlogn) average case runtime. However, it’s superior to merge sort in many scenarios because many factors influence an algorithm’s runtime, and, when taking them all together, quicksort wins out.
In particular, the often-quoted runtime of sorting algorithms refers to the number of comparisons or the number of swaps necessary to perform to sort the data. This is indeed a good measure of performance, especially since it’s independent of the underlying hardware design. However, other things – such as locality of reference (i.e. do we read lots of elements which are probably in cache?) – also play an important role on current hardware. Quicksort in particular requires little additional space and exhibits good cache locality, and this makes it faster than merge sort in many cases.
In addition, it’s very easy to avoid quicksort’s worst-case run time of O(n2) almost entirely by using an appropriate choice of the pivot – such as picking it at random (this is an excellent strategy).
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
Stable Sorting Algorithms (stable sort algo - IBM (Insertion, Bubble, Merge)):
- Insertion Sort
- Bubble Sort
- Merge Sort
- Tim Sort
- Counting Sort
Unstable Sorting Algorithms:
- Heap Sort
- Selection sort
- Shell sort
- Quick Sort
Stability matters if, and only if, the problem you're solving requires retention of that relative order.