data structure - sorting

BUBBLE SORT

BUBBLE _SORT [N,A]


The bubble sort loops through the elements in the list comparing the adjacent element and moves the largest element to the top of the list

Here , n= total no of elements
a= represent the list of element
i &j =are the integer variable
Temp=temporary variable of type integer


step 1: [ Initialize]

I0


Step 2: repeat through step 5 while (i a[j+1]) then

(temp is a temporary variable which store the largest element )

tempa[j]
a[j]  a[j+1]
a[j+1]  temp

endif

step 6: Exit






SELECTION SORTING


SELECTION _SORTING (A,N)



Selection sorting starts from fist element and searches the entire list until finds the minimum value. The sort places minimum value in the first place, select the second element and searches for the second smallest element.

Here , n= represent the size of list
a= represent the list of elements
i &j =are the integer variable
Temp=temporary variable of type integer


Step 1: [initialize]

I0

Step 2: Repeat through step 7 while ( i a[j]) then

(temp is a temporary variable which store the largest element )

temp a[j]
a[j]  a[j]
a[j]  temp

endif

step 6: j  j+1

step 7: I I+1

step 8: Exit



LINEAR SEARCH

LINEAR _SEARCH (I,N,KEY)

This is a technique to find out an element an unsorted list. In this technique value is compared with the first element if match is found then search is successful otherwise next element from the list is fetched and compared with the key.
This process is continue till the key is found or list is completed.

Where a= represent the list of element
N=represent the no of element in the list
Key=represent the value to be search in the list
Flag =0 means True
Flag =1 means False


Step 1: [initaialize]

I0
Flag1

Step 2: Repeat step 3 for k=0,1,2………..n-1

Step 3: a[i] = key then

Flag0
( prompt the message search successful)
write “search is successful”
(increasing the value of variable I by 1)

II+1

Step 4: [prompt the message if search is not done]
Write “Search is unsuccessful”

Step 5: Exit








BINARY SEARCH

BINARY_SEARCH (KEY,N,A)

Binary search works for sorted list and is a very efficient technique.It is use to find the location of a given element or record in a list.


Where low= lower limit of the list
upper =upper limit of the list
mid= average of low and high

a= represent the list of element
N=represent the no of element in the list
Key=represent the value to be search in the list
Flag =0 means True
Flag =1 means False



Step 1: [initialize]

Low0
uppern-1
Flag1

Step 2: Repeat through step 4 while ( low<=upper) Step 3: [find average] mid (low+upper)/2 step 4: if (key = a[I]) then (change the lower to mid) uppermid-1 else if (change upper to mid) lowmid+1 else if (when key is found) (key = a[mid]) write “Search is successful” flag0 return step 5: if (flag =1) write “search is unsuccessful” step 6: Exit DOUBLE ORDER LINK LIST DOUBLE_LIST (HEAD,VAL) [This function to insert an element in the list which sorted to its info field and value is the info field of the new node and prev is the field which point to previous node] step 1: [Allocate the memory for the new node] new=node step 2: [Copy the information field of the new node] info(new)=val step 3: [is the list empty?] if (temphead=NULL) then temphead newnode next(temphead) NULL return (temphead) step 4: [does the newnode precede all other node in the list?] if (val < info(temphead) then prev(newnode) prev(temphead) next(newnode) temphead tempheadnewnode return (temphead) else firsttemphead while(val > info(next(temphead)) && next(temphead) !=NULL)
tempheadnext(temphead)

endwhile

next(newnode) next(temphead)
prev(newnode) temphead
next(temphead) newnode
return (first)
step 5: exits

Read More

data structure - tree

1. Algorithm For Create of Binary Tree:-

Function CREATE(T,VAL)
[ROOT=Dummy header for the root of the binary tree initialized by NULL,
NEWNODE=Variable points to the new element,
T=Temporary variables for traverse the tree,
INFO=Information part of node.]

Step 1: [Allocate the memory for new node .]
NEWNODE<=NODE

Step 2: [Read the element.]
Read(VAL)

Step 3: [Store element into new node.]
INFO(NEWNODE )VAL

Step 4: [Temporary store right and left tree is NULL.]
LEFT(NEWNODE)RIGHT(NEWNODE)NULL

Step 5: [Check if the root is NULL.]
If ROOT=NULL
Then
ROOTNEWNODE
Return

Step 6: [Search the place to insert the element.]
While T!=NULL
(Check for element is less than information of T)
if VAL < INFO (T)
then
PARENTT
TLEFT(T)
Else
PARENTT
TRIGHT(T)

Step 7: [Check element is less than information of parent.]
If VAL < INFO(PARENT)
Then
LEFT(PARENT)NEWNODE
Else
RIGHT(PARENT)NEWNODE


2. Algorithm For Inorder Traversal of Binary Tree:-

Function INORDER(T)
[T = Temporary pointer variable initialized with root,




INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node,]

Step 1: [Repeat step 2,3,4 and check that T is not equal to NULL ]
If T!=NULL
Then

Step 2: [Call function itself as a left most node.]
INORDER(LEFT(T))

Step 3: [Print information part of node.]
Write INFO(T)

Step 4: [Call function itself as a right most node.]
INORDER(RIGHT(T))


3. Algorithm For Preorder Traversal of Binary Tree:-

Function PREORDER(T)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node,]

