2.1 - sorting Flashcards
2 methods of searching
Binary search
Linear search
3 types of sorting
Bubble
Merge
Insertion
How does binary search work
- Set counter to middle of list
- If value is a match, end search
- If the value at midpoint is smaller than the search value, the lower half is ignored and search continues in upper half
- If the value at midpoint is greater than the search value, top half of numbers is ignored and search continues in lower half
- Search continues to midpoint of remaining values and 2-4 are related
What does the binary search code look like
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
How does linear search work
- Find length of data set
- Set counter to 0
- Examine value at counter position
- If found, end search
- If not found, add 1 to counter
Code for linear search
Searchitem = 2
Counter = 0
Found = false
While counter < list and found = false:
If counter == searchitem:
Found = true
Else:
Counter = counter + 1
Disadvantages of linear search
Can take a while as it goes through every value
Advantage of linear search
Works on any data set wether in order or not
How does a bubble sort work
- Start at beginning of list
- 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
- Move to the second value in the list. Again, compare this value with the next and swap if the value is bigger.
- Keep going until there are no more items to compare.
- Go back to the start of the list
Code for bubble sort
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
How does insertion sort work
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.
Code for insertion sort
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
What is a flow diagram?
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.
Advantages of flow diagrams
- easy to see how program flows
- follow an international standard
Disadvantages of using flow diagrams
- can be large in size and confusing to follow
- any changes mean large portion of diagram has to be redrawn
