Searching And Sorting Algorithms Flashcards
Can linear search be used in ordered or unordered
Both
How does linear search work
Every number in the list is checked in the order of the list until the number is found
Is linear search slow or fast
Linear search is slow unless you get lucky however in a computer algorithm there tends to be lots of numbers so it would be long
Does binary search work on unordered or ordered lists
Ordered lists
How does binary search work
You find the midpoint by adding the smallest and largest position in the list and divide by 2 if it’s a decimal you round up. If the midpoint is the number you are looking for the search ends. If not then you see if the midpoint is less than or more than and then which ever it is you eliminate the opposite for example if greater than you remove the smaller numbers. Next you repeat this process until your number is found
Is binary search fast or slow
It is fast when using long lists
Disadvantages of binary search
It is very slow on short lists
The list has to be ordered
Does bubble sort work on ordered or unordered list
Unordered
Show how bubble sort works
- 1
- 4
- 5
- 6
- 8
Does bubble sort work on short or long lists
Short
Advantages of bubble sort
Simple to understand
Effective for very small data sets or almost-sorted lists
How does merges sort work (e.g. with an 8 number list)
First divide all the numbers in the list until there is 8 sub lists.
Next merge the sub lists into 4 sub lists and order the numbers
Next merge into 2 sub lists and order them
Finally merge into one list and order them
Advantages of merge sort
Efficient for large datasets
Insertion sort
(6 0) 4 8 1 5
0 (6 4) 8 1 5
0 4 (6 8) 1 5
0 4 6 (8 1) 5
0 4 6 1 (8 5)
(0 4) 6 1 5 8
0 (4 6) 1 5 8
0 4 (6 1) 5 8
0 4 1 (6 5) 8
0 4 1 5 (6 8)
(0 4) 1 5 6 8
Disadvantage of merge sort
Uses more memory as more space is needed to merge the lists
Advantages of insertion sort
simple to use
Fast for short lists
Needs very little memory
Disadvantages of insertion sort
Slow on long lists
