Sorting Techniques

Merge K Sorted Arrays

by

Objective: Given k sorted array, write an algorithm to merge Them into One sorted array.

Example :

int [][] A = new int[5][];

A[0] = new int[] { 1, 5, 8, 9 };
A[1] = new int[] { 2, 3, 7, 10 };
A[2] = new int[] { 4, 6, 11, 15 };
A[3] = new int[] { 9, 14, 16, 19 };
A[4] = new int[] { 2, 4, 6, 9 };

Output:
[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]

Read more

Counting Sort

by

Counting Sort is an sorting algorithm, which sorts the integers( or Objects) given in a specific range.

Algorithm: Time Complexity O(n)

  • Take two arrays, Count[] and Result[] and given array is input[].
  • Count[] will store the counts of each integer in the given array.
  • Update the Count[] so that each index will store the sum till previous step. (Count[i]=Count[i] + Count[i-1]). Now updated Count[] array will reflect the actual position of each integer in Result[].
  • Now navigate the input array taking one element at a time, Count[input[i]] will tell you the index position of input[i] in Result[]. When you do that, decrease the count in Count[input[i]] by 1. See Example

Read more

Sort 3 Integers without using if condition OR use only Max() function.

by

Objec­tive: – Given three integers, sort them without using if condition.

Appraoch:

  • Say 3 integers are, a, b, and c.
  • Find the maximum of a, b, and c using Max() function.
  • multiply all integers by -1. Again find Minimum of -a, -b, -c using Max() function.
  • Add the Max and Min from the above steps and subtract them from (a+b+c). It will give you a middle element.

Read more

Sort an Given Array in the order defined by another array

by

Objective: Given an array of integers, write an algorithm to sort it according to the order defined by another array.

Input: An Array of Integers

Example:

Input Array : 2 6 9 1 4 4 2 1 10 13 5 7 8

DefinedArray : 1 2 4 6

Output : 1 1 2 2 4 4 6 5 7 8 9 10 13

Appraoch:

Method 1: Sort and Search

Read more

Sort an Array – odd numbers appear first in ascending order followed by the even numbers in descending order.

by

Objective: Given an array of intergers, sort it such that the odd numbers appear first followed by the even numbers . The odd numbers in ascending order and the even numbers in descending order.

Input: An Array of Integers

Example:

Input Array : 1 2 3 4 5 6 7 8 9 10
Output : 1 3 5 7 9 10 8 6 4 2

Read more