Sorting and Searching

To sort a list containing N elements, bubble sort requires (N − 1) passes. During each pass, the number of elements to be compared reduces by one, since the largest remaining element always moves to its correct position at the end.

Algorithm for Bubble Sort (ascending order)

1. Step 1: Start.
2. Step 2: Accept a value in N as the number of elements of the list.
3. Step 3: Accept N elements into the list named LIST.
4. Step 4: Repeat Steps 5 to 7, (N − 1) times.
5. Step 5: Repeat Step 6 until the second last element of the current list.
6. Step 6: Starting from the first position, compare two adjacent elements in the list. If they are not in the proper order, swap the elements.
7. Step 7: Revise the list by excluding the last element in the current list.
8. Step 8: Print the sorted list, LIST.
9. Step 9: Stop.

To improve clarity and maintainability, Python encourages dividing large code blocks into smaller, well-defined functions. Following this approach, the bubble sort steps (5 to 7) are separated into a dedicated bubble_sort() function.

# Traverse through all elements in the list
def bubble_sort(LIST, n):
    for i in range(n - 1):
        # Last i elements are already in place
        for j in range(0, n - i - 1):
            # Swap if element found is greater than next element
            if LIST[j] > LIST[j + 1]:
                LIST[j], LIST[j + 1] = LIST[j + 1], LIST[j]
    return LIST

# Accept number of elements
count = int(input("Enter how many numbers: "))
# Create an empty list
ITEMS = []
# Accept n numbers from the user
for i in range(count):
    num = int(input(f"Enter number {i+1}: "))
    ITEMS.append(num)
# Display the list
print("Original list:", ITEMS)
# Display the sorted list
print("Sorted list:", bubble_sort(ITEMS, count))

Enter how many numbers: 5
Enter number 1: 56
Enter number 2: 34
Enter number 3: 98
Enter number 4: 12
Enter number 5: 39
Original list: [56, 34, 98, 12, 39]
Sorted list: [12, 34, 39, 56, 98]

A pass is completed once the smallest element in the unsorted section is located and exchanged with the element at the current position. For N elements there will be N − 1 passes. Though each pass is intended for an exchange, no exchange is made if the smallest value is already in the correct location — as seen in Pass 3 above.

Algorithm for Selection Sort

1. Step 1: Start.
2. Step 2: Accept a value in N as the number of elements of the list.
3. Step 3: Accept N elements into the list named LIST.
4. Step 4: Repeat Steps 5 to 9, (N − 1) times.
5. Step 5: Assume the first element in the list as the smallest and store it in MIN and its position in POS.
6. Step 6: Repeat Step 7 until the last element of the list.
7. Step 7: Compare the next element in the list with the value of MIN. If it is found smaller, store it in MIN and its position in POS.
8. Step 8: If the first element in the unsorted list and the value in MIN are not the same, then swap the first element with the element at position POS.
9. Step 9: Revise the list by excluding the first element in the current list.
10. Step 10: Print the sorted LIST.
11. Step 11: Stop.

As with bubble sort, the repeated operations of identifying the smallest element and swapping it (steps 5 to 9) are grouped into a separate selection_sort() function.

# Traverse through all elements in the list
def selection_sort(LIST, n):
    for i in range(n - 1):
        # Assume first element is the minimum
        min_index = i
        # Find index of smallest element in the remaining list
        for j in range(i + 1, n):
            if LIST[j] < LIST[min_index]:
                min_index = j
        # Swap min element with the first element of unsorted part
        LIST[i], LIST[min_index] = LIST[min_index], LIST[i]
    return LIST

# Accept number of elements
count = int(input("Enter how many numbers: "))
# Create an empty list
ITEMS = []
# Accept n numbers from the user
for i in range(count):
    num = int(input(f"Enter number {i+1}: "))
    ITEMS.append(num)
# Display the list
print("Original list:", ITEMS)
# Display the sorted list
print("Sorted list:", selection_sort(ITEMS, count))

Enter how many numbers: 5
Enter number 1: 78
Enter number 2: 45
Enter number 3: 97
Enter number 4: 34
Enter number 5: 67
Original list: [78, 45, 97, 34, 67]
Sorted list: [34, 45, 67, 78, 97]

(a) sort() Function

The built-in function sort() arranges the elements of a list in place — it changes the original list instead of creating a new one, and works only with lists. By default it sorts in ascending order; pass reverse=True for descending order.

