Algorithms- S12

Question 1

Linear Search

Answer 1

searching the data one by one until the required one is found or the end of the list is reached.

Question 2

Algorithm for Linear Search

Answer 2

Function linerarSearch (alist, itemsought)
index=-1
i=0
found=False
While i< length(alist) found=false
	If alist[i] = itemSought then
		index=i
		found= True
	endIf
	i=i+1
	Endwhile
	Return index 
end function

Question 3

Binary Search

Answer 3

items in a list must be sorted. Each time half of the list is discarded and this continues until there is only one item left. This is efficient when there is a large amount of numbers.

Question 4

Algorithm for Binary Search

Answer 4

Function BinarySearch (alist, itemsought)
	Found = False
	index= -1
	First=0
	last = len(aList)-1
	While first <= last  and found= False
		midpoint= ((first+last)/2)
		If aList[midpoint]= itemSought then
			found=true
			Index= midpoint
		Else
			If aList [midpoint] < itemSought then
first=midpoint+1
		Else 
				last= midpoint -1
			Endif
		Endif
Endwhile
End function

Question 5

Bubble sorting

Answer 5

go through the array comparing each item with the one next to it. If it’s greater/smaller than swap. The last element will be in the correct place after the first pass. `

Question 6

Bubble sort algoithm

Answer 6

numbers= [9,5,4,15,3,8,11]
numItems= len(number)
For i=0 to numItems - 2
	For J=0 to(numItems-i-2)
		If number [ j ] > number [j+1]
			temp= numbers [ j ]
			Numbers[ j ] =numbers[ j+1]
			Numbers[ j +1] = temp
		Endif
	Next j	
	Print (numbers)
Next i

Question 7

Insertion sort

Answer 7

sorts one data item at a time. A data item is taken from the list and placed in the correct position. This repeats until all data items are sorted.

Question 8

Insertion sort algorithm

Answer 8

Procedure insertionSort (alist)
	n=len(alist)
	For index= 1 to n-1
		Currentvalue=alist[ index]
		Position = index
		While position >0 and alist[position-1]> currentvalue 
Alist [position]= alist[position-1]
position=position-1
Endwhile
alist[position]=currentvalue
Next index
Endprocedure

Question 9

Why can insertion sort be considered more efficient

Answer 9

Has less checks