Search and sort

IMPORTANT: bubble sort, quick sort is not in your syllabus dont read.

here is the pdf link :

https://pdflink.to/search-sort/

1. Linear Search

It is a searching technique that searches sequentially.
Time Complexity: O(n)

Algorithm: Linear_Search(A, n, key)

Start from the first element of the array.
Compare the key with the current element.
If both are equal, the search is successful.
If not equal, move to the next element.
Repeat this process until the element is found or the array ends.
If the full array is checked and no match is found, the search is unsuccessful.

Example

Array: A = [4, 2, 7, 9, 5]
Key: 9

Compare key with 4 → no
Compare with 2 → no
Compare with 7 → no
Compare with 9 → match found at position 4

2. Binary Search

It is a fast searching algorithm.
Time Complexity: O(log n)
Works only on sorted arrays.

Algorithm

Algorithm: Binary_Search(A, n, key)

Set low = 1 and high = n.
Find mid = (low + high)/2.
Compare the key with A[mid].
If they are equal → search successful.
If key < A[mid], search in the left half (high = mid – 1).
If key > A[mid], search in the right half (low = mid + 1).
Repeat until low > high.
If low > high → search unsuccessful.

Example

Array: A = [3, 6, 9, 12, 15]
Key: 9

low = 1, high = 5 → mid = 3
A[3] = 9 → match found at mid

3. Selection Sort

The list is divided into two parts: sorted + unsorted.
We repeatedly select the minimum from the unsorted part.

Algorithm: Selection_Sort(A, n)

From the unsorted part, find the smallest element.
Swap it with the first element of the unsorted part.
Now the first element becomes part of the sorted list.
Move to the next position and repeat the process.
Continue until all elements are placed in sorted position.

Example

A = [7, 4, 9, 2]

Smallest element is 2 → swap with 7 → [2,4,9,7]
Next smallest in remaining → 4 → already in place
Next smallest → 7 → swap with 9 → [2,4,7,9]

Final sorted array → [2, 4, 7, 9]

5. Insertion Sort

Suitable only for small inputs.
Elements are inserted in the correct position in the sorted part of the list.

Algorithm: Insertion_Sort(A, n)

Consider the first element as sorted.
Take the next element as the key.
Compare the key with elements on the left.
Shift larger elements to the right.
Insert the key into the correct position.
Repeat for all elements.

Example

A = [5, 3, 8, 2]

Key = 3 → insert before 5 → [3,5,8,2]
Key = 8 → stays → [3,5,8,2]
Key = 2 → shift 8,5,3 → insert → [2,3,5,8]

Final sorted array → [2, 3, 5, 8]

6. Merge Sort

Divide and conquer technique.
Time Complexity: O(n log n)

Algorithm: Merge_Sort(A)

Divide the array into two halves.
Continue dividing until each part has one element.
Merge the parts back by comparing and placing elements in sorted order.
Continue merging until the whole list is sorted.

Example

A = [6, 3, 9, 1]

Divide: [6,3] and [9,1]
→ [6] [3] → merge → [3,6]
→ [9] [1] → merge → [1,9]

Final merge → [3,6] + [1,9] → [1,3,6,9]

7. Quick Sort

Partitions array into small and large parts.
Time Complexity: O(n log n)

Partitioning uses:

pivot
left pointer
right pointer

8. Shell Sort

More efficient version of insertion sort.
Uses a "gap" to compare far elements.
Gaps reduce in each pass.

Algorithm

Algorithm: Shell_Sort(A, n)

Choose a gap value (n/2).
Compare elements that are ‘gap’ distance apart.
Swap if needed.
Reduce the gap (gap = gap/2).
For gap = 1, perform insertion sort.
Continue until the array becomes fully sorted.

Example

A = [10, 20, 15, 6, 80, 21, 8]
n = 7 → first gap = 3

Compare positions:
(0 & 3), (1 & 4), (2 & 5), (3 & 6)

After arranging with gap 3 → new arrangement
Next gap = 1 → final insertion-sort-like pass

Final sorted array → [6, 8, 10, 15, 20, 21, 80]