Chapter -16

Sorting Techniques

Introduction:
Sorting is very important in every computer application.Sorting
refers to arranging of data elements in some given order
There are different sorting techniques(a) Bubble sort
(b) Selection sort
(c) Insertion sort
(d) Quick sort
(e) Merge sort
(f) Raddix sort
(g) Heap sort
BUBBLE SORT
Suppose the list of number a [1], a [2]a[n] is in the memory. The bubble sort
algorithm work as follows
STEP 1:Compare a [1] and a [2] and arrange them in desire order, so that a[1]<a[2] then
compare a[2] and a[3] and arrange them,
Continue until we compare a [n-1] with a[n]
Observe the step 1 involves (n-1) comparison. During step 1, the largest element is
bubbled upon the nth position or sinks to the nth position. When step 1 is completed
a[n]will contain the largest element.
STEP 2: Repeat step 1 with one less. Comprising and possibly rearranging a [n-2] and a
[n-1]
_
_
STEP (N-1): Compare a[1] with a[2] and arrange then so that a[1]<a[2]
After n-1 step, the list will sorted in increasing order. the above process of sequentially
traversing through all that list frequently is called a pass so each of the above step is
called as pass accordingly , the bubble sort algorithm requires n-1 passes, where n is the
number of input item.
Example 1:
Suppose the foolowing numbers are sorted in an array a.
32, 51,85,66,23,13,10,57

PASS 1:

(1)32

51 27

85

(2)32

51 27

85

(3)32

27 51

(4)32

27

(5)32

27

(6) 32

66

85

51
51

27

66

85
66

51

66
66
85

66

23

(7)

32

27

51 66 23

(8)

32

27

51

66 23

23

13

23

57

53

23
23
23

57

13
13
13

(EXCHANGE 27<85)

57
67
57

(EXCHANGE 66<85)
(EXCHANGE 23<85)

85

13

67

(EXCHANGE 13<85)

13

85

57

(EXCHANGE 13<85)

13

57

85

SELECTION SORT
A selection sort is one in which successive element are selected in order and placed into
their proper position. The selection sort is used to find the smallest element along a [1], a
[l-1],a[n], and interchange it with A[1]. The interchange places the smallest element
is the first position in the table. Similarly again locate the second smallest element. Then
this element is placed at A[L+1]
The process of location or finding for the smallest element continues k until all the
elements have been sorted in ascending order. if n element are present then. (N-1)
comparison is required. Hence the number of comparison are proportional to n2 i.e. 0(n2)
EXAMPLE
PASS 1:

11

56

47

36

24

91

85

PASS 2:

11

24

47

36

56

91

85

32

PASS 3:

11

24

32

36

56

91

85

47

PASS 4:

11

24

32

36

47

91

85

56

PASS 5:

11

24

32

36

47

56

PASS 6:
PASS 7:

11
11

24

24
32

32
36

36
47

47
56

85

91

56

85

85

91

ALGORITHM:
SEL_SORT (A, N, MIN, TEMP)
STEP 1:
START
STEP 2:
REPEATE STEP 4, 5 FOR I=1 TO N BY 1
STEP 3:
SET MIN=A[i]
STEP 4:
REPEATE STEP FOR J=i+1 TO N BY 1
IF A [J] <MIN, THEN
SET TEMP= A[j]
A[j] = MIN

32

91

MIN = TEMP
X=j
END OF IF
END OF STEP 4 LOOP
IF A[i] <MIN, THEN
SET TEMP=A[i]
A[i] =MIN
A[X] =TEMP
[END OF IF]
[END OF SYEP 2 LOOPS]
EXIT

STEP 5:

STEP 6:

