Searching and Sorting Algorithms

Searching and Sorting Algorithms

Searching Algorithms

1. Linear Search

   • Description: Checks each element in a list sequentially until the desired element is found or the list ends.
   • Time Complexity: O(n)
   • Use Case: Suitable for small or unsorted lists.
   • Example Code:
     python

     Copy code

     def linear_search(arr, target):
     for i in range(len(arr)):
     if arr[i] == target:
     return i
     return -1

     arr = [10, 23, 45, 70, 11, 15]
target = 70
print(linear_search(arr, target)) # Output: 3


2. Binary Search

   • Description: Efficiently searches a sorted list by repeatedly dividing the search area in half.
   • Time Complexity: O(log n)
   • Use Case: Suitable for large, sorted lists.
   • Example Code:
     python

     Copy code

     def binary_search(arr, target):
     left, right = 0, len(arr) - 1
     while left <= right:
     mid = (left + right) // 2
     if arr[mid] == target:
     return mid
     elif arr[mid] < target:
     left = mid + 1
     else:
     right = mid - 1
     return -1

     arr = [2, 3, 4, 7, 9]
print(binary_search(arr, 7)) # Output: 3


Sorting Algorithms

1. Bubble Sort

   • Description: Compares adjacent elements and swaps them if they are in the wrong order.
   • Time Complexity: O(n²)
   • Space Complexity: O(1)
   • Use Case: Educational purposes or small datasets.
   • Example Code:
     python

     Copy code

     def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr) # Output: [11, 12, 22, 25, 34, 64, 90]


2. Insertion Sort

   • Description: Builds the sorted array one item at a time by inserting elements into their correct position.
   • Time Complexity: O(n²)
   • Space Complexity: O(1)
   • Use Case: Efficient for small or nearly sorted datasets.
   • Example Code:
     python

     Copy code

     def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array is:", arr) # Output: [5, 6, 11, 12, 13]


3. Merge Sort

   • Description: Divides the list into smaller sublists, sorts them, and merges them back together.
   • Time Complexity: O(n log n)
   • Space Complexity: O(n)
   • Use Case: Suitable for large datasets.
   • Example Code:
     python

     Copy code

     def merge_sort(arr):
     if len(arr) <= 1:
     return arr
     mid = len(arr) // 2
     left = merge_sort(arr[:mid])
     right = merge_sort(arr[mid:])
     return merge(left, right)

     def merge(left, right):
     result = []
     i = j = 0
     while i < len(left) and j < len(right):
     if left[i] < right[j]:
     result.append(left[i])
     i += 1
     else:
     result.append(right[j])
     j += 1
     result.extend(left[i:])
     result.extend(right[j:])
     return result

     arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array is:", sorted_arr) # Output: [3, 9, 10, 27, 38, 43, 82]


4. Quick Sort

   • Description: Selects a pivot element and partitions the array around it, sorting the partitions recursively.
   • Time Complexity: O(n log n)
   • Space Complexity: O(log n) (in-place version)
   • Use Case: Efficient for large datasets.
   • Example Code:
     python

     Copy code

     def quick_sort(arr):
     if len(arr) <= 1:
     return arr
     pivot = arr[len(arr) // 2]
     left = [x for x in arr if x < pivot]
     middle = [x for x in arr if x == pivot]
     right = [x for x in arr if x > pivot]
     return quick_sort(left) + middle + quick_sort(right)

     arr = [33, 14, 27, 35, 10, 19, 42, 44]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr) # Output: [10, 14, 19, 27, 33, 35, 42, 44]


Activity Questions

1. Implement Sorting Algorithms:

   • Code for all sorting algorithms is provided above.

2. Compare Time and Space Complexity:

   • Bubble Sort:
     • Time: O(n²)
     • Space: O(1)
   • Insertion Sort:
     • Time: O(n²) (worst case), O(n) (best case for sorted arrays)
     • Space: O(1)
   • Merge Sort:
     • Time: O(n log n)
     • Space: O(n)
   • Quick Sort:
     • Time: O(n log n)
     • Space: O(log n)

3. Best Performance for Sorted Arrays:

   • Insertion Sort performs best with an already sorted array, achieving a time complexity of O(n), as it only requires linear scans without swaps.