# sorting

Merge Sort Algorithm

Merge sort is one of the fastest comparison-based sorting algorithms, which works on the principle of the divide and conquer approach. The worst and best case time complexity of merge sort is O(nlogn), and space complexity is O(n). It is also the best algorithm for sorting linked lists.

Counting Sort Algorithm

The counting sort algorithm assumes that each n input element is an integer in the range 0 to k. So by using array indexing as a tool for determining relative order, counting sort can sort n numbers in O(k + n) time when k = O(n). In other words, counting sort is one of the popular linear time sorting algorithms that works in O(n) time complexity if input elements are an integer in the range 0 to k.

Why do we need to learn different Sorting algorithms?

These are some critical reasons to study sorting algorithms: 1) It can help us to learn analysis of algorithms and various problem-solving approaches 2) Sorting can work as a problem-solving approach to solve several coding problems 3) We can learn code optimization techniques and variations in boundary conditions using sorting.

Lower bound of comparison based sorting

Comparison-based sorting algorithms like merge sort, quicksort, insertion sort, heap sort, etc., determine the sorted order based on the comparisons between the input elements. We call such algorithms comparison sort. The critical question is: Why is the lower bound of comparison sort O(nlogn)? Explore this blog to get an answer!

First Missing Positive

Given an array that includes both positive and negative numbers, write a program to find the first missing positive integer. This is one of the best searching problems for learning step-by-step optimization using various approaches. An in-place hashing solution uses the same input array to process values and generate correct output.

Sort Characters by Frequency

Given a string S[], write a program to sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. If two characters have the same frequency, whichever occurs earliest in S, must come first. In other words, the sorting must be stable.

Sort a stack using another stack

Given a stack, write a program to sort the stack in ascending order. We are not allowed to make any assumptions about how the stack is implemented. The only functions to be used are push(s, x), pop(s), top(s), isEmpty(s).

Find maximum j – i such that A[j] > A[i]

Given an unsorted array X[] of distinct elements, write a program to find the maximum j  -  i such that j > i and X[j] > X[i].

Triplet with Zero Sum

Given an array X[] of distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, suppose such triplets in the array are X[i], X[j] and X[k] then X[i] + X[j] + X[k] = 0. Note : solution set must not contain duplicate triplets.

Sorting Algorithms Comparison

Comparison of sorting algorithms based on different parameters helps us choose an effcient sorting method in various problem-solving scenarios. You will get an answer to the following questions: how to compare two sorting algorithms? Which sorting is best in terms of properties like efficiency, in-place, stability, online vs. offline, etc.

Check if two arrays are equal or not

Given two integer arrays X[] and Y[], write a program to check if the arrays are equal or not. Two arrays are equal if they have the same elements in any order. If there are repeated elements, then counts of repeated elements must also be the same for both arrays.

Longest Consecutive Sequence

Given an array X[] of n integers, write a program to find the length of the longest consecutive elements sequence. In other words, we need to find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers. The consecutive numbers can be in any order.

Find most frequent element in an array

Given an array X[] of size n, write a program to find the most frequent element in the array, i.e. the element which occurs the most number of times. It is assumed that at least one element is repeated.

Find whether an array is a subset of another array

We are given two integer arrays X[] and Y[], write a program to check whether array Y[] is a subset of array X[] or not. An array Y is a subset of another array X if each Y element is present in X. How do you check if one array is a subset of another? Explore and Enjoy!

Check for pair in an array with a given sum

Given an array of n integers and a target number, write a program to check whether a pair sum exits in the array or not. In other words, we need to check whether pair of elements in the array sum exactly to the target value.

Quick Sort Algorithm

Quicksort is often the best practical choice for sorting because it works remarkably efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn problem-solving using recursion and divide and conquer approach. In this blog, we have covered: 1) How quick sort works recursively? 2) Choosing a correct pivot value in the partition algorithm 3) Best, worst, and average-case time complexity analysis 4) Space complexity and essential properties of the quick sort. Explore and Enjoy!

Sorting Algorithms: Bubble Sort, Selection Sort and Insertion Sort

Sorting algorithms are the most fundamental problems to study in data structure and algorithms. But the critical question is - why we learn the design, code, and analysis of the sorting algorithms? Explore and Think!

Sort an array of 0s, 1s, and 2s —Dutch National Flag Problem

Given an array X[] consisting of 0s, 1s, and 2s. Write a program to sort the array of 0’s, 1’s, and 2’s in ascending order. This is a famous coding interview problem asked in facebook, microsoft and amazon.

Sort an array in a waveform

Given an array of integers, sort the array into a wave-like arrangement. In other words, An array A[0..n-1] is sorted in wave form if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= ….This problem has been asked during google coding interview.