Studied by 0 people
How does a binary search work?
A binary search works by comparing the element you want in an ordered list to the midpoint and checking if it’s higher or lower than it. If the element is higher, than the search repeats with the elements higher than the midpoint. The same thing happens if the element is lower, just with the elements lower than the midpoint.
What must be done for a binary search to take place?
For a binary search to be done to a list of data, the data must be ordered (processed). A binary search cannot operate properly without this step as the midpoint of the data will not be able to be found. This condition is known as a prerequisite, and the algorithm will not work correctly without it.
What are the advantages and disadvantages of a binary search?
advantages
More efficient than linear search (if the element being searched for is not the first in the list).
Most suitable for large lists.
disadvantages
Less suitable for lists where the first or last element is being searched for.
Prerequisite must be met or the algorithm will not work correctly.
Harder to implement.
How does a linear search work?
A linear search works by searching through a list in sequential order from start to end to find the element being searched for. It’s known as a sequential sequence for this reason.
What conditions must be met for a linear search to take place
No conditions are in place for a linear search to take place.
What are the advantages and disadvantages of a linear search?
advantages
Most efficient than binary search (when the element being searched for is the first in a list)
Most efficient in small lists
Simple to understand
Easy to implement
disadvantages
Not efficient to use in large lists
Inefficient overall as it starts from the beginning every time.
What is bubble sort?
Bubble sort is a sorting algorithm that consists of swapping data elements until the largest element has bubbled to the right.
How does bubble sort work?
It works by checking if one element is larger than the other and then swapping their positions if it is. This continues until the algorithm can go through the list without making any swaps.
What are the advantages and disadvantages of bubble sort?
advantages
Easy to write code for and to understand.
Does not need extra memory to run (list is already sorted).
disadvantages
Less suitable for long lists since sort speed depends on list length – they can take a long time.
What is merge sort?
Merge sort is a sorting algorithm that consists of splitting your list into sublists before a loop of merging and resorting to sort it.
How does merge sort work?
It works by splitting your list into sublists until every single data item is separate in a sublist with a length of 1 before starting a loop of merging and resorting until the list is sorted.
What are the advantages and disadvantages of merge sort?
advantages
More efficient for larger lists – does not go through the program multiple times.
disadvantages
Slower compared to the other two.
Uses more memory to store the memory of the sublists made during the algorithm.
What is insertion sort?
Insertion sort is a sorting algorithm that consists of an unsorted and sorted part of the list and checking unsorted values from the left and inserting it into the sorted part.
How does insertion sort work?
It works by using two sections of the same list; the unsorted part and the sorted part. The algorithm starts on the left and checks the element and inserts it into the correct position. This repeats until the list is completely sorted. If an element is the first on a list it will automatically be sorted.
What are the advantages and disadvantages of insertion sort?
advantages
Efficient to sort small lists.
disadvantages
Less suitable for long lists – they can take a long time.
Note 
Flashcard (102)