Sorting and Searching

Sorting is arranging elements in a specific logical order: ascending or descending for numbers, dictionary (alphabetical) order for strings. Sorted data is easier to access, interpret and process, and makes efficient searching (like binary search) possible.

Bubble sort and selection sort. Python also provides the built-in sort() and sorted() functions.

The algorithm moves through the list comparing each pair of adjacent elements and swaps them if they are in the wrong order, then moves to the next pair until the end of the list. After one pass, the largest element is at the end. The process is repeated on the remaining unsorted part. It is called bubble sort because the larger elements "bubble" towards the end of the list.

The sorted list is 4, 7, 11, 12, 23.

N – 1 passes. In each pass the number of elements compared reduces by one, because the largest element of the pass moves to its correct position at the end. For 5 elements: 4 passes, with 4, 3, 2 and 1 comparisons respectively.

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

def bubble_sort(LIST):
    n = len(LIST)
    for last in range(n - 1, 0, -1):          # n-1 passes
        for j in range(0, last):              # compare up to the unsorted end
            if LIST[j] > LIST[j + 1]:
                LIST[j], LIST[j + 1] = LIST[j + 1], LIST[j]    # swap
    return LIST

N = int(input("Enter number of elements: "))
LIST = []
for i in range(N):
    LIST.append(int(input("Enter element: ")))
print("Sorted list:", bubble_sort(LIST))

For 23, 12, 7, 11, 4 the output is [4, 7, 11, 12, 23]. Changing the condition to LIST[j] < LIST[j + 1] sorts in descending order.

def bubble(LIST, last):
    for j in range(0, last):
        if LIST[j] > LIST[j + 1]:
            LIST[j], LIST[j + 1] = LIST[j + 1], LIST[j]
    return LIST

def bubble_sort(LIST):
    n = len(LIST)
    for last in range(n - 1, 0, -1):
        LIST = bubble(LIST, last)
    return LIST

data = [23, 12, 7, 11, 4]
print(bubble_sort(data))     # [4, 7, 11, 12, 23]

The outer function calls bubble() N – 1 times with a shrinking value of last.

It finds the smallest value in the list and places it in the first position, swapping it with the element that was there. It then finds the second smallest and places it in the second position, and so on until the list is sorted. 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 are N – 1 passes. If the smallest value is already in the correct place, no exchange is made in that pass.

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

def selection_sort(LIST):
    n = len(LIST)
    for i in range(n - 1):
        pos = i                          # position of the smallest so far
        for j in range(i + 1, n):
            if LIST[j] < LIST[pos]:
                pos = j
        if pos != i:                     # exchange only if needed
            LIST[i], LIST[pos] = LIST[pos], LIST[i]
    return LIST

N = int(input("Enter number of elements: "))
LIST = []
for i in range(N):
    LIST.append(int(input("Enter element: ")))
print("Sorted list:", selection_sort(LIST))

For 32, 23, 10, 2, 30 the output is [2, 10, 23, 30, 32].

def exchange(LIST, first, n):
    # find the smallest element from index 'first' to n-1 and swap it to 'first'
    pos = first
    for j in range(first + 1, n):
        if LIST[j] < LIST[pos]:
            pos = j
    if pos != first:
        LIST[first], LIST[pos] = LIST[pos], LIST[first]
    return LIST

def selection_sort(LIST):
    n = len(LIST)
    for first in range(n - 1):          # n-1 calls
        LIST = exchange(LIST, first, n)
    return LIST

print(selection_sort([32, 23, 10, 2, 30]))    # [2, 10, 23, 30, 32]

sort() arranges the elements of a list in ascending order by default and modifies the original list (it does not create a new one). It works only with lists. Use reverse=True for descending order.

nums = [40, 10, 30, 20]
nums.sort()
print(nums)                  # [10, 20, 30, 40]
nums.sort(reverse=True)
print(nums)                  # [40, 30, 20, 10]

Strings are sorted alphabetically by default. The key parameter names a function that decides the sorting criterion; key=len sorts by word length.

words = ["banana", "fig", "apple", "kiwi"]
words.sort()
print(words)                 # ['apple', 'banana', 'fig', 'kiwi']
words.sort(key=len)
print(words)                 # ['fig', 'kiwi', 'apple', 'banana']

sorted() returns a new sorted list from a list, tuple or string and does not modify the original. It also accepts reverse=True and key=len.

marks = (45, 12, 78, 33)
print(sorted(marks))                    # [12, 33, 45, 78]
print(sorted(marks, reverse=True))      # [78, 45, 33, 12]
print(marks)                            # (45, 12, 78, 33) unchanged
print(sorted("python"))                 # ['h', 'n', 'o', 'p', 't', 'y']

Learning these algorithms helps us understand how data is processed, how efficiency is measured, and why some methods perform better in specific situations. It strengthens programming skills and prepares us for advanced concepts.

