Linear List Manipulation

# Program: Insert and Delete in a sorted list (Python 2)

def insert_sorted(data_list, num):
    # Insert num at correct position to keep ascending order
    pos = 0
    while pos < len(data_list) and data_list[pos] < num:
        pos = pos + 1
    data_list.insert(pos, num)

def delete_number(data_list, num):
    # Delete first occurrence of num if found
    if num in data_list:
        data_list.remove(num)
        return True
    return False

# ---- main part ----
raw = raw_input("Enter sorted numbers (space separated): ")
lst = []
for x in raw.split():
    lst.append(int(x))

print "Original list:", lst

n = int(raw_input("Enter a number to insert: "))
insert_sorted(lst, n)
print "After insertion:", lst

m = int(raw_input("Enter a number to delete: "))
found = delete_number(lst, m)
if found:
    print "After deletion:", lst
else:
    print "Number not found, list unchanged:", lst

# sample output
Enter sorted numbers (space separated): 2 5 9 15 20
Original list: [2, 5, 9, 15, 20]
Enter a number to insert: 10
After insertion: [2, 5, 9, 10, 15, 20]
Enter a number to delete: 5
After deletion: [2, 9, 10, 15, 20]

# Program: Find position of a number in a list using Linear Search (Python 2)

def linear_search(lst, key):
    # Returns index if found, else -1
    for i in range(len(lst)):
        if lst[i] == key:
            return i
    return -1

raw = raw_input("Enter integers (space separated): ")
nums = []
# Build the list from user input
for p in raw.split():
    nums.append(int(p))

print "List:", nums

key = int(raw_input("Enter number to search: "))
# Call linear search function
pos = linear_search(nums, key)

# Display result based on returned index
if pos != -1:
    print "Number found at position (index):", pos
else:
    print "Number not found."

# sample output
Enter integers (space separated): 12 4 99 15 7 4
List: [12, 4, 99, 15, 7, 4]
Enter number to search: 15
Number found at position (index): 3

# sample output (number not present)
Enter integers (space separated): 8 21 34 55 89
List: [8, 21, 34, 55, 89]
Enter number to search: 50
Number not found.

# Program: Binary Search in a sorted list (Python 2)

def binary_search(lst, key):
    # Set initial search boundaries
    low = 0
    high = len(lst) - 1

    # Continue while valid search range exists
    while low <= high:
        mid = (low + high) / 2  # integer division in Python 2
        if lst[mid] == key:
            # Key found at index mid
            return mid
        elif key < lst[mid]:
            # Search in left half
            high = mid - 1
        else:
            # Search in right half
            low = mid + 1
    # Key not found
    return -1

# Given sorted list
sorted_list = [2, 5, 9, 10, 15, 20]
print "Sorted list:", sorted_list

k = input("Enter number to search: ")
# Call binary search function
pos = binary_search(sorted_list, k)

# Display final result
if pos != -1:
    print "Found at index:", pos
else:
    print "Not found."

# sample output
Sorted list: [2, 5, 9, 10, 15, 20]
Enter number to search: 10
Found at index: 3

# Program: Selection Sort for names (Python 2)

def selection_sort_names(lst):
    # Sort list of names in ascending order using selection sort
    n = len(lst)
    # Fix one position at a time
    for i in range(n - 1):
        min_i = i
        # Find index of smallest name in remaining unsorted part
        for j in range(i + 1, n):
            if lst[j] < lst[min_i]:
                min_i = j
        # swap
        temp = lst[i]
        lst[i] = lst[min_i]
        lst[min_i] = temp

# Read names and create list
raw = raw_input("Enter student names (space separated): ")
names = raw.split()
print "Original:", names

# Sort and display result
selection_sort_names(names)
print "Sorted:", names

# sample output
Enter student names (space separated): Riya Aman Neha Kabir
Original: ['Riya', 'Aman', 'Neha', 'Kabir']
Sorted: ['Aman', 'Kabir', 'Neha', 'Riya']

# Program: Selection Sort by marks (descending) - Python 2

def selection_sort_by_marks_desc(lst):
    # Each record format: [roll_no, name, marks]
    n = len(lst)
    # Place highest marks at position i in each pass
    for i in range(n - 1):
        max_i = i
        # Find index of maximum marks in unsorted part
        for j in range(i + 1, n):
            # Compare marks (index 2)
            if lst[j][2] > lst[max_i][2]:
                max_i = j
        # swap current element with maximum-marks element
        temp = lst[i]
        lst[i] = lst[max_i]
        lst[max_i] = temp

students = []
n = int(raw_input("Enter number of students: "))
# Read all student records
for i in range(n):
    print "Enter student", i + 1
    roll = int(raw_input("Roll no: "))
    name = raw_input("Name: ")
    marks = int(raw_input("Marks: "))
    students.append([roll, name, marks])

print "Original:", students
# Sort records by marks in descending order
selection_sort_by_marks_desc(students)
print "Sorted by marks (desc):", students