QUICK SORT:
Quick sort is a sorting algorithm which is based on divide and conquerrule. The three step
divide and conquer is given below to sort typical sub arrayA [p..r].
DIVIDE:
The array A[PR].IS Portioned (rearranged) into two non-empty sub array A[P...Q] and
a [Q+1.R] such that each element of A [pq] is less than or equal to each element of A
[q+1r]. The index q is computed as part of this portioning procedure.
Conquer:
The two sub arrays A[pq] and A[q+1r] are sorted by recursive calls to quick sort.
Combine:
Since the sub arrays are sorted in place, no work is needed to combine them, the entire
array a [p..r] Is now sorted.
The following function implements the quick sort.
QUICK SORT (A,p,r):
Step 1: if (p<r) then
Q= portioned (A,p,r)
Step2: quick sort (A,p,q)
Step 3:Quick sort (A,q+1,r)
Step 4: stop:
Portioned list:
Now we must construct the function portioned. There are several method that we might
us , method that sometimes are faster than the algorithm we develop but that are intricate
and difficult to get correct. The algorithm we develop is much simpler and easier to
understand, and it is certainly not slow; in fact it does the smallest possible number of
key comparisons of any portioning algorithm.
Choice of pivot:

We are not bounded to the choice of the first item in the list as the pivot; we can choose
any item we wish a swap it. With the first item before beginning the loop that portions the
list. In fact first item is often a poor choice for pivot. Since if the list is already sorted,
then the first, key will have no other less than it, and so one of the sub list will be empty.
Hence let us instead choose a pivot near the center of the list, I the hope that our partition
the keys so that about have come on each side of pivot.
PARTIONING ARRAY:
The key to algorithm is PARTIONED function, which rearrange the sub array
A[p..r ] in the place
PARTITION (A,P,R):
Step 1: x=A[p],i=p-1,j=r+1
Step 2: as long as A[j]<=x,j=j-1,
Step 3: increment i value as long as
A[i]>=x
Step 4: if (i<j) then
Swap A[i] and A[j]
Else return j.
Step 5: if (i<j) then stop step 2
Step 6: stop
INSERTION SORT:
Suppose array A with n elements A [1],A [2]..A[N]. the insertion sort algorithm
scans A from A[1] TO A[N],inserting each element A [K] into its property position is the
previously sorted array [1],A[2]A[K-1]. That is,
PASS 1: A[1] by itself is trivially sorted.
PASS 2: A[2] is inserted either before or after A[1] so that A[1],A[2] is sorted.
PASS 3: A[3] is inserted into its proper position is A[1],A[2] that is before A[1],between
A[1] and A[2] or after A[2],so that A[1],A[2] and A[3] is sorted.
PASS 4: A[4] is inserted into its proper position in A[1],A[2],A[3],A[4] is sorted.
--

-PASS N: A[N] is inserted into its paper place in A[1],A[2],A[N-1] so that

A[1],A[2],..A[N] is sorted.
The idea of this method is to be placed an unsorted element into its correct position in
a growing sorted list of data.

SORTED LIST

UNSORTED LIST

ALGORITHM:
1.
2.
3.
4.
5.
6.
7.
8.
9.

Accept n number into array data

2. Data [0] is considered a sorted file of one element
Next=1
New element = data[next]
Move all element 7 new element by one position to the right
Insert new element in the array at the position where step 5 is terminated
Next >next+1
Continue from step 4 as long as next <n
stop

Merge sort:
It basically works on the principle of divide and conquers technique. In the method
first we divide the list in two sub list, with each sub list of almost equal sizes. Continue
dividing the list till sub list reduce to unit length. Merge the sub list which will be in
sorted order.
Example 9:
Sort the following set of number, using merge sort method.
40 60 70 50 20 10 30.
We now break the list in two sub lists.
First sub list: 40 60 70 50
Second sub list:20 10 30
Again subdivide first sub list: 40, 60 and 70,50

Further division gives us

40
40, 60

, 60
And

and 70
50,7
0

, 50

Merge these two:

40, 50,
60, 70

Now divide the second sublis

20, 10

And 30

20

10

10, 20

And 30
30

Merge
Merge
10, 20, 30

Now merge the two sub list:

40, 50, 60,
70

10, 20, 30

10 20 30 40 50 60
70