Searching is finding the location of a given element in a collection (list, array, database): whether it is present and, if so, where. The most frequently used algorithms are linear search, where each element is checked one by one, and binary search, which works efficiently on sorted elements.

Binary search locates an element in a sorted list using the minimum number of comparisons. It checks the middle element: if it matches, the search ends; if the search value is smaller, the search continues in the first half; if larger, in the second half. Repeatedly halving the list quickly narrows down the position. The list must be sorted.

45 is at index 4, i.e. position 5.

Now FIRST (4) > LAST (3), so the loop ends. LOC is still –1 and the program displays "Not Found".

Step 1: Start
Step 2: Accept N
Step 3: Accept N elements into LIST in sorted order
Step 4: Accept the value to search in ITEM
Step 5: Set LOC = –1
Step 6: Store the position of the first element in FIRST and of the last in LAST
Step 7: Repeat Steps 8 to 12 while FIRST <= LAST
Step 8: Find MIDDLE = (FIRST + LAST) / 2
Step 9: Compare ITEM with the element at MIDDLE
Step 10: If equal, store the position in LOC and stop searching (go to Step 13)
Step 11: If ITEM is larger, set FIRST = MIDDLE + 1
Step 12: If ITEM is smaller, set LAST = MIDDLE – 1
Step 13: If LOC < 0 display "Not Found", else display LOC + 1 as the position
Step 14: Stop

def binary_search(LIST, ITEM):
    first = 0
    last = len(LIST) - 1
    while first <= last:
        middle = (first + last) // 2
        if LIST[middle] == ITEM:
            return middle
        elif ITEM > LIST[middle]:
            first = middle + 1
        else:
            last = middle - 1
    return -1

N = int(input("Enter number of elements: "))
LIST = []
for i in range(N):
    LIST.append(int(input("Enter element in sorted order: ")))
ITEM = int(input("Enter the item to search: "))
loc = binary_search(LIST, ITEM)
if loc < 0:
    print("Not Found")
else:
    print("Found at position", loc + 1)

The integer division // gives a whole-number middle index.

def bsearch_recursive(LIST, ITEM, first, last):
    if first > last:                    # base case: not found
        return -1
    middle = (first + last) // 2
    if LIST[middle] == ITEM:            # base case: found
        return middle
    elif ITEM < LIST[middle]:
        return bsearch_recursive(LIST, ITEM, first, middle - 1)   # first half
    else:
        return bsearch_recursive(LIST, ITEM, middle + 1, last)    # second half

data = [21, 28, 33, 35, 45, 58, 61]
loc = bsearch_recursive(data, 45, 0, len(data) - 1)
print("Not Found" if loc < 0 else "Found at position " + str(loc + 1))

Output: Found at position 5. Each call searches only one half, so the problem repeats on a smaller list, which is why recursion suits binary search.

For a list of 1000 elements, linear search may need up to 1000 comparisons; binary search needs at most about 10.

The first half is searched, so LAST = MIDDLE – 1. If the middle element is smaller than the item, the second half is searched and FIRST = MIDDLE + 1.

It checks whether a value exists in a list, string or tuple; it returns True if found and False otherwise.

marks = [45, 12, 78, 33]
print(78 in marks)       # True
print(50 in marks)       # False

index() returns the index of the first occurrence of an element in a list (starting from 0). If the element is not in the list it raises an exception (ValueError); handling exceptions is taught in Class 12.

marks = [45, 12, 78, 33]
print(marks.index(78))    # 2
print(marks.index(50))    # ValueError: 50 is not in list

Combine with in to avoid the error: if 50 in marks: print(marks.index(50)).

names = ["Asha", "Meenakshi", "Raju", "Sreeja"]
names.sort(key=len, reverse=True)
print(names)     # ['Meenakshi', 'Sreeja', 'Asha', 'Raju']

Names of equal length keep their original relative order.

def bubble_sort(L):
    for last in range(len(L) - 1, 0, -1):
        for j in range(last):
            if L[j] > L[j + 1]:
                L[j], L[j + 1] = L[j + 1], L[j]
    return L

def binary_search(L, item):
    first, last = 0, len(L) - 1
    while first <= last:
        mid = (first + last) // 2
        if L[mid] == item:
            return mid
        elif item > L[mid]:
            first = mid + 1
        else:
            last = mid - 1
    return -1

data = list(map(int, input("Enter numbers separated by spaces: ").split()))
bubble_sort(data)
print("Sorted:", data)
item = int(input("Search for: "))
loc = binary_search(data, item)
print("Found at position", loc + 1 if loc >= 0 else "Not Found")

• Bubble sort needs ______ passes for N elements: N – 1.
• After the first pass of bubble sort, the ______ element is at the end: largest.
• Binary search requires the list to be ______: sorted.
• Function that sorts a list in place: sort(); function that returns a new sorted list: sorted().
• Argument for descending order: reverse=True; argument to sort by length: key=len.
• Operator that checks presence of a value: in.
• Function giving the first index of an element: index().