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

Step 3: [Initialize]

J0

Step 4: repeat through step 5 while ( j< n-i)


Step 5: if (a[j] > 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
Step 3: [initialize]

J I+1

Step 4: Repeat through step 6 while (j
step 5: if (a[j] > 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