Radix Sort:
In this sorting records or elements of the table are arranged in sequential order.
For numeric data of decimal number , suppose there are 9 packets corresponding to the
decimal digits are to be sorted
348,143,361,423,538,128,321,543,366
These number would be sorted in three phase.
1. In first pass, the in it digits are sorted into packets. The cards are collected
packets , from 9 to packet 0.
2. In second pass, the 10 digits are sorted into packets.
3. In the third and final pass, the 100 digits are sorted into packets.

Chapter-17 Graphs
Introduction:

In this chapter we will be another non-linear data structure: the graph which is widely
used to solve many real life problems .Basically the graph is collection nodes called
vertices and line segments connecting pairs of vertices called line or edges.
Definition and Terminology:
Graph:
Definition:
A graph is a collection of two sets V and E, where
a. A set of V elements called nodes (or points or vertices)
b. Set E of edges such that e in E is identified with unique (unordered) pair [u,v]
of nodes in V , denoted by e=[u,v]
A graph can be denoted by G= (V, E) or an edge is represented by two adjacent
vertices G is represented as G= [V, E].
In above definition e represents edge u and v are endpoints in e , u and v are said
to be adjacent or neighbours.
Example1:

A
D

B
B
B

G= (V, E)
V= [A, B, C, D]
E= {(A, B),(B,C),(C,D),(D,A)}

Fig: 8.1 Example of graph

Here A, B, C, D are nodes, lines between A, B, C, D are called as edges.
8.2.2 Types of graphs:
There are two types of graphs
(a)
Undirected graph
b. Directed graph
a. Undirected graph :
An undirected graph is a graph in which there is no direction on the lines
,known edges.In an undirected graph , the flow between two vertices can go in
either direction .
Undirected graph;
An undirected graph (represented as G =(V,E)) is one where each edge E is
an unordered pair of
vertices.Thus the pair
(V1,V2) and
(V2,V1) represent the
same edge.
Example 2:

Fig :8.2 :
The above graph G1 and G2 are undirected graph where G2 is also a tree .Tree are special
case of graphs.
For G1
G1=(V,E)
V(G1)={A,B,C,D}
E(G1)={(A,B),(A,C),(A,D),(B,C),(B,D),(C,D)}
For G2
G2=(V,E)
V(G2)={A,B,C,D,E,F,G}
E(G1)={(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)}
(b)

Directed graph :
A directed graph is also called as diagraph or graph .A directed
graph is one where each edge is represented by a specific
direction or by a directed pair or each edge is represented by a
pair of ordered vertices i.e an edge has a specific direction.
Suppose G is directed graph with directed edges e=(u,v).Then e
is also called as an arc.Following terminology used :
(i) e begins at u and ends at v.
(ii) u is the origin or initial points of e , and v is the destination or terminal point of e.
(iii)
u is a predecessor of v and v is successor or neighbour at u.
(iv)
u is a adjacent to v and v is adjacent to u.
(v) The out degree of a node is the number of edges beginning at u.
(vi)
The indegree of a node is the number of edges ending at u.
(vii)
A node is called a source if it is has a positive outdegree but zero indegree.
(viii)
A node is called sink if it has a zero outdegree but positive indegree.
G =(V,E)
V =[A,B,C,D]

E ={e1,e2,e3,e4,e5,e6}

Fig : 8.3 Directed graph Terminology :

(a)

(b)

Degree :
It is the number of edges containg a node .It is written as deg(u), where u is a
node.If deg(u) =0,
Then u does not belong to any edge .Then u is called an isolated node.
Isolated vertex :
As said above , if any node does not bellog too any edge then it is called as
isolated node.
Example 3:
Node E is isolated graph

Fig : 8.4 Graph

(c)

(d)
(e)
(f)

Path :
It is sequence of vertices in which each vertex is adjacent vertices to the next
one .
Length of path :
The length of a path is the number of edges on it.
Linear path :
A linear path is a path whose first and last vertex are distinct.
Cycle:
A cycle is a closed graph with length 3 or more , such that starts and ends with
same vertex.