Apart from numbers, sort() can be used on lists of strings, or any data type that supports comparison. By default, strings are sorted alphabetically. The key parameter specifies a function that determines the sorting criteria — for example, sorting by word length with key=len.

(b) sorted() Function

This built-in function returns a new sorted list from the elements of literal collections such as list, tuple or string — it does not modify the original collection. Like sort(), it also accepts reverse=True and key=len.

Even though Python provides sort() and sorted() for quick and efficient sorting, it is important to study the algorithms behind these operations. Learning bubble sort and selection sort helps you understand how data is processed, how efficiency is measured, and why certain methods perform better in specific situations.

Algorithm for Binary Search

1. Step 1: Start.
2. Step 2: Accept a value in N as the number of elements of the list.
3. Step 3: Accept N elements into the list named LIST in sorted order.
4. Step 4: Accept the value to be searched in the variable ITEM.
5. Step 5: Set search location, LOC = -1.
6. Step 6: Store the position of the first element of the list in FIRST and position of the last element in LAST.
7. Step 7: Repeat Steps 8 to 12 while (FIRST <= LAST).
8. Step 8: Find the middle position using (FIRST + LAST)/2 and store it in MIDDLE.
9. Step 9: Compare the search value in ITEM with the element at MIDDLE of the list.
10. Step 10: If the MIDDLE element contains the search value, stop, display the position and go to Step 13.
11. Step 11: If the search value is larger than the MIDDLE element, set FIRST = MIDDLE + 1.
12. Step 12: If the search value is smaller than the MIDDLE element, set LAST = MIDDLE - 1.
13. Step 13: If the value at LOC is less than 0, display "Not Found"; else display LOC + 1 as the position of the search value.
14. Step 14: Stop.

As with the sorting algorithms, the repeated operations of locating the required element or narrowing the list to half its size are grouped into a separate binary_search() function.

# Initialize variables
def binary_search(LIST, item, n):
    low = 0
    high = n - 1
    LOC = -1
    LIST.sort()
    # Perform binary search
    while low <= high:
        mid = (low + high) // 2
        if LIST[mid] == item:
            LOC = mid + 1   # Record position
            break
        elif item > LIST[mid]:
            low = mid + 1   # Search right half
        else:
            high = mid - 1  # Search left half
    # Display the location
    if LOC == -1:
        return None
    else:
        return LOC

# Accept number of elements
count = int(input("Enter how many numbers: "))
ITEMS = []
for i in range(count):
    num = float(input(f"Enter number {i+1}: "))
    ITEMS.append(num)
print("Number list:", ITEMS)
# Accept item to search
search_item = float(input("Enter the element to search: "))
pos = binary_search(ITEMS, search_item, count)
if pos is None:
    print("Element not found")
else:
    print("Element found at position ", pos)

Enter how many numbers: 5
Enter number 1: 23
Enter number 2: 34
Enter number 3: 43
Enter number 4: 46
Enter number 5: 49
Number list: [23.0, 34.0, 43.0, 46.0, 49.0]
Enter the element to search: 46
Element found at position  4

Recursive Binary Search

Binary search is a good example of a problem that repeats in smaller, similar patterns — making it a natural fit for recursion. The algorithm examines the middle element; if the search value is smaller, it recursively searches the first half, and if larger, it recursively searches the second half.

def bsearch_recursive(arr, low, high, item):
    if low > high:
        return -1                       # Element not found
    mid = (low + high) // 2
    if arr[mid] == item:
        return mid + 1                  # Return position
    elif item > arr[mid]:
        return bsearch_recursive(arr, mid + 1, high, item)   # Right half
    else:
        return bsearch_recursive(arr, low, mid - 1, item)    # Left half

# Accept number of elements
n = int(input("Enter how many numbers: "))
LIST = []
for i in range(n):
    num = float(input(f"Enter number {i+1}: "))
    LIST.append(num)
print("Number list:", LIST)

# Accept item to search
item = float(input("Enter the element to search: "))

# Perform recursive binary search
LOC = bsearch_recursive(LIST, 0, n - 1, item)

# Display result
if LOC == -1:
    print("Element not found")
else:
    print("Element found at position", LOC)

(a) in Operator

in checks whether a value exists in a list, string, or tuple. If found, it returns True, otherwise False.

(b) index() Function

index() returns the index of the first occurrence of an element in a list. If the element is not in the list, it raises an exception (exception handling is covered in Class 12). Note that indexing starts from 0.