public class HeapSort
{
public static void heapify(int a[],int i,int n)
{
int l=2*i+1;
int r=2*i+2;
int temp,largest;
if(la[i])
largest=l;
else
largest=i;
if(ra[largest])
largest=r;
if(largest !=i)
{
temp=a[largest];
a[largest]=a[i];
a[i]=temp;
heapify(a,largest,n);
}
}
public static void bheap(int a[])
{
for(int i=(a.length/2)-1;i>=0;i--)
{
heapify(a,i,a.length);
}
}
public static void Sort(int a[])
{
int temp,j,i;
bheap(a);
for( i=(a.length)-1; i>0;)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
heapify(a,0,i--) ;
}
}
public static void printarray(int a[])
{
System.out.println();
for(int i=0; i < a.length; i++)
{
System.out.print(a[i]+" ");
}
}
public static void main(String[] args)
{
int n, res,i;
Scanner s = new Scanner(System.in);
System.out.print("Enter number of elements in the array:");
n = s.nextInt();
int a[] = new int[n];
System.out.println("Enter "+n+" elements ");
for( i=0; i < n; i++)
{
a[i] = s.nextInt();
}
System.out.println( "elements in array ");
printarray(a);
Sort(a);
System.out.println( "\nelements after sorting");
printarray(a);
}
}
Heap Sort algorithm
Quick Sort algorithm
public class QuickSort {
public static void main(String[] args) {
int i;
int[] arr={90,23,101,45,65,23,67,89,34,23};
quickSort(arr, 0, 9);
System.out.println("\n The sorted array is: \n");
for(i=0;i<10;i++)
System.out.println(arr[i]);
}
public static int partition(int a[], int beg, int end)
{
int left, right, temp, loc, flag;
loc = left = beg;
right = end;
flag = 0;
while(flag != 1)
{
while((a[loc] <= a[right]) && (loc!=right))
right--;
if(loc==right)
flag =1;
elseif(a[loc]>a[right])
{
temp = a[loc];
a[loc] = a[right];
a[right] = temp;
loc = right;
}
if(flag!=1)
{
while((a[loc] >= a[left]) && (loc!=left))
left++;
if(loc==left)
flag =1;
elseif(a[loc] <a[left])
{
temp = a[loc];
a[loc] = a[left];
a[left] = temp;
loc = left;
}
}
}
returnloc;
}
static void quickSort(int a[], int beg, int end)
{
int loc;
if(beg<end)
{
loc = partition(a, beg, end);
quickSort(a, beg, loc-1);
quickSort(a, loc+1, end);
}
}
}
Merge Sort algorithm
public class MergeSort
{
void merge(int arr[], int beg, int mid, int end)
{
int l = mid - beg + 1;
int r = end - mid;
intLeftArray[] = new int [l];
intRightArray[] = new int [r];
for (int i=0; i<l; ++i)
{
LeftArray[i] = arr[beg + i];
}
for (int j=0; j<r; ++j)
RightArray[j] = arr[mid + 1+ j];
int i = 0, j = 0;
int k = beg;
while (i<l&&j<r)
{
if (LeftArray[i] <= RightArray[j])
{
arr[k] = LeftArray[i];
i++;
}
else
{
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i<l)
{
arr[k] = LeftArray[i];
i++;
k++;
}
while (j<r)
{
arr[k] = RightArray[j];
j++;
k++;
}
}
void sort(int arr[], int beg, int end)
{
if (beg<end)
{
int mid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
public static void main(String args[])
{
intarr[] = {90,23,101,45,65,23,67,89,34,23};
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
for(int i =0; i<arr.length;i++)
{
System.out.println(arr[i]+"");
}
}
}
Insertion Sort Algorithm
public class InsertionSort {
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
}
public static void main(String a[]){
int[] arr1 = {9,14,3,2,43,11,58,22};
System.out.println("Before Insertion Sort");
for(int i:arr1){
System.out.print(i+" ");
}
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sort");
for(int i:arr1){
System.out.print(i+" ");
}
}
}
Selection Sort algorithm
public class SelectionSort {
public static void selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;//searching for lowest index
}
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
public static void main(String a[]){
int[] arr1 = {9,14,3,2,43,11,58,22};
System.out.println("Before Selection Sort");
for(int i:arr1){
System.out.print(i+" ");
}
System.out.println();
selectionSort(arr1);//sorting array using selection sort
System.out.println("After Selection Sort");
for(int i:arr1){
System.out.print(i+" ");
}
}
}
Bubble Sort algorithm
public class BubbleSort {
static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String[] args) {
int arr[] ={3,60,35,2,45,320,5};
System.out.println("Array Before Bubble Sort");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
bubbleSort(arr);//sorting array elements using bubble sort
System.out.println("Array After Bubble Sort");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
}
}
binary search algorithm
Binary Search using Iteration
class BinarySearch{
public static void binarySearch(int arr[], int first, int last, int key){
int mid = (first + last)/2;
while( first <= last ){
if ( arr[mid] < key ){
first = mid + 1;
}else if ( arr[mid] == key ){
System.out.println("Element is found at index: " + mid);
break;
}else{
last = mid - 1;
}
mid = (first + last)/2;
}
if ( first > last ){
System.out.println("Element is not found!");
}
}
public static void main(String args[]){
int arr[] = {10,20,30,40,50,60};
int key = 30;
int last=arr.length-1;
binarySearch(arr,0,last,key);
}
}
Binary Search using Recurssion
class BinarySearchUsingRecurssion{
public static int binarySearch(int arr[], int first, int last, int key){
if (last>=first){
int mid = first + (last - first)/2;
if (arr[mid] == key){
return mid;
}
if (arr[mid] > key){
return binarySearch(arr, first, mid-1, key);//search in left subarray
}else{
return binarySearch(arr, mid+1, last, key);//search in right subarray
}
}
return -1;
}
public static void main(String args[]){
int arr[] = {10,20,30,40,50};
int key = 30;
int last=arr.length-1;
int result = binarySearch(arr,0,last,key);
if (result == -1)
System.out.println("Element is not found!");
else
System.out.println("Element is found at index: "+result);
}
}
linear search algorithm
public class LinearSearch{
public static int linearSearch(int[] arr, int key){
for(int i=0;i < arr.length;i++){
if(arr[i] == key){
return i;
}
}
return -1;
}
public static void main(String a[]){
int[] a1= {10,20,30,50,60,70,80};
int key = 50;
System.out.println(key+" found at index: "+linearSearch(a1, key));
}
}
Interview questions on recursion
fibonacci series
Factorial
GCD
Tower of hanoi
decimal to binary using recursion
Recursion
The process in which a method calls itself is called recursion.
Recursion occurs when a method calls itself.
Example: a method calling itself
Method1()
{
Method1();
}
Recursion is used to solve the problem where the solution of a problem depends on the solution of the smaller instances of the same problem
For example we are trying to find factorial of 5.
problem: factorial(5) factorial(5) = 5* Factorial(4) to find the solution for factorial(5), we need to find solution for another smaller instance of same problem Factorial(4). Factorial(4) = 4 * factorial(3) to find the solution for factorial(4), we need to find solution for another smaller instance of same problem Factorial(3). similarly Factorial(3) = 3 * factorial(2) Factorial(2) = 2 * factorial(1) Factorial(1) = 1 * factorial(0) factorial(0) = 1 once terminal condition or base condition occurs, it is the end of recursion. from this point there is no recursion. and it return the value of that condition. here in this example factorial(0) returns 1. and the execution continues Factorial(1) = 1 * 1 // as factorial(0) = 1 Factorial(2) = 2 * 1 // as Factorial(1) = 1 Factorial(3) = 3 * 2 // as Factorial(2) = 2 Factorial(4) = 4 * 6 // as Factorial(3) = 6 Factorial(5) = 5 * 24 // as Factorial(4) = 24 final out put for Factorial(5) is 120.
factorial(5)
= (5* Factorial(4))
= (5* (4 * Factorial(3)))
=(5* (4 * (3 * Factorial(2))))
= (5* (4 * (3 * (2 * Factorial(1)))))
= (5* (4 * (3 * (2 * (1 * Factorial(0))))))
= (5* (4 * (3 * (2 * (1 * 1)))))
= (5* (4 * (3 * (2 * 1))))
= (5* (4 * (3 * 2)))
= (5* (4 * 6))
=(5 * 24)
= 120
The recursion can be direct (when the method calls itself) or indirect (when the method calls some other method that then calls the first method).
Direct Recursion:
Method1()
{
Method1()
}
Indirect Recursion:
Method1()
{
Method2()
}
Method2()
{
Method1()
}
Recursion can also be single (when the method calls itself once) or multiple (when the method calls itself multiple times).
Examples: Factorial Fibonacci series GCD Tower Of Hanoi
Subscribe to:
Posts (Atom)