2.1 - sorting

Question 1

2 methods of searching

Answer 1

Binary search
Linear search

Question 2

3 types of sorting

Answer 2

Bubble
Merge
Insertion

Question 3

How does binary search work

Answer 3

1. Set counter to middle of list
2. If value is a match, end search
3. If the value at midpoint is smaller than the search value, the lower half is ignored and search continues in upper half
4. If the value at midpoint is greater than the search value, top half of numbers is ignored and search continues in lower half
5. Search continues to midpoint of remaining values and 2-4 are related

Question 4

What does the binary search code look like

Answer 4

Searchitem = 11
list = [“2”, “3”, “4”, “6”, “8”]
Last = length(list)-1
First = 0

While first <= last and found = false:
Midpoint = (first + last)/2

      If list[midpoint] == searchitem:
                Found = true
     
      Else:
                If searchitem < list[midpoint]:
                           Last = midpoint - 1
                Else:
                            First = midpoint + 1

Question 5

How does linear search work

Answer 5

1. Find length of data set
2. Set counter to 0
3. Examine value at counter position
4. If found, end search
5. If not found, add 1 to counter

Question 6

Code for linear search

Answer 6

Searchitem = 2
Counter = 0
Found = false

While counter < list and found = false:
If counter == searchitem:
Found = true
Else:
Counter = counter + 1

Question 7

Disadvantages of linear search

Answer 7

Can take a while as it goes through every value

Question 8

Advantage of linear search

Answer 8

Works on any data set wether in order or not

Question 9

How does a bubble sort work

Answer 9

1. Start at beginning of list
2. Compare the first value in the list with the next one up. If the first value is bigger, swap the positions of the two values
3. Move to the second value in the list. Again, compare this value with the next and swap if the value is bigger.
4. Keep going until there are no more items to compare.
5. Go back to the start of the list

Question 10

Code for bubble sort

Answer 10

counter = 0
swapped = True
swaps = 0
length = list.length

while swapped == True:

 while counter < length-1:
      if list[counter] > list[counter+1]:
            temp = list[counter]
            list[counter] = list[counter+1]
            list[counter+1] = temp
            swaps = swaps + 1
      counter = counter + 1

if swaps == 0 then
     swapped = False
else:
     swaps = 0
     counter = 0

Question 11

How does insertion sort work

Answer 11

An insertion sort compares values in turn, starting with the second value in the list. If this value is greater than the value to the left of it, no changes are made. Otherwise this value is repeatedly moved left until it meets a value that is less than it. The sort process then starts again with the next value. This continues until the end of the list is reached.

Question 12

Code for insertion sort

Answer 12

For i from 0 to length(list)-1:
Key = list[i]
j = i - 1
while j > -1 and key < list[j]
list[j+1] = list[j]
j = j + 1
list[j + 1]= key
Next i

Question 13

What is a flow diagram?

Answer 13

A flow diagram is a diagram that shows an overview of a program. Flow diagrams normally use standard symbols to represent the different types of instruction. These symbols are used to construct the flowchart and show the step-by-step solution to the problem. Flow diagrams are sometimes known as flowcharts.

Question 14

Advantages of flow diagrams

Answer 14

• easy to see how program flows
• follow an international standard

Question 15

Disadvantages of using flow diagrams

Answer 15

• can be large in size and confusing to follow
• any changes mean large portion of diagram has to be redrawn

Question 16

Pros of merge sort

Answer 16

Quickest
Most efficient

Question 17

Cons of merge sort

Answer 17

Difficult to understand

Question 18

Pros of bubble sort

Answer 18

Simple to understand

Question 19

Cons of bubble sort

Answer 19

Slow, inefficient, lots of steps

Question 20

Pros of insertion sort

Answer 20

Fast, good for small data sets

Question 21

Cons of insertion sort

Answer 21

Remembering pivot point/ key