2.1.3-searching and sorting algorithms

how to carry out binary search

-calculate the mid-point in the data set

-check if that is the item to be found

-if not

-if the item to be found is lower than the mid-point, repeat on the left half of the data set

-if the item to be found is greater than the mid-point, repeat on the right half od the data set

-repeat until the item is found or there are no items left to check

advantage of binary search

-more efficient than a linear search as more quicker

-can be used on large set of data

disadvantage of binary searches

-requires the data to be ordered

when are scenarios where binary search is not better

-when the item to be found is the first one on the list

algorithm for binary search (don’t have to memorise)

found=false

left=0

right=list.length-1

while found ==false AND left <= right

mid= (left+right) DIV 2

If list[mid] == item_to_find then

found=TRUE

else

if item_to_find > list[mid] then

left=mid+1

else

right=mid-1

endif

endif

endwhile

how to perform a linear search

starting from beginning of a data set, each item is checked in turn to see if it is the ones being searched for

advantage of linear search

-doesnt require the data set to be in order

-will work on any type of storage device

-can be efficient for smaller data sets

disadvantage of linear search

very inefficient for large data sets

algorithm for linear search

found=FALSE
I=0

while NOT found AND NOT end of data set

if item[I] ==item to find then

found=TRUE

output item

endif

I=I+1

endwhile

how does a bubble sort work

-sorts unordered list of items

-compares each item with the next one and swaps them if they are out of order

-the algorithm finishes when no more swaps are made

advantage of bubble sort

-efficient for small data sets because easy to implement

disadvantage of bubble sort

-most inefficient

code for bubble sort

n=list.length

swapped=true

while n>0 AND swapped =true

swapped=false

n=n-1

for i=0 to n

if list[i] > list[i+1] then

temp=list[i]

list[i]=list[i+1]

list[i+1]=temp

swapped=true

endif

next i

endwhile

merge sort

-uses divide and conquer method

-creates two or more identical subprograms from the largest problem and solves them individually

-data set is repeatedly split into half until each item in its own list

-adjacent lists are then merged together

advantage of merge sort

-works very well for larger data sets

insertion sort

-inserts each item into its correct position in a data set one at a time

-it is usually replaced by more efficient sorting algorithms for larger data sets

advantages of insertion sort

-useful algorithm for small data sets

-particularly useful for inserting items into an already sortted list

code for insertion

for i=1 to list.length

c=list[i]

p=i

while p>0 AND list[p-1] > c

list[p]=list[p-1]

p=p-1

endwhile

list[p]=c

next i