Introsort Algorithm: Overview & Implementation

Given an array of integers, sort it using introsort sorting algorithm.   Introsort is an efficient in-place sorting algorithm, which usually beats all other sorting algorithms in terms of performance. Due to its high performance, it is used in a number of standard library sort functions, including some C++ sort implementations.   Introsort is a comparison …

Quicksort using Dutch National Flag Algorithm

Implement Quicksort efficiently for inputs containing many repeated elements.

Ternary Search vs Binary search

In this article, we will implement Ternary Search algorithm and compare its performance with Binary Search.

Longest Increasing Subsequence

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

Merge Sort Algorithm for Singly Linked List (in C and Java)

Given a linked list, sort it using merge sort algorithm.     Merge sort algorithm is an efficient, general-purpose sorting algorithm which produces a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a comparison sort, i.e. it can sort items of any …

Efficiently implement power function | Recursive and Iterative

Given two integers x and n where n is non-negative, efficiently compute the value of power function pow(x, n).

Maximum Sum Subarray using Divide & Conquer

Given an array of integers, find maximum sum subarray among all subarrays possible.

Find peak element in an array

Given an array, find peak element in it. A peak element is an element that is greater than its neighbors.

Find number of 1’s in a sorted binary array

Given a sorted binary array, efficiently find the number of 1’s in it.

Search in a nearly sorted array in log(n) time

Given a nearly sorted array such that each of the N elements may be misplaced by no more than one position from the correct sorted order, efficiently search a given element in it. Report if the element is not present in the input array.

Find Floor and Ceil of a number in a sorted array

Given a sorted array of integers, find floor and ceil of a given number in it. The floor and ceil map the given number to the largest previous or the smallest following integer, respectively.

Find smallest missing element from a sorted array

Given a sorted array of distinct non-negative integers, find smallest missing element in it.