19.1 Algorithms

# Linear search
```Pseudocode
DECLARE myList : ARRAY[0:9] OF INTEGER
DECLARE upperBound : INTEGER
DECLARE lowerBound : INTEGER
DECLARE index : INTEGER
DECLARE item : INTEGER
DECLARE found : BOOLEAN
upperBound ← 9
lowerBound ← 0
OUTPUT "Please enter item to be found"
INPUT item
found ← FALSE
index ← lowerBound
REPEAT
	IF item = myList[index]
	  THEN
	    found ← TRUE
	ENDIF
	index ← index + 1
UNTIL (found = TRUE) OR (index > upperBound)
```

```Python
#Python program for Linear Search
#create array to store all the numbers
myList = [4, 2, 8, 17, 9, 3, 7, 12, 34, 21]
#enter item to search for
item = int(input("Please enter item to be found "))
found = False
for index in range(len(myList)):
	if(myList[index] == item):
		found = True
if(found):
	print("Item found")
else:
	print("Item not found")
```
# Binary search

```
DECLARE myList : ARRAY[0:9] OF INTEGER
DECLARE upperBound : INTEGER
DECLARE lowerBound : INTEGER
DECLARE index : INTEGER
DECLARE item : INTEGER
DECLARE found : BOOLEAN
upperBound ← 9
lowerBound ← 0
OUTPUT "Please enter item to be found"
INPUT item
found ← FALSE
REPEAT
	index ← INT ( (upperBound + lowerBound) / 2 )
	IF item = myList[index]
	  THEN
		found ← TRUE
	ENDIF
	IF item > myList[index]
	  THEN
		lowerBound ← index + 1
	ENDIF
	IF item < myList[index]
	  THEN
		upperBound ← index - 1
	ENDIF
UNTIL (found = TRUE) OR (lowerBound = upperBound)
IF found
  THEN
	OUTPUT "Item found"
  ELSE
	OUTPUT "Item not found"
ENDIF
```
# Bubble sort
```
DECLARE myList : ARRAY[0:8] OF INTEGER
DECLARE upperBound : INTEGER
DECLARE lowerBound : INTEGER
DECLARE index : INTEGER
DECLARE swap : BOOLEAN
DECLARE temp : INTEGER
DECLARE top : INTEGER

upperBound ← 8
lowerBound ← 0
top ← upperBound

REPEAT
	FOR index ← lowerBound TO top - 1
		Swap ← FALSE
		IF myList[index] > myList[index + 1]
		  THEN
			temp ← myList[index]
			myList[index] ← myList[index + 1]
			myList[index + 1] ← temp
			swap ← TRUE
		ENDIF
	NEXT index
top ← top -1
UNTIL (NOT swap) OR (top = 0)
```

##### two factors that may affect the performance of a sorting algorithm.
- The initial order of the data
- The number of data items to be sorted
- The efficiency of the sorting algorithm
##### the necessary condition for a binary search
- The list to be searched must be ordered/sorted
##### how to perform a binary search
- Find the middle item / index
- Check the value of middle item in the list to be searched
- If equal item searched for is found
- If this is not equal/greater/less than the item searched for
- … discard the half of the list that does not contain the search item
- Repeat the above steps until the item searched for is found
- … or there is only one item left in the list and it is not the item searched for // lower bound > / = upper bound
##### how the performance of a binary search varies according to the number of values in the array
- As the number of items in the list increases the time to search the list increases
##### Compare the performance of the algorithms for a binary search and a linear search using Big O notation for order of time complexity
- Linear search O(n) and Binary search O(log<sub>2</sub><sup>n</sup>) / O(Log n)
- time to search increases linearly in relation to the number of items in the list for a linear search and logarithmically for a Binary search
- time to search increases less rapidly for a binary search and time to search increases more rapidly for a linear search
##### Big O notation for time complexity of a linear search
- O(n) 
##### Describe the meaning of O(log n) as it applies to a binary search algorit
- O(log n) is a time complexity that uses logarithmic time.
- The time taken goes up linearly as the number of items rises exponentially
- O(log n) is the worst case scenario (time complexity for a binary search)   
##### how you could improve the simplified linked list structure.
-  Include a free list pointer
-  …to reuse the unused space
-  …as a linked list of free space.   
##### how a new element can be added to the queue if it is implemented using two stacks
- (Two stacks are required) so that the second stack can reverse the order of the first stack.
- Stack 1 operates as the queue with the newest elements at the bottom. Stack 2 is empty.
- To add an element, pop all the elements from stack 1 and push onto stack 2.
- Push the new element onto either stack.
- Pop all the elements of stack 2 back onto stack 1.