BubbleSort in JAVA

ArrayBub.Java Class

public class ArrayBub {

private long[] a;
private int nElems;

public ArrayBub(int max){
nElems = 0;
a = new long[max];
}

public void insert(long value){
a[nElems++]= value;
}

public void display(){
for(int i=0;i<nElems;i++){
System.out.print(a[i] + " ");
}
}

public void bubbleSort(){
int out, in;

for(out= nElems -1; out > 1; out--){
for(in=0;in<out;in++){
if(a[in] > a[in+1]){
long temp = a[in];
a[in] = a[in+1];
a[in+1] = temp;
}
//swap(in,in+1);
}
}

}

private void swap(int one, int two){
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}

}

----------------------------------------------------------------------------------------------------------------------------------
BubbleSortApp.java class

public class BubbleSortApp {

public static void main(String[] args) {

int maxSize = 100;
ArrayBub  bub;
bub = new ArrayBub(maxSize);

bub.insert(77);
bub.insert(43);
bub.insert(99); // insert 10 items
bub.insert(44);
bub.insert(55);
bub.insert(22);
bub.insert(88);
bub.insert(11);
bub.insert(00);
bub.insert(66);
bub.insert(33);
bub.display();

bub.bubbleSort();
System.out.println("");
bub.display();
}

}

Breadth First Search (BFS) and Depth First Search (DFS) Program in C++/CPP

#include <iostream>
#include <fstream>

using namespace std;


template <class T>
class Stack{
private:
int max_size, top;
T * list;
public:
Stack(T size){
max_size = size;
top = 0;
list = new T[max_size];
}
bool isEmpty(){
return (top <= 0);
}
bool isFull(){
return (top >=max_size);
}
void push(const T& item){
if(!isFull()){
list[top] = item;
top++;
}
}
T pop(){
if(!isEmpty()){
top--;
}
return list[top];
}

T Top(){
return list[top-1];
}
};

//Queue Implementation
template <class T>
class Queue {
private:
int Qmax, count, Qf, Qr;
T * list;

public:
Queue(int size){
Qmax = size;
Qf = 0;
Qr = Qmax - 1;
count = 0;
list = new T[Qmax];
}

bool isEmpty(){
return (count == 0);
}

bool isFull(){
return (count == Qmax);
}

void addQueue(const T &element){
if(!isFull()){
Qr = (Qr + 1 ) % Qmax;
count++;
list[Qr] = element;
}
}

T FindFront(){
return list[Qf];
}

T DeleteQueue(){
T x;
if(!isEmpty()){
x = list[Qf];
count--;
Qf = (Qf + 1) % Qmax;
return x;
}else
return 100;
}


};

void revisit(int *visited, int size){
for(int i=0; i<size; i++){
visited[i] = 0;
}
}

int main(int argc, char **argv)
{
if(argc < 2){
cout<<"\n Please Enter a File Name:\n\n\n";
return 0;
}
argv++;

fstream input(*argv);  //Input as a file name at run time( from command line)

int size;

if(input>>size) cout<<"\nMatrix of: "<<size<<"*"<<size<<endl;
else return 0;

int adjmat[size][size];
int visited[size];

for(int i=0; i<size; i++){
for(int j=0; j<size; j++){
input>>adjmat[i][j];
}
}



cout<<"\nAdj. Matrix:\n";
for(int i=0; i<size; i++){
for(int j=0; j<size; j++){
cout<<adjmat[i][j]<<" ";
}
cout<<"\n";
}


//BFS(adjmat,size,visited);
cout<<"\n\nBreadth First Search:\n";
revisit(visited,size);
Queue<int> bfs(size);
{
int v = 0, w ;

bfs.addQueue(v);
visited[v] = 1;


while(!bfs.isEmpty()){

w = bfs.DeleteQueue();

cout<<w<<"--";

if(w==100){continue;}

for(int i = 0; i<size; i++){
if(adjmat[w][i] == 1 && visited[i] == 0){
bfs.addQueue(i);
visited[i] = 1;
}
}


}
cout<<"\n";
}
//bfs code ends here


//DFS Code Starts From Here
cout<<"\n\nDepth First Search:\n";
Stack<int> dfs(size);
revisit(visited,size);
{
int v = 0;
cout<<v<<"--";
dfs.push(v);
visited[0] = 1;

while(!dfs.isEmpty()){

for(int i=0; i<size; i++){
if(adjmat[v][i] == 1 && visited[i] == 0){
cout<<i<<"--";
dfs.push(i);
visited[i] = 1;
v = i;
i=0;
}
}

v = dfs.pop();

}
cout<<"\n";
//DFS Code ends Here



//Biparted Graph
{
revisit(visited,size);
int colored[size];
revisit(colored,size);
Queue<int> Bipart(size);
int v = 0, x;
visited[v] = 1;
colored[v] = 3;

for(int i = 0; i<size; i++){
if(adjmat[v][i] == 1 && visited[i] == 0){
Bipart.addQueue(i);
visited[i] = 1;
colored[i] = 4;
}
}

while(!Bipart.isEmpty()){
x = Bipart.DeleteQueue();
for(int i=0; i<size; i++){
if(adjmat[x][i] == 1 && visited[i] == 1 && colored[x]==colored[i]){
cout<<"\n\n Not a Biparted Graph\n\n";
return 0;
}
}

for(int j=0; j<size; j++){
if(adjmat[x][j] == 1 && visited[j] == 0){
Bipart.addQueue(j);
visited[j] = 1;
if(colored[x] == 3){
colored[j] = 4;
}else colored[j] = 3;
}
}
}

cout<<"\n\nBiparted Graph\n";

}
//Biparted graph ends here
}
return 0;
}

