Searching and Sorting Algorithms Flashcards
(12 cards)
What is a linear search algorithm?
An algorithm that looks through each item in a set until the search key is found or every item has been inspected.
What are the advantages and disadvantages of linear search?
+ Only option for unsorted lists
- Inefficient: O(n)
What does the efficiency of a linear search depend on?
- Size of the dataset
- The location of the item to search for
What is a binary search algorithm?
An algorithm that looks at the middle item, if it is less look at the middle item in the lower half, if it is more look at the middle item in the upper half. This is repeated until it is found or low pointer is above the high pointer
What are the advantages and disadvantages of binary search?
+ Very efficient for large databases - O(log n)
- Can be more difficult to implement
- Must be a sorted list
How do you search in a binary search tree?
Using an in-order traversal
How does bubble sort work?
Each item in a list is compared to the one after it. If the item after is smaller that the current one then they swap until no swaps are made and it is sorted.
What are the disadvantages of bubble sort?
- Inefficient time wise as time complexity of O(n2)
- Algorithm continues to iterate over the list even if no further swaps are required
How can bubble sort be improved?
- Reducing the number of comparisons after each pass
- A sorted flag that can stop the sort if no swaps are made
How does merge sort work?
- Example of a divide and conquer algorithm where the program is broken down into smaller units
- List is continuously divided until there is only one item in each
- Sublists are combined in order until the list is fully sorted
What are the disadvantages of merge sort?
If done recursively is not very memory efficient
What are the advantages of merge sort?
Time efficient with an efficiency of O(nlogn)
