Insertion Sort Program in Java. Write a java program to sort an unsorted array using insertion sort.
In this tutorial, We are going to cover following points.
Let’s say we have an unsorted array and we want to sort this array using insertion sort. Let’s first understand how insertion sort works?
Input : {5, 4, 2, 9, 1}
Output : {1, 2, 4, 5, 9}
Get minimum element from stack in O(1).
In this problem, we have to design a stack that supports push, pop, top, and retrieving the minimum element in constant time (O(1)).
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.
For example: Suppose, If we push the following elements in a stack.
9 ==> Top
1
2
3
Then if we call getMin() method, It should return 1 in O(1) (constant time).
How to Segregate 0s and 1s in an Array.
Given an array of 0s and 1s in a random order. We have to write a code to segregate 0s on the left side and 1s on the right side of the array.
Basically, we have to sort an array of 0s and 1s.
For example –
Input array = [0, 1, 0, 1, 0, 0, 1]
Output array = [0, 0, 0, 0, 1, 1, 1]
In an input array 0s and 1s are in an unsorted order. The output is the sorted order of 0s and 1s.