Implement selection sort in java
package com.java2novice.algos;
public class MySelectionSort
{
public static int[] doSelectionSort(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;
int smallerNumber
= arr[index];
arr[index] =
arr[i];
arr[i] =
smallerNumber;
}
return arr;
}
public static void main(String
a[])
{
int[] arr1 =
{10,34,2,56,7,67,88,42};
int[] arr2 =
doSelectionSort(arr1);
for(int i:arr2)
{
System.out.print(i);
System.out.print(", ");
}
}
}
Implement insertion sort in java
package com.java2novice.algos;
public class MyInsertionSort
{
public static void main(String a[])
{
int[] arr1 =
{10,34,2,56,7,67,88,42};
int[] arr2 =
doInsertionSort(arr1);
for(int i:arr2)
{
System.out.print(i);
System.out.print(", ");
}
}
public static int[]
doInsertionSort(int[] input)
{
int temp;
for (int i = 1; i
< input.length; i++)
{
for(int j = i ; j
> 0 ; j--){
if(input[j]
< input[j-1]){
temp =
input[j];
input[j]
= input[j-1];
input[j-1] = temp;
}
}
}
return input;
}
}
Implement quick sort in java
package com.java2novice.sorting;
public class MyQuickSort
{
private int array[];
private int length;
public void sort(int[] inputArr)
{
if
(inputArr == null || inputArr.length == 0)
{
return;
}
this.array
= inputArr;
length
= inputArr.length;
quickSort(0,
length - 1);
}
private void quickSort(int lowerIndex, int
higherIndex)
{
int
i = lowerIndex;
int
j = higherIndex;
int
pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
while
(i <= j)
{
while
(array[i] < pivot)
{
i++;
}
while
(array[j] > pivot)
{
j--;
}
if
(i <= j)
{
exchangeNumbers(i,
j);
i++;
j--;
}
}
if
(lowerIndex < j)
quickSort(lowerIndex,
j);
if
(i < higherIndex)
quickSort(i,
higherIndex);
}
private void exchangeNumbers(int i, int j)
{
int
temp = array[i];
array[i]
= array[j];
array[j]
= temp;
}
public static void main(String a[])
{
MyQuickSort
sorter = new MyQuickSort();
int[]
input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int
i:input){
System.out.print(i);
System.out.print("
");
}
}
}
Implement merge sort in java
package com.java2novice.sorting;
public class MyMergeSort
{
private int[] array;
private int[]
tempMergArr;
private int length;
public static void main(String a[])
{
int[]
inputArr = {45,23,11,89,77,98,4,28,65,43};
MyMergeSort
mms = new MyMergeSort();
mms.sort(inputArr);
for(int
i:inputArr)
{
System.out.print(i);
System.out.print("
");
}
}
public void sort(int inputArr[])
{
this.array
= inputArr;
this.length
= inputArr.length;
this.tempMergArr
= new int[length];
doMergeSort(0,
length - 1);
}
private void doMergeSort(int lowerIndex, int
higherIndex)
{
if
(lowerIndex < higherIndex)
{
int
middle = lowerIndex + (higherIndex - lowerIndex) / 2;
doMergeSort(lowerIndex,
middle);
doMergeSort(middle
+ 1, higherIndex);
mergeParts(lowerIndex,
middle, higherIndex);
}
}
private void mergeParts(int lowerIndex, int
middle, int higherIndex)
{
for
(int i = lowerIndex; i <= higherIndex; i++)
{
tempMergArr[i]
= array[i];
}
int
i = lowerIndex;
int
j = middle + 1;
int
k = lowerIndex;
while
(i <= middle && j <= higherIndex)
{
if
(tempMergArr[i] <= tempMergArr[j])
{
array[k]
= tempMergArr[i];
i++;
}
else
{
array[k]
= tempMergArr[j];
j++;
}
k++;
}
while
(i <= middle)
{
array[k]
= tempMergArr[i];
k++;
i++;
}
}
}
Stack introduction & implementation
package com.java2novice.ds.stack;
public class MyStackImpl
{
private
int stackSize;
private int[] stackArr;
private int top;
public
MyStackImpl(int size)
{
this.stackSize
= size;
this.stackArr
= new int[stackSize];
this.top
= -1;
}
public void
push(int entry) throws Exception
{
if(this.isStackFull())
{
throw
new Exception("Stack is already full. Can not add element.");
}
System.out.println("Adding:
"+entry);
this.stackArr[++top]
= entry;
}
public
int pop() throws Exception
{
if(this.isStackEmpty())
{
throw
new Exception("Stack is empty. Can not remove element.");
}
int
entry = this.stackArr[top--];
System.out.println("Removed
entry: "+entry);
return
entry;
}
public int peek()
{
return
stackArr[top];
}
public boolean
isStackEmpty()
{
return
(top == -1);
}
public boolean
isStackFull()
{
return
(top == stackSize - 1);
}
public
static void main(String[] args)
{
MyStackImpl
stack = new MyStackImpl(5);
try
{
stack.push(4);
stack.push(8);
stack.push(3);
stack.push(89);
stack.pop();
stack.push(34);
stack.push(45);
stack.push(78);
}
catch
(Exception e)
{
System.out.println(e.getMessage());
}
try
{
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
}
catch
(Exception e)
{
System.out.println(e.getMessage());
}
}
}
No comments:
Post a Comment