Searching and Sorting I

Question 1

What is a Sequential (Linear) Search ?

Answer 1

Scans each element one by one,
Simple but time inefficient (O(n)),
Useful for unsorted arrays.

Question 2

What is a Binary Search ?

Answer 2

Repeatedly divides the search range in half,
Efficient on sorted arrays (O(log n))
Can be implemented iteratively or recursively.

Question 3

What is an Interpolation Search ?

Answer 3

Uses the estimated position of the search key
Optimised for uniformly distributed data (average case = O (log log n), worst case = O(n))
More precise than binary when data is evenly spaced (e.g. 1,2,3,4)

Question 4

What is a Bubble Sort ?

Answer 4

Repeatedly swaps adjacent elements if they’re out of order,
Very inefficient - (On^2)

Question 5

What is an Insertion Sort ?

Answer 5

Builds sorted arrays one element at a time,
Efficient for small or nearly sorted arrays,
Best = O(n), worst = O(n^2)

Question 6

What is a Merge Sort ?

Answer 6

Recursively splits the array then merges sorted halves,
Very efficient but needs additional space,
Time complexity = O(n log n)
Space Complexity = O(n)

Question 7

What is a QuickSort ?

Answer 7

Selects a pivot, partitions the array and recursively sorts subarrays,
Average = O(n log n)