(g)

(h)

(i)

Fig : Graph with cycle

Complete graph :
A graph G is said to be complete if every node in graph is adjacent to every
other node .A complete graph with n nodes will have [n(n-1)/2] edges.
Connected graph:
Two vertices vi and vj are said to be connected if there is a path in G from vi and
vj.
Subgraph :
A subgraph of G is a graph G such that V(G) V(G) and E(G) E(G)

Example4:

Fig :(A )Graph G1

(j)
(k)

(l)

(B) Subgraph of G1

Labeled graph :
A graph G is said to labeled if its edges are assigned data.
Weighted graph :
A graph G is said to be weighted if each edge e in G is assigned a non-negative
numerical value W(e) called weight or length of e. in such a case , each path P
in G is assigned a weight or length which is the sum of the weights of the
edges along the path P.
Multiple edge :
If one or more edges connects to the same endpoints then edges.
e2
10
e1

Ae3

4
B

Fig :8.7 : Weighted graph

Fig : Multiple edges

Representation of graph :
There ar two standard ways of maintaining a graph G in the memory of
computer.
1. Sequential representation of G , is by means of its adjacency matrix of A
2. Linked representation of G , is by means of linked list of neighbours.
Sequential representation of Graph :
Sequential representation of graph is done by adjacency matrix.
(a)
Adjacency matrix :
The adjacency matrix A of graph G is a two dimensional
array n*n elements where n is the number of vertices .Then
entries of A are defined as ,
A[i][j]=1 ,if there exists an edge between vertex I and j in G.
A[i][j]=0 ,if no edge exists between I and j .

 Suppose G is a simple directed graph with m nodes and

suppose nodes of G have been ordered and are called
V1,V2 Vm.Then the adjacency matrix A=(aij) of the
graph G is the n*n matrix defined as follows
Aij = 1 if vi is adjacent to vj , that I , if
there is an edge (Vi , Vj)
0 otherwise
Such a matrix , which contains entries of only 0
and 1 , is called a Bit matrix or a Boolean matrix.
The adjacency matrix A of graph G does not depends on the
ordering of the nodes of G , that is a different ordering of the
nodes may result in a different adjacency matrix .However ,
the matrices resulting from two different ordering are closely
related is that , one can be obtained from the by simply
interchanging rows and columns .
Otherwise , assume that the nodes of the graph G have fixed
ordering .
If graph G is an undirected graph then adjacency matrix will
be a symmetric matrix.
For example :
A

Fig :graph

Example 6 :
Consider the graph given

2
3

(1)
(2)

Give adjacency matrix representation .

Give adjacency list representation.

1)Adjacency matrix =
2) Adjacency list :
Start
1

Example 8 :
Given adjacency matrix

Example: To find the path matrix of graph given below

Directed graph
Bm =A1+A2+A3+.+Am
A above graph G has 4 node
m=4
B4=A1+A2+A3+A4
And replacing non-zero entries in B4 by 1.
We obtained the path matrix P of graph G.
A1

A2

A3 =

0 0 1 1
0 0 0 1
A=
4

B4=

Replacing nonzero elements by 1,

B4=

The above graph is not strongly connected; since the path.

Matrix P of G has zero entries.
Example: Write Warshalls algorithm (write comments wherever applicable) for
graph shown below.

i)prepare adjacency matrix

ii) Prepare path matrix applying Warshalls
algorithm

i)Adjancey matrix
=V1

V2

V3

V4

A=

V2
V3
V4

ii) Prepare path matrix applying Warhalls algorithm

0

A2=A*A=

A2 =
A3=

A1=

0 1

0 0

0 0

0 1

A3=

A4=

B4=A1+A2+A3+A4

Path

B4=

matrix=

DEPTH FIRST SEARCH:

The idea behind a depth first search beginning at a starting node A is as follows: first we
examine the starting node A. then we examine each node N along path P which begins at
A, that is we process a neighbor of A, the neighbor of neighbor of A and so on.
After coming to a dead end that is to the end of path P , we backtrack on P until we can
continue along another path P and so on.
This algorithm is similar to breadth first search except we uses stack, instead of queue.
Again, a field STATUS is used to tell us the current status of a node.
Algorithm:
This algorithm executes a depth first search on a graph G beginning at the starting
node A.
Step 1: initialize all nodes to ready state (STATUS =1)
Step 2: push the starting node A into STACK and change its status to the waiting state
(STATUS =2)
Step 3: repeat step 4 and 5 until stack is empty
Step 4: pop the top node N of stack. Process N and change its status to the processed
state (STATE =3)
step 5: push onto stack all the neighbors of N that are still in the ready state (STATUS
=1),and change their status to the waiting state (STATUS =2)
[End of step 3 loop]
Step 6: Exit.
EXAMPLE:

C
A
E
B
D

Node

Adjacency list

C,B

A,B,C,E

Explanation :
Initially push node B on the stack

Pop and print

neighbors of B

the top element and then push onto the stack all the
in ready state

But in case node B doesnt have any Neighbors and so nothing is pushed onto stack
and empty stack is empty. So the algorithm completes .
Therefore there is no node reachable from node B.
EXAMPLE 23:
Consider the graph G given suppose we want to find and print all the nodes
reachable from the node j(including J itself).
One way to do this is to use a depth first search of G starting at node J. the step are
as follows,
a) Initially push J onto stack

Top
stack

b) Pop and print the top element J and then push onto the stack all the
neighbors of J(those are in the ready state) as follows,

K
(C) Pop and print the top
Stack all the neighbor of k

D
G
E
D

element k, and then push onto the

in ready state

PRINT OUTPUT: J, K
(d) Pop and print the top element g and then push onto the stack all the neighbors
of g in ready state,

C
E
D

(e) POP AND PRINT TOP ELEMENT C AND THEN PUSH ONTO THE STACK ALL
THE NEIGHBOURS OF C IN READY STATE.

F
E
D

(F) Pop and print top element f and then push onto the stack all the neighbors of F
in ready state

PRINT OUTPUT: J, K, G, C, F
Note that the only neighbor D of F is not pushed onto the stack, since D is only in
ready state.
(g) pop and print top element E and then push onto the stack all the neighbours of
E. Even E has 3 neighbours but not in ready state .

Print output: J, K, G, C F, E
(h)pop and print the top element D and push at stack all neighbours of D. since D
neighbours are not in ready state and stack is empty, so the depth first search of
G starting at J is now completed.
J, K, G, C, F, E, D are nodes reachable from node J.

EXAMPLE:
Find and print all nodes reachable from node K for following graph:
(Hint use depth first Search. Show content of stack at the end of each step
with brief Explanation)

Consider the above graph and find all the nodes reachable from K
a. Initially push K onto the

Stack.
K
STACK

b. Pop and print the top element K, and the push onto the stack all the
neighbours of K in ready state.

G
c. Pop and print the top element
the neighbours of g in ready

G, and then push onto the stack all

state.

C
F
Print output : K,G
d. Pop and print the top element C and then push all the neighbours of C in
ready State.

B
F
Print output: K, G, C
e. Pop and print the top element B and then push all the neighbour of B in ready
state .

f.

Pop and print the top element E

neighbour of E. even E has 3

E
F

and push onto the stack all the

neighbour but not in ready state

F
g. Pop and print the top element F
and push onto the stack all the
neighbour of F.since Fneighbour are not in ready state and stack is empty, so
the depth first search of graph starting at K is now complete

K, G, C, E, F are the nodes reachable from node J.

Application of Graph:
Graph can be used in various application like
(a) Representation of electric current flow
(b) Maps indicates connectivity between different places
(c) Telephone and computer networking
(d) Routing from one location to another
(e) Scheduling of interdependent tasks or activities.
(f) Computing projects completion time, delay, early, start and late finish
times for a project which is made up of several tasks.
(g) To find shortest path, for topological sort, critical path method.