Tuesday, September 6, 2011

Algo for Searching and Sorting


Linear Search
This is most frequently used search method. We simply traverse the list or array or records and
check if the identification number matches with the id number of our interest.

Algorithm:
Begin:
Found = false
Count = 0
Obtain the input array.
Obtain number of terms, key
Do
{ If array[count]== key
Found = true.
Else
Count ++
} while ( count <=N) && found==false)
if false declare the key is not present in the array
Else declare the position and value of the element
End

Binary Search Algorithm
Algorithm
begin :
max=length-1
min=0;
success=false
while ((!success) && max>=min)
{
mid=max+min/2
if ( mid==key)
declare the result. Mid is the position. success=true;
else
if key < array[mid]
// adjust max to left sub array
Max = Mid-1
Else
Min=min+1
end

Bubble Sort
Algorithm
Procedure bubblesort(sort[],len)
for i=1 to len-1 do
begin
for j=0 to len-i do
begin
if [sort[j] > sort[j+1]
swap (sort[i],sort[j+1])
end
end
return

Selection Sort
Algorithm :
Selectsort(sort[],len)
for i=0 to i<len-1 do
begin
min=i
for j=i+1 j<len do
begin
if[sort[j] < sort[min]
min=j
end
if(min != i)
swap(sort[min],sort[i])
end

INSERTION SORT
Algorithm for Insertion Sort
for i=1 to i<len
begin
temp = sort[i]
for j=I to j=1
for j=i to j=1
begin
if [sort[j-1] > temp]
sort[j] = sort[j-1] // shift one position to the right
end
sort[j] = temp
end

QUICK SORT
Procedure QSort[int sort[], int lo, int hi]
Where sort[] is the input array which has to be sorted, ‘lo’ and ‘hi’ are indexes to the first and last
elements of the sub array that has to be sorted.
If (lo >= hi)
Return;
Initialize :
i = lo-1
j = hi
pivot = sort[hi] // set pivot element to print to last element of the array
while (i < j)
{
while (Sort[++i] < pivot);
while (j>=0 && sort[—j] > pivot);
if (i<j)
swap(sort[i],sort[j])
}