YEAR 1 CO2 WEEK 12 SEARCH/SORTING ALGORITHMS.

Question 1

Describe a Linear Search.

Answer 1

If data is unsorted linear search has to be used.
Each value is examined in turn until either the value located or end of file is reached.
Very inefficient except on very small number of items.

Question 2

Describe a Binary Search.

Answer 2

If data is sorted binary search can be used.
Array divided into three parts:
LB
UB : Pointers created for each point
MP

MP is examined. If equal to search value algorithm ends.
If not equal to search value see if it is greater than search value. If MP greater than the SV Upper part of array discarded, UB becomes MP-1 and MP recalculated.
Else if MP less than SV lower part of array discarded. LB becomes MP+1 and MP recalculated.

Question 3

Describe Bubble Sort.

Answer 3

Starts from an end of list/array and compared first item to next item.
If smaller item comes before larger it is left alone.
Else they are swapped.
Continues comparing pairs of elements and repeates from beginning if list not sorted.

Question 4

Describe Insertion Sort.

Answer 4

Works by dividing list into two parts sorted + unsorted.
One item at a time moves into correct position in the sorted list until all items in list sorted.