Paper 2: Sorting and Searching Algorithms Flashcards
What is sorting?
Putting words or numbers into order, either alphabetical or numerical.
What is searching?
Finding a particular value in a list of data.
What does shifting mean in data management?
Moving data to the right or left in a list.
What is exchanging in data management?
Moving data from one memory location to another using a temporary variable.
What is a temporary variable?
A temporary store of data used when exchanging data to ensure a value is not overwritten.
What is a linear/sequential search?
Starts at the first item and works through the list until the item is found or the end is reached.
What are the advantages of linear search?
- Can work on any list sorted or unsorted
- Easy to program
- Efficient for small lists if the value is near the start.
What are the disadvantages of linear search?
Not efficient for larger lists of data.
How does a binary search work?
Finds the midpoint of the list and checks that value, splitting the list until the item is found or not.
What is a requirement for binary search to work?
Only works on an ordered list.
What are the advantages of binary search?
- More efficient than linear for larger lists
- Faster search time.
What are the disadvantages of binary search?
Harder to program than linear search.
What is bubble sort?
Starts at Item 1, checks the first two items, swaps if needed, and repeats until no swaps are made.
What are the advantages of bubble sort?
- Easy to program
- Does not use a great deal of memory to run.
What are the disadvantages of bubble sort?
Not very efficient and can take a long time for larger lists.
What is insertion sort?
Starts at item 2, compares it with previous items, and places it in the correct position.
What are the advantages of insertion sort?
- Efficient use of memory and time
- More efficient and faster than bubble sort.
What are the disadvantages of insertion sort?
Slower than merge sort for larger lists.
What is merge sort?
Splits the list until items are in individual lists, then merges them back together in order.
What are the advantages of merge sort?
Very efficient for sorting large lists.
What are the disadvantages of merge sort?
Very memory intensive as it creates many lists.
True or False: Linear search can only be performed on sorted lists.
False.
True or False: Insertion sort is less efficient than bubble sort for larger lists.
False.
Fill in the blank: Merge sort is __________ for sorting large lists.
very efficient.