search and sort Flashcards
What is sequential (linear) search?
A method that checks each element in a list one-by-one.
What is the time complexity of sequential search?
O(n)
What is binary search?
A method that divides a sorted array in half repeatedly to find a target.
When can binary search be used?
Only on sorted arrays or ArrayLists.
What is the time complexity of binary search?
O(log n)
How does binary search work?
Check middle
What happens if target not found in binary search?
Eventually returns -1 or a “not found” flag.
What is insertion sort?
A sorting method that builds a sorted list one item at a time.
What is the time complexity of insertion sort?
O(n^2) worst case
What is selection sort?
A sorting method that repeatedly selects the smallest element.
How does selection sort work?
Find smallest
What is the time complexity of selection sort?
O(n^2) in all cases
What is merge sort?
A divide-and-conquer algorithm that splits
What is the time complexity of merge sort?
O(n log n)
How does merge sort work?
Divide list
What is the benefit of merge sort over selection/insertion?
It’s faster for large datasets (O(n log n) vs. O(n^2)).
Is merge sort recursive?
Yes
Which sort is best for nearly-sorted data?
Insertion sort.
Which sort is the easiest to implement?
Selection sort — it’s conceptually simple.
Which sort requires extra memory?
Merge sort — due to the temporary arrays used in merging.
What’s a stable sort?
A sort that maintains relative order of equal elements.
Is selection sort stable?
No.
Is insertion sort stable?
Yes.
Is merge sort stable?
Yes.
