Sorting

# Bubble sort: show list after 3 complete passes
numList = [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]  # list to be sorted

# i = pass number (0 to 2)
for i in range(3):
    # j scans adjacent elements for this pass
    for j in range(0, len(numList) - 1 - i):
        # swap if left element is larger than right element
        if numList[j] > numList[j + 1]:
            numList[j], numList[j + 1] = numList[j + 1], numList[j]  # swap adjacent values
    # show list after each complete pass
    print("After pass", i + 1, ":", numList)

After pass 1 : [7, 3, 10, 11, 17, 1, 4, 21, 5, 23]
After pass 2 : [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]
After pass 3 : [3, 7, 10, 1, 4, 11, 5, 17, 21, 23]

# Compare swaps and comparisons for Selection Sort vs Bubble Sort
numList = [63, 42, 21, 9]  # list to be sorted

def selection_counts(arr):
    a = arr[:]  # working copy of list
    swaps = 0   # counts swaps
    comps = 0   # counts comparisons
    for i in range(len(a) - 1):
        min_idx = i  # index of smallest element in unsorted part
        for j in range(i + 1, len(a)):
            comps += 1  # compare a[j] with current minimum
            if a[j] < a[min_idx]:
                min_idx = j  # update minimum index
        # swap smallest found into correct position
        if min_idx != i:
            a[i], a[min_idx] = a[min_idx], a[i]
            swaps += 1
    return swaps, comps

def bubble_counts(arr):
    a = arr[:]  # working copy of list
    swaps = 0   # counts swaps
    comps = 0   # counts comparisons
    for i in range(len(a) - 1):
        # compare adjacent elements in remaining unsorted range
        for j in range(0, len(a) - 1 - i):
            comps += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]  # swap out-of-order pair
                swaps += 1
    return swaps, comps

sel_swaps, sel_comps = selection_counts(numList)  # selection sort metrics
bub_swaps, bub_comps = bubble_counts(numList)     # bubble sort metrics

print("Selection Sort -> swaps:", sel_swaps, ", comparisons:", sel_comps)
print("Bubble Sort    -> swaps:", bub_swaps, ", comparisons:", bub_comps)
print("Better w.r.t comparisons:", "Both (equal)")
print("Better w.r.t swaps:", "Selection Sort")

Selection Sort -> swaps: 2 , comparisons: 6
Bubble Sort    -> swaps: 6 , comparisons: 6
Better w.r.t comparisons: Both (equal)
Better w.r.t swaps: Selection Sort

def bubble_sort(num_list):
    """
    Sorts the list in ascending order using Bubble Sort.
    (Adjacent elements are compared and swapped if unordered.)
    """
    n = len(num_list)

    # Number of passes = n-1 (in general)
    for i in range(n):
        for j in range(0, n - i - 1):
            # If current element is bigger than next element, swap them
            if num_list[j] > num_list[j + 1]:
                num_list[j], num_list[j + 1] = num_list[j + 1], num_list[j]


def find_median(num_list):
    """
    Finds median of a list:
    - If odd number of terms: center term
    - If even number of terms: average of two middle terms
    """
    bubble_sort(num_list)  # sorting first using Bubble Sort

    n = len(num_list)
    mid = n // 2

    if n % 2 == 1:
        # Odd count -> middle element
        return num_list[mid]
    else:
        # Even count -> average of two middle elements
        return (num_list[mid - 1] + num_list[mid]) / 2


# ---- Input and output ----
raw = input("Enter numbers separated by space: ")
num_list = [int(x) for x in raw.split()]
median_value = find_median(num_list)

print("Sorted List:", num_list)
print("Median:", median_value)

Enter numbers separated by space: 12 4 7 9 3
Sorted List: [3, 4, 7, 9, 12]
Median: 7

Enter numbers separated by space: 10 2 8 4
Sorted List: [2, 4, 8, 10]
Median: 6.0

def selection_sort(marks):
    """
    Sorts the list in ascending order using Selection Sort.
    (Smallest element from unsorted part is selected and swapped.)
    """
    n = len(marks)

    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if marks[j] < marks[min_index]:
                min_index = j
        if min_index != i:
            marks[i], marks[min_index] = marks[min_index], marks[i]


def xth_percentile(marks, x):
    """
    Calculates xth percentile using the given steps.
    """
    selection_sort(marks)  # Step I

    n = len(marks)
    position = (x / 100) * n  # Step II
    position = round(position)  # Step III

    # Convert to 0-based index and keep within range
    index = position - 1
    if index < 0:
        index = 0
    if index >= n:
        index = n - 1

    return marks[index], marks


# ---- Input and output ----
raw = input("Enter marks separated by space: ")
marks_list = [int(x) for x in raw.split()]
x = int(input("Enter percentile (0-100): "))

value, sorted_marks = xth_percentile(marks_list, x)

print("Sorted Marks:", sorted_marks)
print("Percentile Value:", value)

Enter marks separated by space: 55 72 91 60 39 85 77 68 87 49
Enter percentile (0-100): 90
Sorted Marks: [39, 49, 55, 60, 68, 72, 77, 85, 87, 91]
Percentile Value: 87

Enter marks separated by space: 10 20 30 40 50
Enter percentile (0-100): 50
Sorted Marks: [10, 20, 30, 40, 50]
Percentile Value: 30

def insert_name_in_sorted_list(name_list, new_name):
    """
    Inserts new_name into name_list so that the list remains
    in ascending order (a-z). This is like Insertion Sort idea.
    """
    pos = 0

    # Find correct position for insertion
    while pos < len(name_list) and name_list[pos].lower() <= new_name.lower():
        pos += 1

    # Insert at the found position
    name_list.insert(pos, new_name)


# ---- Sample run ----
names = []

n = int(input("How many names? "))

for i in range(n):
    name = input("Enter name: ")
    insert_name_in_sorted_list(names, name)  # invoked every time
    print("List after insertion:", names)

print("Final sorted list:", names)

How many names? 4
Enter name: Riya
List after insertion: ['Riya']
Enter name: Aman
List after insertion: ['Aman', 'Riya']
Enter name: Zoya
List after insertion: ['Aman', 'Riya', 'Zoya']
Enter name: Bharat
List after insertion: ['Aman', 'Bharat', 'Riya', 'Zoya']
Final sorted list: ['Aman', 'Bharat', 'Riya', 'Zoya']