Sorting Techniques

Longest substring with at most K unique characters

by

Objective: Given a string, write an algorithm to find the longest substring with at most K characters. Example: Input: aabbaacdeeeeddded, K = 3 Output: Longest substring with 3 most unique characters is: cdeeeeddded with length 11 Input: abcddefabc, K = 4 Output: Longest substring with 4 most unique characters is: abcdd with length 5 Input: … Read more

Sort a given stack – Using Temporary Stack

by

Objective: Given a stack of integers, write an algorithm to sort the stack using a temporary stack.  Example: Given Stack: [14, 9, 67, 91, 101, 25] Sorted Stack: [9, 14, 25, 67, 91, 101] Approach: Use another stack, let’s call it a temporary stack. While given original is not empty Pop the element from the … Read more

Sum of all Unique elements in a given array

by

Objective: Given an array of integers that contains duplicates as well. Write a program to find the sum of all unique elements in the array. This problem is also referred to as find the sum of all distinct elements in the array Example: [] arrA = {1, 6, 4, 3, 2, 2, 3, 8, 1}; … Read more

Selection Sort – Java Implementation

by

What is Selection Sort?? Selection sort is a simple sorting algorithm that builds the sorted array one item at a time. This sorting is efficient for small data sets, not efficient for large data sets. This is in-place sorting algorithm. How Selection Sort algorithm works?? This algorithm divides the given input list into two parts, … Read more

Find Number of reverse pairs in an array

by

Objective: Given an array of integers A[],find no of reverse pairs means no of (i, j) pairs where i < j and A[i]>A[j]. This problem is also asked as Count Inversions in an array. Example: A[] = {10, 3, 4, 2, 5, 7, 9, 11} Output:7 Reversed pairs: (10, 3) (10, 4) (10, 2) (10, … Read more

Heap Sort – Java Implementation

by

What is Heap Sort?? Heap sort is comparison based sorting algorithm. Heap sort is considered as improved selection sort, it divides the input into sorted and unsorted region. The improvement from selection sort is to use Heap Data Structure instead of using linear search algorithm to reduce of the time complexity. Pre-requisite: Binary Heap (min … Read more

Bubble Sort and Optimized Bubble Sort- Java Implementation

by

In this article we will discuss about what is bubble sort, why it is considered as one of the simplest sorting algorithm, what its complexity, how we can improve the bubble sort algorithm. What is bubble sort?? Bubble sort is one of the simplest sorting algorithms. Bubble sort compares each pair of adjacent items and swaps … Read more

Sort Names by their Last Names.

by

Objective: Given a list of names ( first name and last name), sort the list by their last names. Example: List [] = {“Daenerys Targaryen”, “Jon Snow”, ” Tyrion Lannister”, ” Joffrey Baratheon”} Output: [Joffrey Baratheon, Tyrion Lannister, Jon Show, Daenerys Targaryen] Approach: We have sort() and Collections.sort() but we cannot do the normal sorting … Read more

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, c.
  • Find the maximum of a, b, 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 above steps and subtract it from (a+b+c). It will give you middle element.

Read more

Merge Sort in a Linked list

by

Objective: Given a Linked List, Sort it using merge sort. Example: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Reference : Merge Sort in array As it Merge sort, we apply the same logic , Divide and Conquer. Find the length of the link list, say it is L. mid will be L/2. Now we need to divide … 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