Algorithm for Sorting and Searching
a) Bubble Sort Algorithm with Values
1. Input: arr = [20, 24, 13, 12, 44, 54, 12, 17, 77, 76, 8, 7, 5], n = 13.
2. Process:
- Outer loop (i = 0 to n-2 = 11):
- Inner loop (for each value of i):
- Compare adjacent elements.
- If the left element is greater than the right element, swap them.
- Example Iterations:
- First Pass (i = 0):
- Compare 20 and 24 (no swap needed).
- Compare 24 and 13 (swap), new array: [20, 13, 24, 12, 44, 54, 12, 17,
77, 76, 8, 7, 5].
- Continue similarly until the end of the pass.
- Repeat for each pass until fully sorted.
- Final sorted array: [5, 7, 8, 12, 12, 13, 17, 20, 24, 44, 54, 76, 77].
3. Output: Sorted array is [5, 7, 8, 12, 12, 13, 17, 20, 24, 44, 54, 76, 77].
b) Binary Search Algorithm with Values
1. Input: Sorted array arr = [5, 7, 8, 12, 12, 13, 17, 20, 24, 44, 54, 76, 77], target = 120, n = 13.
2. Process:
- Initialize left = 0, right = 12 (last index).
- Loop (while left <= right):
- Calculate mid = left + (right - left) / 2.
- Example Iterations:
- First Iteration:
- mid = 6, arr[mid] = 17.
- Since 17 < 120, set left = mid + 1 = 7.
- Second Iteration:
- mid = 9, arr[mid] = 44.
- Since 44 < 120, set left = mid + 1 = 10.
- Continue similarly until left > right.
- Since the loop completes without finding 120, return -1.
3. Output: -1 (indicating 120 is not found in the array).