Step 1: [Repeat step 2,3,4 and check that T is not equal to NULL ]
If T!=NULL
Then

Step 2:[Print information part of node.]
Write INFO(T)

Step 3: [Call function itself as a left most node.]
PREORDER(LEFT(T))

Step 4: [Call function itself as a right most node.]
PREORDER(RIGHT(T))



4. Algorithm For Postorder Traversal of Binary Tree:-

Function POSTORDER(T)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node,]

Step 1: [Repeat step 2,3,4 and check that T is not equal to NULL ]
If T!=NULL
Then

Step 2: [Call function itself as a left most node.]
POSTORDER(LEFT(T))

Step 3: [Call function itself as a right most node.]
POSTORDER(RIGHT(T))

Step 4: [Print information part of node.]
Write INFO(T)


5. Algorithm For Depth of Binary Tree:-

Function DEPTH(T, LEVEL)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node.]

Step 1: [Repeat step 2,3,4 and check that T is not equal to NULL ]
If T!=NULL
Then

Step 2: [Check D is less than LEVEL.]
If D Then
(Store LEVEL into D)
DLEVEL

Step 3: [Call function itself as a left most node.]
DEPTH(LEFT(T),LEVEL+1)

Step 4: [Call function itself as a right most node.]
DEPTH(RIGHT(T),LEVEL+1)

Step 5: [Print the LEVEL.]
Write ‘level’,D


6. Algorithm For Search of Binary Tree:-

Function SEARCH(T,KEY)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node.]

Step 1:[Read the KEY]
Read(KEY)
Step 2: [Repeat step 2,3,4 and check that T is equal to NULL ]
If T = NULL
Then
(Prompt the message key not found)
write ‘Key not found’
return

step 3: [Check the that information of T is equal to key.]
If INFO(T)=KEY
Then
(Prompt the message key found)
write ‘Key found’
return

step 4: [Check that key is less than information of T.]
If KEY Then
(Call function itself as a left most node.)
SEARCH(LEFT(T),KEY)
Else
(Call function itself as a right most node.)
SEARCH(RIGHT(T),KEY)


7. Algorithm For Modify of Binary Tree:-

Function MODIFY (T,KEY,VAL)
[T = Temporary pointer variable initialized with root,
INFO=Information part of node,
LEFT=Pointer to left most node,
RIGHT=Pointer to right most node.
VAL=New element.]

Step 1: [Read the KEY]
Read (KEY)

Step 2: [Read the value.]
Read(VAL)

0Step 3: [Repeat step 4,5,6 and check that T is equal to NULL ]
If T = NULL
Then
(Prompt the message key not found)
write ‘Key not found’
return

step 4: [Check the that information of T is equal to key.]
If INFO(T)=KEY
Then
(To store value in information of T)
INFO(T)VAL
return

step 5: [Check that key is less than information of T.]
If KEY Then
(Call function itself as a left most node.)
MODIFY(LEFT(T),KEY,VAL)
Else
(Call function itself as a right most node.)
MODIFY(RIGHT(T),KEY,VAL)

Read More

circular queue

4) CIRCULAR QUEUE :

7) Procedure ( VAL )
[Description]

Step 1: [Check Queue is overflow or not]

If REAR = 0 AND REAR=SIZE – 1
Then
Write (‘Overflow…..’)
Return

If REAR = FRONT -1
Then
Write (‘Overflow…..’)
Return

Step 2: [If needed Reset the pointer, and insert value]

If REAR = SIZE – 1
Then
REAR = 0
Q [REAR]  VAL

Else If REAR= -1
Then
REAR  FRONT  0
Q [REAR]  VAL
Else
REAR  REAR +1
Q [REAR]  VAL
Step 3: [Finished]

Return
--------------------------------------------------------------------------------------------
8) Function DELETE ( )
[Description]

Step 1: [Check Queue is empty or not]

If FRONT < 0
Then
Write (‘Queue Underflow……’)
Return -1

Step 2: [Delete an element]

VAL  Q [FRONT]

Step 3: [Queue Empty?]

If FRONT = REAR
Then
FRONT  REAR  -1
Else If FRONT = SIZE – 1
Then
FRONT  0
Else
FRONT  FRONT + 1

Step 4: [Return the Deleted element]

Return VAL
----------------------------------------------------------------------------------------------
9) Procedure PRINT
[Description]

Step 1: [Check Queue is empty or not]

If FRONT < 0
Then
Write (‘Underflow…..’)
Return

Step 2: [Print the element of Queue]

If FRONT < = REAR
Then
Repeat for I = FRONT, FRONT+1…… I < = REAR
Write Q [I]
Else
Repeat for I = FRONT, FRONT+1…… I < SIZE
Write Q [I]
Repeat for I = 0, 1….I < = REAR
Write Q [I]

Step 3: [Finished]

Return

Read More