Data structures throw java Lab Programs Last part
Program 30(b): Dictionary operations using
java.util.Hashtable
import java.util.*;
class HashtableDemo
{ public static void main(String[] args)
{
Hashtable<String, String> htab = new
Hashtable<String, String>();
// Insert the
following items
htab.put("man",
"gentleman");
htab.put("watch",
"observe");
htab.put("hope",
"expect"); 80 Lab Manual Data Structures through Java
htab.put("arrange", "put
together");
htab.put("run", "sprint");
htab.put("wish",
"desire");
htab.put("help",
"lend a hand");
htab.put("insert", "put
in");
htab.put("count", "add
up");
htab.put("format",
"arrangement");
System.out.println(htab); // Display the table
items
System.out.println("get(hope): " +
htab.get("hope"));
System.out.println("remove(arrange):
" + htab.remove("arrange"));
System.out.println("remove(help): "
+ htab.remove("help"));
// returns a
set containing all the pairs (key, value).
System.out.println(htab.entrySet());
}
}
Output:
{ arrange=put together, man=gentleman, wish=desire,
run=sprint, help=lend a
hand,
count=add up, watch=observe, hope=expect, format=arrangement,
insert=put in
}
get(hope):
expect
remove(arrange): put together
remove(help):
lend a hand
[ man=gentleman, wish=desire, run=sprint, count=add
up, watch=observe,
hope=expect,
format=arrangement, insert=put in ] Graphs
31. Write Java programs for the implementation of
bfs and dfs for a given graph.
Note: Refer chapter 16: Graphs for more detailed
discussion.
Graph Traversals
A primary problem concerning the graphs is the
reachability. A number of graph problems involve
traversal of a graph. Traversal of a graph means
visiting each of its nodes exactly once. This is
accomplished by visiting the nodes in a systematic
manner. Two commonly used techniques of graph
traversal are depth-first search (DFS) and
breadth-first search (BFS). These algorithms work for both
directed and undirected graphs.
Depth-First Search
Depth-first search is a generalization of the
preorder traversal of a tree. DFS can serve as a structure
around which many other efficient graph algorithms
can be built.
As an example of dfs, suppose in the graph of the
following figure, we start at node A. A
complete program listing is given in Program 31(a).
Program 31(a): Depth-First Search
class Node
{ int label; // vertex label
Node next; //
next node in list
Node( int b )
// constructor
{ label = b;
}
}
class Graph
{ int size;
Node
adjList[];
int mark[];
Graph(int n)
// constructor
{ size = n;
A B C D E
A 0 1 0 1 1
B 1 0 1 1 0
C 0 1 0 1 1
D 1 1 1 0 0
E 1 0 1 0 0
Undirected Graph Adjacency list
A
B
C
D E
B A C D X
E A C X
A B D E X
D A B C X
C B D E X
Adjacency matrix82 Lab Manual Data Structures
through Java
adjList = new
Node[size];
mark = new
int[size]; // elements of mark are initialized to 0
}
public void
createAdjList(int a[][]) // create adjacent lists
{
Node p; int
i, k;
for( i = 0; i
< size; i++ )
{ p =
adjList[i] = new Node(i); //create first node of ith adj. list
for( k = 0; k
< size; k++ )
{ if( a[i][k]
== 1 )
{ p.next =
new Node(k); // create next node of ith adj. list
p = p.next;
}
}
}
}
public void
dfs(int head) // recursive depth-first search
{ Node w; int
v;
mark[head] =
1;
System.out.print( head + " ");
w =
adjList[head];
while( w !=
null)
{ v =
w.label;
if( mark[v]
== 0 ) dfs(v);
w = w.next;
}
}
}
///////////////////////// DfsDemo.java
////////////////////////
class DfsDemo
{ public static void main(String[] args)
{ Graph g =
new Graph(5); // graph is created with 5 nodes
int a[][] = {
{0,1,0,1,1}, {1,0,1,1,0}, {0,1,0,1,1},
{1,1,1,0,0},
{1,0,1,0,0}};
g.createAdjList(a);
g.dfs(0); //
starting node to dfs is 0 (i.e., A)
}
}
Output of this program is: 0 1 2 3 4
Here, 0 is for A, 1 is for B, 2 is for C, 3 is for
D, and 4 is for E
Breadth-First Search
Another systematic way of visiting the nodes is
called breadth-first search (bfs). The approach is called
“breadth-first” because from each node v that we
visit we search as broadly as possible by next visiting all
nodes adjacent to v.
The breadthFirstSearch algorithm inserts a node into
a queue, which we assume is initially empty.
Every entry in the array mark is assumed to be
initialized to the value unvisited. If the graph is not
connected, bfs must be called on a node of each
connected component. Note that in bfs we must mark a
node visited before inserting it into the queue, to
avoid placing it on the queue more than once. The
algorithm terminates when the queue becomes
empty. 8. Graphs
83
We assume the graph is represented by an adjacency
list and is globally available. The algorithm
depends on the availability of an implementation of
a queue of integers (here, a simple queue is assumed;
not circular queue). Three methods relating to
queue: qinsert(), qdelete(), and isEmpty() are to be properly
defined before the method for bfs is defined.
Program 31(b): Breadth-First Search
class Node
{ int label; // vertex label
Node next; //
next node in list
Node( int b )
// constructor
{ label = b;
}
}
class Graph
{ int size;
Node
adjList[];
int mark[];
Graph(int n)
// constructor
{ size = n;
adjList = new
Node[size];
mark = new
int[size];
}
public void
createAdjList(int a[][]) // create adjacent lists
{ Node p; int
i, k;
for( i = 0; i
< size; i++ )
{ p =
adjList[i] = new Node(i);
for( k = 0; k
< size; k++ )
{ if( a[i][k]
== 1 )
{ p.next =
new Node(k);
p = p.next;
}
} // end of
inner for-loop
} // end of outer for-loop
} // end of
createAdjList()
public void
bfs(int head)
{ int v; Node
adj;
Queue q = new
Queue(size);
v = head;
mark[v] = 1;
System.out.print(v + " ");
q.qinsert(v);
while(
!q.IsEmpty() ) // while(queue not empty)
{
v =
q.qdelete();
adj =
adjList[v];
while( adj !=
null )
{ v =
adj.label;
if( mark[v]
== 0 )
{
q.qinsert(v);
mark[v] = 1;
System.out.print(v + " ");
} 84 Lab
Manual Data Structures through Java
adj =
adj.next;
}
}
}
} // end of Graph class
class Queue
{ private int maxSize; // max queue size
private int[]
que; // que is an array of integers
private int
front;
private int
rear;
private int
count; // count of items in queue
public
Queue(int s) // constructor
{ maxSize =
s;
que = new
int[maxSize];
front = rear
= -1;
}
public void qinsert(int item)
{ if( rear ==
maxSize-1 )
System.out.println("Queue is Full");
else { rear =
rear + 1;
que[rear] =
item;
if( front ==
-1 ) front = 0;
}
}
public int qdelete()
{ int item;
if( IsEmpty()
)
{
System.out.println("\n Queue is Empty");
return(-1);
}
item =
que[front];
if( front ==
rear ) front = rear = -1;
else front =
front+1;
return(item);
}
public
boolean IsEmpty()
{ return(
front == -1 ); }
} // end of Queue class
//////////////////////////////////////////////////////////
class BfsDemo
{ public static void main(String[] args)
{ Graph g =
new Graph(5);
int a[][] = {
{0,1,0,1,1}, {1,0,1,1,0}, {0,1,0,1,1},
{1,1,1,0,0},
{1,0,1,0,0}};
g.createAdjList(a);
g.bfs(0);
}
}
Output of this program is: 0 1 3 4 2Sorting
32. Write Java programs for implementing the
following sorting methods:
(a) Bubble sort
(b) Selection sort
(c) Insertion sort
(d) Quick sort
(e) Merge sort
(f) Heap sort
(g) Radix sort
(h) Binary tree sort
As soon as you create an important database, you
will probably think of reasons to sort it in various
ways. You need to arrange names in alphabetical
order, students by marks, customers by pin code,
cities in order of increasing population, countries
by GNP, and so on.
Sorting data may also be a preliminary step to
searching it. As we saw in the previous chapter, a
binary search, which can be applied only to sorted
data, is much faster than a linear search.
Because sorting is so important and potentially so
time-consuming, it has been the subject of
extensive research in computer science, and some
very sophisticated methods have been developed.
First we will look at three of the simpler
algorithms: the bubble sort, the selection sort, and the
insertion sort. Besides being easier to understand,
they are actually better in some circumstances than
the more sophisticated algorithms. The insertion
sort, for example, is preferable to quick sort for small
files and for almost-sorted files. In fact, an
insertion sort is commonly used as a part of a quick sort
implementation.
Bubble Sort
The familiar sorting procedure is the bubble sort
(exchange sort). This is the widely known among
beginning students of programming and easy to
understand and program. Of course, it is probably the
least efficient.
We consider an array, ai of size, n. When this
approach is used, there are at most n-1 passes are
required. During the first pass, a0 and a1 are
compared, and if they are out of order, then a0 and a1 are
interchanged; this process is repeated for a1 and
a2, a2 and a3, and so on. This method will cause small
elements to move or “bubble up”. After the first
pass, the array with the largest element will be in the
position n-1 (last location). On each successive
pass, the array with the next largest element will be
placed in position n-2, n-3,.., 1, respectively,
thereby resulting in a sorted array.
After each pass through the array, a check can be
made to determine whether any interchanges
were made during that pass. If no interchanges
occurred, then the array must be sorted and no further
passes are required. An example of bubble sort for
the array {27, 49, 35, 37, 15, 75, 63, 65} is
illustrated in the Table 9.1.
Program 9(a): Bubble Sort
void bubbleSort(Object[] a)
{
int i, pass,
exch, n = a.length;
Object tmp;
for( pass =
0; pass < n; pass++ )
{ exch = 0;
86 Lab Manual Data Structures through Java
for( i = 0; i
< n-pass-1; i++ )
if(
((Comparable)a[i]).compareTo(a[i+1]) > 0)
{ tmp = a[i];
a[i] =
a[i+1];
a[i+1] = tmp;
exch++;
}
if( exch == 0
) return; // sorting finished – return early
}
}
Table 9.1:
Trace of Bubble sort (elements to be interchanged are shown in red colour)
pass 0 1 2 3 4 5 6 7 Process
- 27 49 35 37 15 75 63 65 Original array
1 27 35 49 37 15 75 63 65 49, 35 interchanged
1 27 35 37 49 15 75 63 65 49, 37 interchanged
1 27 35 37 15 49 75 63 65 49, 15 interchanged
1 27 35 37 15 49 63 75 65 75, 63 interchanged
1 27 35 37 15 49 63 65 75 75, 65 interchanged
2 27 35 15 37 49 63 65 75 37, 15 interchanged
3 27 15 35 37 49 63 65 75 35, 15 interchanged
4 15 27 35 37 49 63 65 75 27, 15 interchanged
Selection Sort
One of the easiest ways to sort a list is by
selection. Beginning with the first element in the array, a
search is performed to locate the smallest element.
When this item is found, it is exchanged with the
first element. This interchange places the smallest
element in the first position of the array. A search
for the second smallest element is then carried out.
Examining the items from second position onward
does this. The smallest element is exchanged with
the item in second position. This process continues
until all elements of the array have been sorted in
ascending order. The following is the selection sort
algorithm.
An example of
the selection sort is given in the Table 9.2. The second row (pass 0) of the
table
shows the original unordered array.
Table 9.2:
Trace of Selection sort (elements to be interchanged are shown in red colour)
0 1 2 3 4 5 6
7 pass min a[pass] a[min] swap a[pass], a[min]
49 27 65 37 15 75 63 60 0 4 49 15 49, 15
15 27 65 37 49 75 63 60 1 1 27 27 min = pass
no exchange
15 27 65 37 49 75 63 60 2 3 65 37 65, 37
15 27 37 65 49 75 63 60 3 4 65 49 65, 49
15 27 37 49 65 75 63 60 4 7 65 60 65, 60
15 27 37 49 60 75 63 65 5 6 75 63 75, 63
15 27 37 49 60 63 75 65 6 7 75 65 75, 65
15 27 37 49 60 63 65 75 Sorted list 9. Sorting
87
Program 9(b): Selection Sort
class SelectionSortDemo
{
public static
void main(String[] args)
{
int[] arr = {
49, 27, 65, 37, 15, 75, 63, 60 };
System.out.print("\n Unsorted array:
");
display( arr
);
selectionSort(
arr );
System.out.print("\n Sorted array:
");
display( arr
);
}
static void
selectionSort( int a[] )
{
int n =
a.length;
for( int pass
= 0; pass < n-1; pass++ )
{
int min =
pass;
for( int i =
pass+1; i < n; i++ )
if( a[i] <
a[min] ) min = i;
if( min !=
pass )
{
int tmp =
a[min];
a[min] =
a[pass];
a[pass] =
tmp;
}
}
}
static void
display( int a[] )
{
for( int i =
0; i < a.length; i++ )
System.out.print( a[i] + " " );
}
}
Following output is generated from this program:
Unsorted
array: 49 27 65 37 15 75 63 60
Sorted array:
15 27 37 49 60 63 65 75
Insertion Sort
Insertion sort works very fast on small size arrays.
The insertion sort procedure scans array, a from
a[0] to a[n-1], inserting each element a[j] into its
proper position in the previously sorted sub-array
a[0], a[1], …, a[j-1]. We consider an array of six
elements shown in Table 9.3. 88 Lab Manual Data Structures through Java
Table 9.3: Trace of Insertion Sort (inserted
elements are shown in red)
pass a[0] a[1] a[2] a[3] a[4] a[5] Process
65 50 30 35 25 45 Original array
1 50 65 30 35 25 45 50 is inserted
2 30 50 65 35 25 45 30 is inserted
3 30 35 50 65 25 45 35 is inserted
4 25 30 35 50 65 45 25 is inserted
5 25 30 35 45 50 65 45 is inserted
Program 9(c): Insertion sort method
void insertionSort(Object a[])
{
int i, j, n =
a.length;
Object item;
for( j = 1; j
< n; j++ ) // repeat loop starting from a[1] to a[n-1]
{ item =
a[j]; // element to be inserted
i = j-1;
while( i
>= 0 && ((Comparable)item).compareTo(a[i]) < 0)
{
a[i+1] =
a[i]; // shift element to the right
i = i-1;
}
a[i+1] =
item; // insert element in proper position
}
}
Quick Sort
The algorithm solely depends on the data it
receives. If the data has certain properties, quick sort is one
of the fastest, if not; quick sort can be very slow.
Quick sort can perform quite fast, on average about
O(n log n), but its worst case is a degrading O(n2
). For quick sort, the worst case is usually when
the
data is already sorted.
Quick sort is
naturally recursive. We partition the array into two sub-arrays, and then
re-start the
algorithm on each of these sub-arrays. The partition
procedure involves choosing some object (usually,
already in the array); If some other object is
greater than the chosen object, it is added to one of the
sub-arrays, if it is less than the chosen object, it
is added to another sub-array. Thus, the entire array is
partitioned into two sub-arrays, with one sub-array
having everything that is larger than the chosen
object, and the other sub-array having everything
that is smaller.
Variable a is
an integer array of size, n. The left and right invoke procedure and they are
initialized
with 0 and n -1 respectively; and are the current
lower and upper bounds of the sub-arrays. The indices
newleft and newright are used to select certain
elements during the processing of each sub-array.
Variable amid is the element which is placed in its
final location in the array.
Index left
scans the list from left to right, and index right scans the list from right to
left. A swap is
performed when left is at an element larger than the
pivot and right is at an element smaller than the 9. Sorting
89
pivot. A final swap with the pivot completes the
divide step. The pivot element is placed in its final
proper position in the array. We take the pivot as
the middle element of the array (or sub-array). Table
9.4 illustrates the trace of Quick sort.
Program 9(d): Quick Sort
class QuickSortDemo
{
public static
void main(String[] args)
{
int[] arr = {
65, 35, 15, 90, 75, 45,40, 60, 95, 25, 85, 55 };
System.out.print("\n Unsorted array:
");
display( arr
);
quickSort(
arr, 0, arr.length-1 );
System.out.print("\n Sorted array:
");
display( arr
);
}
static void
quickSort(int a[], int left, int right)
{
int newleft =
left, newright = right;
int amid,
tmp;
amid =
a[(left + right)/2]; // pivot is amid
do //
do-while-loop
{
while(
(a[newleft] < amid) && (newleft < right))
newleft++;
while( (amid
< a[newright]) && (newright > left))
newright--;
if(newleft
<= newright)
{ tmp =
a[newleft];
a[newleft] =
a[newright];
a[newright] =
tmp;
newleft++;
newright--;
}
}
while(newleft <= newright); // end of do-while-loop
if(left <
newright) quickSort(a, left, newright);
if(newleft
< right) quickSort(a, newleft, right);
}
static void
display( int a[] )
{
for( int i =
0; i < a.length; i++ )
System.out.print( a[i] + " " );
}
}
Output:
Unsorted
array: 65 35 15 90 75 45 40 60 95 25 85 55
Sorted array:
15 25 35 40 45 55 60 65 75 85 90 95 90 Lab Manual Data Structures through Java
Table 9.4: Trace of Quick sort
step a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 left
right pivot
0 65 35 15 90 75 45 40 60 95 25 85 55 0 11 45
1 25 35 15 40 45 75 90 60 95 65 85 55 0 4 15
2 15 35 25 40 45 75 90 60 95 65 85 55 1 4 25
3 15 25 35 40 45 75 90 60 95 65 85 55 2 4 40
4 15 25 35 40 45 75 90 60 95 65 85 55 5 11 95
5 15 25 35 40 45 75 90 60 55 65 85 95 5 10 60
6 15 25 35 40 45 55 60 90 75 65 85 95 5 6 55
7 15 25 35 40 45 55 60 90 75 65 85 95 7 10 75
8 15 25 35 40 45 55 60 65 75 90 85 95 9 10 90
9 15 25 35 40 45 55 60 65 75 85 90 95 sorted array
Merge Sort
Merging is the combination of two or more sorted
arrays (or sequences) into a single sorted array.
Following figure illustrates the basic, two-way
merge operation. In a two-way merge, two sorted
sequences are merged into one. Clearly, two sorted
sequences each of length n can be merged into a
sorted sequence of length 2n in O(2n)=O(n) steps.
However in order to do this, we need space in which
to store the result. That is, it is not possible to
merge the two sequences in place in O(n) steps.
Sorting by merging is a recursive,
divide-and-conquer strategy. In the base case, we have a sequence
with exactly one element in it. Since such a
sequence is already sorted, there is nothing to be done. To
sort a sequence of n >1 elements:
• Divide the sequence into two sequences of length ⎡n
2/ ⎤
and ⎣n
2/ ⎦;
• Recursively sort each of the two subsequences; and
then,
• Merge the sorted subsequences to obtain the final
result.
Following figure illustrates the operation of the
two-way merge sort algorithm. We assume to sort the
given array a[n] into ascending order. We split it
into two subarrays: a[0]…a[n/2] and
a[(n/2)+1]…a[n-1]. Each subarray is individually
sorted, and the resulting sorted subarrays are merged
to produce a single sorted array of n elements.
Consider an array of nine elements: {75, 40, 10, 90, 50,
95, 55, 15, 65}. The sort() method divides the array
into subarrays and merges them into sorted
subarrays by merge() method as illustrated in the
figure (Dashed-line arrows indicate the process of
splitting and the regular arrows the merging
process).
10 40 50 75 90
15 55 65
10 15 40 50 55 65 75 90 95
95 9. Sorting
91
Program 9(e): Merge sort
class MergeSort
{ int[] a;
int[] tmp;
MergeSort(int[] arr)
{ a = arr;
tmp = new
int[a.length];
}
void msort()
{ sort(0,
a.length-1); }
void sort(int
left, int right)
{
if(left <
right)
{
int mid =
(left+right)/2;
sort(left,
mid);
sort(mid+1,
right);
merge(left,
mid, right);
}
}
void
merge(int left, int mid, int right)
{ int i =
left;
int j = left;
int k =
mid+1;
while( j
<= mid && k <= right )
{
if(a[j] <
a[k])
tmp[i++] =
a[j++];
else
tmp[i++] =
a[k++];
}
while( j
<= mid )
tmp[i++] =
a[j++];
for(i=left; i
< k; i++)
a[i] =
tmp[i];
}
}
//////////////////// MergeSortDemo.java
///////////////////////
class MergeSortDemo
{ public static void main(String[] args)
{ int[] arr =
{75, 40, 10, 90, 50, 95, 55, 15, 65};
MergeSort ms
= new MergeSort(arr);
ms.msort();
System.out.print("Sorted array:");
for( int i=0;
i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}
Output of this program is:
Sorted array:
10 15 40 50 55 65 75 90 95 92 Lab Manual Data Structures through Java
Heap Sort
The efficiency of the heap data structure provides
itself to a surprisingly simple and very efficient
sorting algorithm called heapsort. The heap sort
algorithm uses a heap tree to sort an array either in
ascending or descending order. It consists of two
phases:
1. Using unsorted data array, build the heap by
repeatedly inserting each element into the heap.
2. Remove the top element (item at the root) from
the heap, and place it in the last location of
the array. Rebuild the heap from the remaining
elements of the array. This process is repeated
until all items from the heap are deleted. Finally,
the array is in sorted order.
A heap is a complete binary tree such that the root
is the largest item (max-heap). The ordering in
a heap is top-down, but not left-to-right. Each root
is greater than or equal to each of its children, but
some left siblings may be greater than their right
siblings and some may be less. Since heaps are
typically stored as arrays, we can apply the heap
operations to an array of integers. We illustrate the
operations as though they are being performed on
binary trees, while they are really defined for the
arrays that represent them by natural mapping.
Program 9(f): Heap sort
class Heap
{ int[] a; // heap array
int maxSize;
// size of array
int
currentSize; // number of nodes in array
public
Heap(int m) // constructor
{ maxSize =
m;
currentSize =
0;
a = new
int[maxSize]; // create heap array
}
public
boolean insert(int key)
{
if(currentSize == maxSize) // if array is
full,
return false;
// return without insertion
a[currentSize] = key; // store the key in the
heap array
moveUp(currentSize++); // move it up
return true;
// insertion is successful
}
public void
moveUp(int index)
{ int parent
= (index-1)/2;
int bottom =
a[index];
while(index
> 0 && a[parent] < bottom)
{ a[index] =
a[parent]; // move node down
index =
parent; // move index up
parent =
(parent-1)/2; // parent <<< its parent
}
a[index] =
bottom;
} 9. Sorting
93
public int
remove()
{
if( isEmpty()
)
{ System.out.println("Heap
is empty");
return -1;
}
int root =
a[0]; // save the root
a[0] =
a[--currentSize]; // root <<< last node
moveDown(0);
// move down the root
return root;
// return deleted item
}
public void
moveDown(int index)
{ int
largerChild;
int top =
a[index]; // save root in top
while(index
< currentSize/2) // while node has at least one child
{ int
leftChild = 2*index+1;
int
rightChild = 2*index+2;
// find
larger child
if(rightChild<currentSize &&
a[leftChild]<a[rightChild])
largerChild =
rightChild;
else
largerChild =
leftChild;
if(top >=
a[largerChild]) break;
a[index] =
a[largerChild]; // shift child up
index =
largerChild; // go down
}
a[index] =
top; // root to index
}
public
boolean isEmpty()
{ return
currentSize==0; }
public void
displayHeap(int[] a)
{ for(int
i=0; i < maxSize; i++)
System.out.print(" [" + i + "]
");
System.out.println();
for(int i=0;
i < maxSize; i++)
System.out.print(" " + a[i] + "
");
}
}
//////////////////////// HeapsortDemo.java ///////////////////////
class HeapsortDemo
{
public static
void main(String[] args)
{
int[] arr = {
50, 20, 30, 10, 40, 70, 60 }; 94 Lab Manual Data Structures through Java
Heap h = new
Heap(arr.length); // create a Heap
// Build heap
by repeated insertions
for(int i =
0; i < arr.length; i++)
h.insert(arr[i]);
// delete and
copy heap’s top item
for( int i =
arr.length-1; i >= 0; i-- )
arr[i] =
h.remove();
System.out.println("\nSorted array:
");
h.displayHeap(arr);
}
}
Output:
Sorted array:
[0] [1] [2]
[3] [4] [5] [6]
10 20 30 40
50 60 70
Radix Sort
This sorting algorithm is known as
least-significant-digit-first radix sorting. Radix sorting is practical
for much larger universal sets. Radix sorting can be
used when each element of the universal set can be
viewed as a sequence of digits (or letters or any
other symbols).
An implementation of radix sort follows. The integer
radix is assigned a value 10 and integer
maxDigits is also assigned the maximum number of
digits for the maximum element of the array.
This algorithm does not depend on comparison of
array elements. For each array element, two
operations are performed:
(1) To get the significant digit (m) of the number,
the array element is divided by the divisor, and
division modulo radix(10).
(2) This array element is inserted in the mth queue.
In each pass, all array elements are added to the
queues, and then the elements are deleted from all
the queues and stored back to array. The method
requires additional space for queues. The ten queues
are implemented by linked lists using
java.util.LinkedList class.
Program 9(g): Radix sort
class RadixSortDemo
{
public static
void main(String[] args)
{
int[] a = {
3305, 99, 52367, 125, 10, 12345, 7, 35, 7509, 3, 345 };
radixSort(a,
10, 5);
System.out.println("Sorted list:
"); 9. Sorting
95
for(int i =
0; i < a.length; i++ )
System.out.print( a[i] + " ");
}
static void radixSort(int[] arr, int radix, int
maxDigits)
{
int d, j, k,
m, divisor;
java.util.LinkedList[]
queue
= new
java.util.LinkedList[radix];
for( d = 0; d
< radix; d++ )
queue[d] =
new java.util.LinkedList();
divisor = 1;
for(d = 1; d
<= maxDigits; d++) // Pass: 1, 2, 3, . . .
{
for(j = 0; j
< arr.length; j++)
{
m =
(arr[j]/divisor) % radix;
queue[m].addLast(new Integer(arr[j]));
}
divisor =
divisor*radix; // 1, 10, 100, ...
for(j = k =
0; j < radix; j++)
{
while(
!queue[j].isEmpty())
arr[k++] =
(Integer)queue[j].removeFirst();
}
}
}
}
Output:
Sorted list:
3 7 10 35 99 125 345 3305 7509 12345 52367
Binary Tree Sort
When we traverse a binary search tree in inorder,
the keys will come out in sorted order. In tree sort,
We take the array to be sorted, use the method
buildTree() to construct the array elements into a
binary search tree, and use inorder traversal to put
them out in sorted order.
Program 9(h): Binary Tree Sort
class BSTNode
{ int data;
BSTNode left;
BSTNode
right;
BSTNode( int
d ) // constructor
{ data = d; }
} 96 Lab Manual Data Structures through Java
class BinarySearchTree
{
int i;
int[] a;
BSTNode root;
BinarySearchTree(int[] arr) // constructor
{
a = new
int[arr.length];
a = arr;
}
private void
buildTree()
{
for( i = 0; i
< a.length; i++ )
root =
insertTree( root, a[i] );
}
private
BSTNode insertTree(BSTNode p, int key)
{
if( p == null
)
p = new
BSTNode(key);
else if( key
< p.data)
p.left =
insertTree( p.left, key);
else p.right
= insertTree( p.right, key);
return p;
}
public void
treeSort()
{
buildTree();
i = 0;
inorder(root);
}
private void
inorder(BSTNode p) // 'p' starts with root
{
if( p != null
)
{
inorder(p.left);
a[i++] =
p.data;
inorder(p.right);
}
}
public void
display()
{
for( i = 0; i
< a.length; i++ )
System.out.print(a[i] + " " );
}
}
//////////////////////// TreeSortDemo.java
//////////////////////////
class TreeSortDemo
{
public static
void main(String args[])
{
int arr[] = {
55, 22, 99, 77, 11, 88, 44, 66, 33 };
BinarySearchTree bst = new
BinarySearchTree(arr); 9. Sorting
97
bst.treeSort();
System.out.print("Sorted array: ");
bst.display();
}
}
Output:
Sorted array:
11 22 33 44 55 66 77 88 99 KMP Algorithm
33. Write a Java program for implementing KMP
pattern matching algorithm.
The KMP algorithm compares the pattern to the text
in left-to-right, but shifts the pattern, P more
intelligently than the brute-force algorithm. When a
mismatch occurs, what is the most we can shift the
pattern so as to avoid redundant comparisons. The
answer is that the largest prefix of P[0..j] that is a
suffix of P[1..j].
Program 33: KMP pattern matching
class KMPDemo
{
public static
void main(String[] args)
{
String T =
"THE RIVER MISSISSIPPI FLOWS IN NORTH AMERICA.";
String P =
"SSIPP";
boolean
isMatch = kmp(T, P);
if(isMatch)
System.out.println("Pattern " + P
+ " is
present in text: " + T);
else
System.out.println("Pattern " + P
+ " is
not present in text: " + T);
}
static
boolean kmp(String T, String P)
{
int n =
T.length();
int m =
P.length();
int[] fail =
computeFailFunction(P);
int i = 0; //
text index
int j = 0; //
pattern index
while( i <
n )
{
if(
P.charAt(j) == T.charAt(i) )
{
if( j == m-1
) return true;
i++;
j++;
}
else
if( j > 0
) j = fail[j-1];
else i++;
}
return false;
}
static int[]
computeFailFunction( String P )
{
int m =
P.length();
int[] fail =
new int[m];
fail[0] = 0;
int i =
1; 10. KMP Algorithm
99
int j = 0;
while( i <
m )
{
if(
P.charAt(j) == P.charAt(i) ) // j+1 characters match
{
fail[i] =
j+1;
i++;
j++;
}
else if( j
> 0 ) // j follows a matching prefix
j =
fail[j-1];
else // no
match
{ fail[i] =
0;
i++;
}
}
return fail;
}
}
Output:
Pattern SSIPP
is present in text:
THE RIVER
MISSISSIPPI FLOWS IN NORTH AMERICA
No comments:
Post a Comment