Searching and Sorting Algorithms - Notes with Python Programs
1. Linear Search
Definition:
Linear search checks each element in the list one by one to find the target.
Algorithm Steps:
1. Start from index 0.
2. Compare each element with the target.
3. If match found, return index.
4. If end of list is reached, return -1 (not found).
Example:
List: [4, 7, 1, 9, 3]
Target: 9 Found at index 3
def linear_search(arr, key):
for i in range(len(arr)):
if arr[i] == key:
return i
return -1
arr = list(map(int, input("Enter numbers separated by space: ").split()))
key = int(input("Enter number to search: "))
result = linear_search(arr, key)
print("Element found at index:" if result != -1 else "Element not found", result)
2. Binary Search
Definition:
Binary search finds an element in a sorted list by repeatedly dividing the list in half.
Algorithm Steps:
1. Set low = 0, high = len(arr) - 1.
2. While low <= high:
- Find mid = (low + high) // 2
- If arr[mid] == key, return mid
- If key < arr[mid], search left half
- If key > arr[mid], search right half
Searching and Sorting Algorithms - Notes with Python Programs
3. If not found, return -1
Example:
List: [1, 3, 5, 7, 9, 11, 13]
Target: 9 Found at index 4
def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1
arr = sorted(list(map(int, input("Enter sorted numbers separated by space: ").split())))
key = int(input("Enter number to search: "))
result = binary_search(arr, key)
print("Element found at index:" if result != -1 else "Element not found", result)
3. Quick Sort
Definition:
Quick Sort sorts elements using a pivot, dividing the list into smaller and larger values.
Algorithm Steps:
1. Choose a pivot (e.g., last element).
2. Partition into elements < pivot and pivot.
3. Recursively sort both partitions.
4. Combine results.
Example:
List: [8, 3, 1, 7, 2]
Sorted: [1, 2, 3, 7, 8]
def quick_sort(arr):
Searching and Sorting Algorithms - Notes with Python Programs
if len(arr) <= 1:
return arr
pivot = arr[-1]
left = [x for x in arr[:-1] if x < pivot]
right = [x for x in arr[:-1] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
arr = list(map(int, input("Enter numbers separated by space: ").split()))
sorted_arr = quick_sort(arr)
print("Sorted List:", sorted_arr)
4. Insertion Sort
Definition:
Insertion Sort builds the sorted list by inserting each element into the correct position.
Algorithm Steps:
1. Start from second element.
2. Store the element in key.
3. Compare with previous elements and shift them.
4. Insert key in correct position.
5. Repeat for all elements.
Example:
List: [5, 2, 4, 6]
Sorted: [2, 4, 5, 6]
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = list(map(int, input("Enter numbers separated by space: ").split()))
insertion_sort(arr)
print("Sorted List:", arr)