Binary Tree Properties

Binary Tree Properties

1.      In binary tree maximum number of nodes are 2^h – 1 where h is the height of the tree.

2.      In binary tree total number of leaf nodes are 2^{h -1}.

3.      In binary tree maximum number of node on each level 1 is 2¹.

4.      In complete binary tree total number of edges are 2^{(tn – 1)} where tn is number of leaf nodes.

5.      In a linked representation of binary tree, if total number of nodes are n then total null links are n + 1.

6.      A tree with n nodes has n – 1 edges or branches. 

Quick Sort example in C++ (Quick Sort.CPP)

#include <iostream>

using namespace std;

void QuickSort(int * a, int n);
void quickSort(int a[], int l, int r);

int main(int argc, char **argv)
{
int a[5];
int i=0;
while(i<5){
cin>>a[i++];
}
QuickSort(a,5);
i=0;
while(i<5){cout<<a[i++]<"\n ";cout<"--";}
return 0;
}

void QuickSort(int * a, int n){
quickSort(a, 0, n-1);
}

void quickSort(int a[], int l, int r){
if(l>=r) return;

int i=l;
int j=r + 1;

int pivot = a[l];

//Swap elements  >= pivot on left side
//with elements <= pivot on right side

while(true){
do{
i++;
}while(a[i] < pivot );

do{
j--;
}while(a[j] > pivot );

if( i >= j) break;

int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}

//Place pivot
a[l] = a[j];
a[j] = pivot;

quickSort(a, l, j-1); //Sort Left Segment
quickSort(a, j+1, r); //Sort Right Segment

}

courtesy : Data Structures, Algorithms and Applications in C++, SAHNI, McGrawHill

Merge Sort Program in C++ (Merge Sort.CPP)

#include <iostream>
using namespace std;

void Merge(int *c, int *d, int l, int m, int r){
//Merge c[l:m] amd c[m:r] to d[l:r]
int i =l; //cursor for first segment
int j = m+1; //cursor for second
int k = l; //cursor for result

//merge until i or j exits its segment
while((i<=m) && (j<=r)){

if(c[i] <= c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
}
//take care over left overs
if(i > m) for(int q =j; q<=r;q++) d[k++] = c[q];

else for (int q = i; q<=m; q++) d[k++] = c[q];

}

void MergePass(int *x, int *y, int s, int n){
//Merge adjacent segments of size s
int i = 0;
while(i <=n -1 * s){
//Merge two adjacent segment of size a
Merge(x,y,i,i+s-1,i+2*s-1);
i = i + 2 *s;
}

//fewer than 2s elements remain
if(i+s < n) Merge(x,y,i,i+s-1,n-1);
else for(int j =i; j<n; j++){
//Copy last segment to y
y[j]= x[j];
}
}

void MergeSort(int *a, int n){
//Sort a[0:n-1] using merge sort
int *b= new int[n];
int s = 1; //Segment Size
while(s<n){
MergePass(a, b, s, n); //merge from a to b
s += s;
MergePass(b,a,s,n); // merge from b to a
s += s;
}

}

int main(int argc, char **argv)
{
int a[6]={10,4,87,17,53,34};
MergeSort(a,6);
int i=0;
while(i<6){
cout<<"--"<<a[i++];
}
return 0;
}

courtesy : Data Structures, Algorithms and Applications in C++, SAHNI, McGrawHill

Application of Queue

1. In a multitasking operating system
2. Round Robin Scheduling
3. Priority Queue

Application of Stack

• Reversing Data: We can use stack to reverse data.
• Converting Decimal to Binary
• Evaluating arithmetic expressions
• Hanoi tower problem 

Application of Linked List

1. Sparse matrix representation
2. Polynomial manipulation
3. Dynamic memory storage
4. In symbol table