# sample output
Enter number of students: 4
Enter student 1
Roll no: 1
Name: Aman
Marks: 78
Enter student 2
Roll no: 2
Name: Neha
Marks: 92
Enter student 3
Roll no: 3
Name: Kabir
Marks: 65
Enter student 4
Roll no: 4
Name: Riya
Marks: 92
Original: [[1, 'Aman', 78], [2, 'Neha', 92], [3, 'Kabir', 65], [4, 'Riya', 92]]
Sorted by marks (desc): [[2, 'Neha', 92], [4, 'Riya', 92], [1, 'Aman', 78], [3, 'Kabir', 65]]

# Program: Bubble sort by price (asc) and Insertion sort by qty (desc) - Python 2

def bubble_sort_price_asc(items):
    # Sort items in ascending order of price (index 2)
    n = len(items)
    for i in range(n - 1):
        for j in range(0, n - 1 - i):
            # Compare adjacent prices
            if items[j][2] > items[j + 1][2]:
                temp = items[j]
                items[j] = items[j + 1]
                items[j + 1] = temp

def insertion_sort_qty_desc(items):
    # Sort items in descending order of quantity (index 3)
    for k in range(1, len(items)):
        temp = items[k]
        ptr = k - 1
        # descending by qty => move smaller qty to right
        while ptr >= 0 and items[ptr][3] < temp[3]:
            items[ptr + 1] = items[ptr]
            ptr = ptr - 1
        items[ptr + 1] = temp

items = []
n = int(raw_input("Enter number of items: "))
# Each record format: [item_code, item_name, price, qty]
for i in range(n):
    print "Enter item", i + 1
    Item_code = raw_input("Item code: ")
    Item_name = raw_input("Item name: ")
    price = int(raw_input("Price: "))
    qty = int(raw_input("Qty: "))
    items.append([Item_code, Item_name, price, qty])

print "Original:", items
# Part (a): sort by price in ascending order
bubble_sort_price_asc(items)
print "Sorted by price (asc):", items
# Part (b): sort by quantity in descending order
insertion_sort_qty_desc(items)
print "Sorted by qty (desc):", items

# sample output
Enter number of items: 4
Enter item 1
Item code: I01
Item name: Pen
Price: 10
Qty: 50
Enter item 2
Item code: I02
Item name: Notebook
Price: 60
Qty: 25
Enter item 3
Item code: I03
Item name: Pencil
Price: 5
Qty: 100
Enter item 4
Item code: I04
Item name: Eraser
Price: 8
Qty: 80
Original: [['I01', 'Pen', 10, 50], ['I02', 'Notebook', 60, 25], ['I03', 'Pencil', 5, 100], ['I04', 'Eraser', 8, 80]]
Sorted by price (asc): [['I03', 'Pencil', 5, 100], ['I04', 'Eraser', 8, 80], ['I01', 'Pen', 10, 50], ['I02', 'Notebook', 60, 25]]
Sorted by qty (desc): [['I03', 'Pencil', 5, 100], ['I04', 'Eraser', 8, 80], ['I01', 'Pen', 10, 50], ['I02', 'Notebook', 60, 25]]

# Program: Sort list and find number position (Python 2)

def selection_sort(lst):
    # Sort list in ascending order using selection sort
    n = len(lst)
    # Fix one position at a time
    for i in range(n - 1):
        min_i = i
        # Find index of smallest element in unsorted part
        for j in range(i + 1, n):
            if lst[j] < lst[min_i]:
                min_i = j
        # swap current element with smallest element found
        temp = lst[i]
        lst[i] = lst[min_i]
        lst[min_i] = temp

def binary_search(lst, key):
    # Set search boundaries
    low = 0
    high = len(lst) - 1
    # Search while valid range exists
    while low <= high:
        mid = (low + high) / 2
        if lst[mid] == key:
            # key found
            return mid
        elif key < lst[mid]:
            # key may be in left half
            high = mid - 1
        else:
            # key may be in right half
            low = mid + 1
    # key not found
    return -1

# Read list of numbers from user
raw = raw_input("Enter numbers (space separated): ")
nums = []
for p in raw.split():
    nums.append(int(p))

print "Original:", nums
# Sort before binary search
selection_sort(nums)
print "Sorted:", nums

k = int(raw_input("Enter number to search: "))
# Find position using binary search
pos = binary_search(nums, k)

# Display suitable message
if pos != -1:
    print "Number found at index:", pos
else:
    print "Number not found in the list."

# sample output
Enter numbers (space separated): 9 2 15 1 10
Original: [9, 2, 15, 1, 10]
Sorted: [1, 2, 9, 10, 15]
Enter number to search: 10
Number found at index: 3

# sample output (number not found)
Enter numbers (space separated): 14 7 3 22 9
Original: [14, 7, 3, 22, 9]
Sorted: [3, 7, 9, 14, 22]
Enter number to search: 11
Number not found in the list.