Searching and sorting are fundamental concepts in computer science. Searching is the process of finding a specific element in a data structure, while sorting is the process of arranging elements in a specific order (ascending or descending).

This note covers sorting algorithms like Bubble Sort, Selection Sort, Insertion Sort and Linear Search .

Searching Algorithms

1. Linear Search

Concept

• Linear search traverses the list from start to end.
• Compares each element with the target key.
• Returns True if the key is found, False otherwise.

Code

def linear_search(lists, key):
    # Step 1: Traverse each element in the list
    for x in lists:
        # Step 2: Check if current element matches the key
        if x == key:
            return True
    # Step 3: If key is not found after traversal
    return False

Explanation

1. Start from the first element.
2. Compare each element with the key.
3. If a match is found, return True.
4. If end of list is reached without a match, return False.

Time Complexity: O(n) Space Complexity: O(1)

2. Binary Search

We will cover this in recursion and backtracking section.

Sorting Algorithms

1. Bubble Sort

Concept

• Bubble sort repeatedly swaps adjacent elements if they are in the wrong order.
• After each pass, the largest unsorted element moves to its correct position.
• Simple but not efficient for large lists.

Code

def bubble_sort(lists):
    # Step 1: Traverse the list multiple times
    for x in range(len(lists) - 1):
        # Step 2: Traverse the unsorted part of the list
        for y in range(0, len(lists) - x - 1):
            # Step 3: Swap if the current element is greater than next
            if lists[y] > lists[y+1]:
                temp = lists[y]
                lists[y] = lists[y+1]
                lists[y+1] = temp

Explanation

1. Outer loop controls the number of passes.
2. Inner loop compares adjacent elements.
3. Swap elements if they are in the wrong order.
4. Repeat until the list is sorted.

Time Complexity: O(n^2) Space Complexity: O(1)

2. Selection Sort

Concept

• In each iteration, find the minimum element from the unsorted part and swap it with the first unsorted element.

Code

def selection_sort(lists):
    # Step 1: Traverse through all list elements
    for i in range(len(lists)):
        # Step 2: Assume the minimum is the first element of unsorted part
        min_index = i
        # Step 3: Find the minimum element in remaining unsorted array
        for j in range(i+1, len(lists)):
            if lists[j] < lists[min_index]:
                min_index = j
        # Step 4: Swap the found minimum element with the first element
        temp = lists[i]
        lists[i] = lists[min_index]
        lists[min_index] = temp

3. Insertion Sort

Concept

• Initially take the first element as sorted and other elements as unsorted.
• Pick elements from unsorted part and insert them into the correct position in the sorted part.

Code

def insertion_sort(lists):
    # Step 1: Traverse from 1 to len(lists)
    for i in range(1, len(lists)):
        key = lists[i]
        j = i - 1
        # Step 2: Move elements of lists[0..i-1], that are greater than key,
        # to one position ahead of their current position
        while j >= 0 and key < lists[j]:
            lists[j + 1] = lists[j]
            j -= 1
        lists[j + 1] = key

4.Merge Sort

We will cover this in recursion and backtracking section.

5.Quick Sort

We will cover this in recursion and backtracking section.

Summary