Sorting and Searching Algorithms

Question 1

what is a bubble sort?

(Compares)

Answer 1

a simple sorting algorithm that
-Compare the first two items in the list to check if they are in the correct order if not then swap them
-Repeat step 1 for items 2 and 3 in the list
-Continue step 1 until all items in the list are sorted

Question 2

An example of bubble sort Looks like:

Answer 2

1 2 3 4
|4 7 6 3 | 4 and 7 are fine but 6<7
<->
|4 6 7 3 | 6 and 7 swapped but now 3<7so need swap
<->
|4 6 3 7 | 3 and 7 swapped but 6>3 so need to swap
<->
|4 3 6 7 | 3 and 6 swapped but now 4 and3needswap
<->
|3 4 6 7 | Everything is sorted

Question 3

How do you write a bubble sort in psuedocode (OCR)

Answer 3

array nums[5] = (4,3,2,1,0)
swapped = true
WHILE swapped == true
swapped = false
FOR i = 0 to nums.Lenght-2
IF List[i] > List[i+1] THEN
temp = nums[i]
nums[i] = nums[i+1]
nums[i+1] = temp
swapped = true
ENDIF
NEXT i
ENDWHILE

Question 4

What is an Insertion sort?

(All in one go)

Answer 4

It is a simple sorting algorithm that follows the steps of;
-places each item one at a time into the correct position
-First Item in the list is the strating point
-each item in the list is cpmpared toithe one before to determine where it need to be placed

Question 5

An example of a Insertion sort looks like:

Answer 5

0 1 2 3 4 5
___________
7 2 8 3 4 1<-\
2 7 8 3 4 1‎ ‎ ‎ ‎ |
2 3 7 8 4 1‎ ‎ ‎ ‎ |
2 3 4 7 8 1‎ ‎ ‎ ‎ |
1 2 3 4 7 8<-/ sorted fully in one go

Question 6

what is the psuedocode for an Insertions sort?

Answer 6

FOR i = 0 to (LenghtOfList - 1)
‎ ‎ ‎ ‎ var j = i
‎ ‎ ‎ ‎ WHILE j > 0 AND list [j-1] > list[j]
‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ swap(list[j], list[j-1])
‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ j = j-1
‎ ‎ ‎ ‎ ENDWHILE
‎ ‎ ‎ ‎ i = i + 1
ENDFOR

Question 7

What is a linear search?

Answer 7

When searching for an item in an array each value is examined in turn until either value is located or that end of the file/array is reached

Question 8

Whats the problems with a linear search?

Answer 8

it is very inefficient for large arrays meaning it takes a lot of time to find a piece of data

Question 9

What is the Pseudocode for a linear Search?

Answer 9

Position = 0

While Position < LenghtOfList AND array[position]<>searchvalue
{
‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ Position = Position + 1
}
if Position >= LenghtOfList
‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎PRINT (“item not in list”)
ELSE
‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎‎ PRINT(“item is at location”,pointer)

Question 10

What is a binary sort?

Answer 10

know as divide an conquer
it works by repeatedly breaking down a problem into smaller problems
n of items being searched is halved each time making it very efficient

Question 11

What is the pseudocode for a binary search?