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?

Question 12

What is a merge sort?

Answer 12

It was developed to handle sorting large lists
it does this via breaking the initial list down into smaller lists sorts them and then puts them back together

Question 13

Write an example of a merge sort

Answer 13

2,45,6,9,15,12,7,8
|2|45|6|9| —– |15|12|7|8|
|2|45|–|6|9| |15|12|–|7|8|
2 45 6 9 15 12 7 8
|2|45|–|6|9| |12|15|–|7|8|
|2|6|9|45| —- |7|8|12|15|
|2|6|7|8|9|12|15|45|