Data Structures and Algorithms in Python

Data Structures and Algorithms in Python

This guide provides sample Python programs for fundamental data structures and algorithms tailored to manage student-related data. Each experiment includes the problem statement, complete code with detailed comments, example input/output, and explanations suitable for beginners to experts.

Table of Contents

Stack Operations
Queue Operations
Circular Queue Operations
Linked List Insertion, Deletion & Copy
Sorting and Searching

5.1. Searching Algorithms

5.1.1. Linear (Sequential) Search
5.1.2. Binary Search

5.2. Sorting Algorithms

5.2.1. Bubble Sort
5.2.2. Selection Sort
5.2.3. Insertion Sort
5.2.4. Quick Sort
5.2.5. Merge Sort

References and Further Reading

1. Stack Operations

Problem Statement

Write a Python program to perform PUSH, POP, PEEP (Peek), and CHANGE operations on a stack that manages student records.

Description

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. In this experiment, each element in the stack represents a student record containing Student ID, Name, and Grade. The primary operations are:

PUSH: Add a student record to the top of the stack.
POP: Remove the top student record from the stack.
PEEP (Peek): View the top student record without removing it.
CHANGE: Modify the value of a student record at a specific position from the top.

1.1. Implementation Using a List

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

class Stack:

def __init__(self, max_size=100):

self.stack = []

self.max_size = max_size

def is_empty(self):

return len(self.stack) == 0

def is_full(self):

return len(self.stack) >= self.max_size

def push(self, student):

if self.is_full():

print("Stack Overflow! Cannot push the student record.")

return

self.stack.append(student)

print(f"Pushed: {student}")

def pop(self):

if self.is_empty():

print("Stack Underflow! Cannot pop.")

return None

student = self.stack.pop()

print(f"Popped: {student}")

return student

def peek(self):

if self.is_empty():

print("Stack is empty. Nothing to peek.")

return None

student = self.stack[-1]

print(f"Top Student: {student}")

return student

def change(self, position, new_student):

if position < 1 or position > len(self.stack):

print("Invalid position!")

return

index = -position

print(f"Changing position {position} from {self.stack[index]} to {new_student}")

self.stack[index] = new_student

def display(self):

if self.is_empty():

print("Stack is empty.")

return

print("Stack elements (top to bottom):")

for student in reversed(self.stack):

print(student)

def main():

stack = Stack()

while True:

print("\n--- Stack Operations Menu ---")

print("1. Push")

print("2. Pop")

print("3. Peek (Peep)")

print("4. Change")

print("5. Display")

print("6. Exit")

choice = input("Enter your choice: ")

if choice == '1':

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

student = Student(student_id, name, grade)

stack.push(student)

elif choice == '2':

stack.pop()

elif choice == '3':

stack.peek()

elif choice == '4':

position = int(input("Enter position to change (1 for top): "))

student_id = input("Enter new Student ID: ")

name = input("Enter new Student Name: ")

grade = input("Enter new Student Grade: ")

new_student = Student(student_id, name, grade)

stack.change(position, new_student)

elif choice == '5':

stack.display()

elif choice == '6':

print("Exiting...")

break

else:

print("Invalid choice! Please try again.")

if __name__ == "__main__":

main()

1.2. Explanation

Student Class:

Represents a student record with student_id, name, and grade.
The __str__ method provides a readable string representation of the student.

Stack Class:

Utilizes a Python list to store student records.
is_empty and is_full methods check the stack's status.
push adds a student to the top, ensuring the stack isn't full.
pop removes the top student, ensuring the stack isn't empty.
peek views the top student without removing it.
change modifies a student at a specified position from the top.
display prints all student records from top to bottom.

Main Function:

Provides a menu-driven interface for performing stack operations.
Continuously prompts the user until they choose to exit.

1.3. Example Run

--- Stack Operations Menu ---

1. Push

2. Pop

3. Peek (Peep)

4. Change

5. Display

6. Exit

Enter your choice: 1

Enter Student ID: S001

Enter Student Name: Alice

Enter Student Grade: A

Pushed: ID: S001, Name: Alice, Grade: A

--- Stack Operations Menu ---

1. Push

2. Pop

3. Peek (Peep)

4. Change

5. Display

6. Exit

Enter your choice: 1

Enter Student ID: S002

Enter Student Name: Bob

Enter Student Grade: B

Pushed: ID: S002, Name: Bob, Grade: B

--- Stack Operations Menu ---

1. Push

2. Pop

3. Peek (Peep)

4. Change

5. Display

6. Exit

Enter your choice: 5

Stack elements (top to bottom):

ID: S002, Name: Bob, Grade: B

ID: S001, Name: Alice, Grade: A

--- Stack Operations Menu ---

1. Push

2. Pop

3. Peek (Peep)

4. Change

5. Display

6. Exit

Enter your choice: 3

Top Student: ID: S002, Name: Bob, Grade: B

--- Stack Operations Menu ---

1. Push

2. Pop

3. Peek (Peep)

4. Change

5. Display

6. Exit

Enter your choice: 4

Enter position to change (1 for top): 2

Enter new Student ID: S003

Enter new Student Name: Charlie

Enter new Student Grade: A+

Changing position 2 from ID: S001, Name: Alice, Grade: A to ID: S003, Name: Charlie, Grade: A+

2. Queue Operations

Problem Statement

Write a Python program to implement insertion (enqueue) and deletion (dequeue) in a queue that manages student records.

Description

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In this experiment, each element in the queue represents a student record containing Student ID, Name, and Grade. The primary operations are:

Enqueue: Add a student record to the rear of the queue.
Dequeue: Remove a student record from the front of the queue.

2.1. Implementation Using collections.deque

from collections import deque

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

class Queue:

def __init__(self, max_size=100):

self.queue = deque()

self.max_size = max_size

def is_empty(self):

return len(self.queue) == 0

def is_full(self):

return len(self.queue) >= self.max_size

def enqueue(self, student):

if self.is_full():

print("Queue Overflow! Cannot enqueue the student record.")

return

self.queue.append(student)

print(f"Enqueued: {student}")

def dequeue(self):

if self.is_empty():

print("Queue Underflow! Cannot dequeue.")

return None

student = self.queue.popleft()

print(f"Dequeued: {student}")

return student

def display(self):

if self.is_empty():

print("Queue is empty.")

return

print("Queue elements (front to rear):")

for student in self.queue:

print(student)

def main():

queue = Queue()

while True:

print("\n--- Queue Operations Menu ---")

print("1. Enqueue")

print("2. Dequeue")

print("3. Display")

print("4. Exit")

choice = input("Enter your choice: ")

if choice == '1':

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

student = Student(student_id, name, grade)

queue.enqueue(student)

elif choice == '2':

queue.dequeue()

elif choice == '3':

queue.display()

elif choice == '4':

print("Exiting...")

break

else:

print("Invalid choice! Please try again.")

if __name__ == "__main__":

main()

2.2. Explanation

Student Class:

Represents a student record with student_id, name, and grade.
The __str__ method provides a readable string representation of the student.

Queue Class:

Utilizes collections.deque for efficient queue operations.
is_empty and is_full methods check the queue's status.
enqueue adds a student to the rear, ensuring the queue isn't full.
dequeue removes a student from the front, ensuring the queue isn't empty.
display prints all student records from front to rear.

Main Function:

Provides a menu-driven interface for performing queue operations.
Continuously prompts the user until they choose to exit.

2.3. Example Run

--- Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 1

Enter Student ID: S101

Enter Student Name: David

Enter Student Grade: B+

Enqueued: ID: S101, Name: David, Grade: B+

--- Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 1

Enter Student ID: S102

Enter Student Name: Eva

Enter Student Grade: A

Enqueued: ID: S102, Name: Eva, Grade: A

--- Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 3

Queue elements (front to rear):

ID: S101, Name: David, Grade: B+

ID: S102, Name: Eva, Grade: A

--- Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 2

Dequeued: ID: S101, Name: David, Grade: B+

--- Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 3

Queue elements (front to rear):

ID: S102, Name: Eva, Grade: A

--- Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 4

Exiting...

3. Circular Queue Operations

Problem Statement

Write a Python program to implement insertion (enqueue) and deletion (dequeue) in a circular queue that manages student records.

Description

A circular queue is a linear data structure that connects the end back to the front to utilize space efficiently. This implementation ensures that the queue can wrap around to the beginning when there's available space after dequeue operations. Each element in the circular queue represents a student record containing Student ID, Name, and Grade.

3.1. Implementation Using a List

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

class CircularQueue:

def __init__(self, max_size=5):

self.queue = [None] * max_size

self.max_size = max_size

self.front = -1

self.rear = -1

def is_empty(self):

return self.front == -1

def is_full(self):

return (self.rear + 1) % self.max_size == self.front

def enqueue(self, student):

if self.is_full():

print("Circular Queue Overflow! Cannot enqueue the student record.")

return

if self.is_empty():

self.front = 0

self.rear = (self.rear + 1) % self.max_size

self.queue[self.rear] = student

print(f"Enqueued: {student}")

def dequeue(self):

if self.is_empty():

print("Circular Queue Underflow! Cannot dequeue.")

return None

student = self.queue[self.front]

self.queue[self.front] = None # Optional: Clear the spot

if self.front == self.rear:

# Queue becomes empty

self.front = -1

self.rear = -1

else:

self.front = (self.front + 1) % self.max_size

print(f"Dequeued: {student}")

return student

def display(self):

if self.is_empty():

print("Circular Queue is empty.")

return

print("Circular Queue elements (front to rear):")

index = self.front

while True:

print(self.queue[index])

if index == self.rear:

break

index = (index + 1) % self.max_size

def main():

cq = CircularQueue(max_size=5)

while True:

print("\n--- Circular Queue Operations Menu ---")

print("1. Enqueue")

print("2. Dequeue")

print("3. Display")

print("4. Exit")

choice = input("Enter your choice: ")

if choice == '1':

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

student = Student(student_id, name, grade)

cq.enqueue(student)

elif choice == '2':

cq.dequeue()

elif choice == '3':

cq.display()

elif choice == '4':

print("Exiting...")

break

else:

print("Invalid choice! Please try again.")

if __name__ == "__main__":

main()

3.2. Explanation

Student Class:

Represents a student record with student_id, name, and grade.
The __str__ method provides a readable string representation of the student.

CircularQueue Class:

Uses a fixed-size list to represent the circular queue.
front and rear pointers track the start and end of the queue.
is_empty checks if the queue is empty.
is_full checks if the queue is full based on the circular condition.
enqueue adds a student to the rear, ensuring the queue isn't full. If the queue is empty, it initializes front.
dequeue removes a student from the front, ensuring the queue isn't empty. Adjusts pointers accordingly.
display prints all student records from front to rear, handling the circular nature.

Main Function:

Provides a menu-driven interface for performing circular queue operations.
Continuously prompts the user until they choose to exit.

3.3. Example Run

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 1

Enter Student ID: S201

Enter Student Name: Frank

Enter Student Grade: B

Enqueued: ID: S201, Name: Frank, Grade: B

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 1

Enter Student ID: S202

Enter Student Name: Grace

Enter Student Grade: A-

Enqueued: ID: S202, Name: Grace, Grade: A-

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 1

Enter Student ID: S203

Enter Student Name: Hannah

Enter Student Grade: B+

Enqueued: ID: S203, Name: Hannah, Grade: B+

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 3

Circular Queue elements (front to rear):

ID: S201, Name: Frank, Grade: B

ID: S202, Name: Grace, Grade: A-

ID: S203, Name: Hannah, Grade: B+

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 2

Dequeued: ID: S201, Name: Frank, Grade: B

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 1

Enter Student ID: S204

Enter Student Name: Ian

Enter Student Grade: A

Enqueued: ID: S204, Name: Ian, Grade: A

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 1

Enter Student ID: S205

Enter Student Name: Jane

Enter Student Grade: B-

Enqueued: ID: S205, Name: Jane, Grade: B-

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 1

Enter Student ID: S206

Enter Student Name: Kyle

Enter Student Grade: A+

Circular Queue Overflow! Cannot enqueue the student record.

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 3

Circular Queue elements (front to rear):

ID: S202, Name: Grace, Grade: A-

ID: S203, Name: Hannah, Grade: B+

ID: S204, Name: Ian, Grade: A

ID: S205, Name: Jane, Grade: B-

--- Circular Queue Operations Menu ---

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice: 4

Exiting...

4. Linked List Insertion, Deletion & Copy

Problem Statement

Write a Python program for linked list insertion, deletion, and copy operations to manage student records.

Description

A linked list is a dynamic data structure consisting of nodes where each node contains data and a reference to the next node. This implementation covers:

Insertion: At the beginning, end, and specific positions.
Deletion: From the beginning, end, and specific positions.
Copying: Creating a duplicate of the existing linked list.

Each node in the linked list represents a student record containing Student ID, Name, and Grade.

4.1. Implementation Using Singly Linked List

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

class Node:

def __init__(self, student):

self.student = student

self.next = None

class LinkedList:

def __init__(self):

self.head = None

# Insert at the beginning

def insert_at_beginning(self, student):

new_node = Node(student)

new_node.next = self.head

self.head = new_node

print(f"Inserted at beginning: {student}")

# Insert at the end

def insert_at_end(self, student):

new_node = Node(student)

if not self.head:

self.head = new_node

print(f"Inserted as the first node: {student}")

return

last = self.head

while last.next:

last = last.next

last.next = new_node

print(f"Inserted at end: {student}")

# Insert after a given position

def insert_after_position(self, position, student):

if position < 1:

print("Invalid position!")

return

current = self.head

for _ in range(position - 1):

if not current:

print("Position exceeds list length.")

return

current = current.next

if not current:

print("Position exceeds list length.")

return

new_node = Node(student)

new_node.next = current.next

current.next = new_node

print(f"Inserted after position {position}: {student}")

# Delete from the beginning

def delete_from_beginning(self):

if not self.head:

print("List is empty. Cannot delete.")

return

removed = self.head.student

self.head = self.head.next

print(f"Deleted from beginning: {removed}")

# Delete from the end

def delete_from_end(self):

if not self.head:

print("List is empty. Cannot delete.")

return

if not self.head.next:

removed = self.head.student

self.head = None

print(f"Deleted from end: {removed}")

return

current = self.head

while current.next.next:

current = current.next

removed = current.next.student

current.next = None

print(f"Deleted from end: {removed}")

# Delete at a specific position

def delete_at_position(self, position):

if not self.head or position < 1:

print("Invalid position or empty list.")

return

if position == 1:

self.delete_from_beginning()

return

current = self.head

for _ in range(position - 2):

if not current.next:

print("Position exceeds list length.")

return

current = current.next

if not current.next:

print("Position exceeds list length.")

return

removed = current.next.student

current.next = current.next.next

print(f"Deleted at position {position}: {removed}")

# Display the linked list

def display(self):

if not self.head:

print("Linked List is empty.")

return

print("Linked List elements:")

current = self.head

position = 1

while current:

print(f"Position {position}: {current.student}")

current = current.next

position += 1

# Copy the linked list

def copy_list(self):

if not self.head:

print("Original list is empty. Cannot copy.")

return None

copied_list = LinkedList()

current_original = self.head

while current_original:

copied_student = Student(current_original.student.student_id,

current_original.student.name,

current_original.student.grade)

copied_list.insert_at_end(copied_student)

current_original = current_original.next

print("Linked List copied successfully.")

return copied_list

def main():

ll = LinkedList()

copied_ll = None

while True:

print("\n--- Linked List Operations Menu ---")

print("1. Insert at Beginning")

print("2. Insert at End")

print("3. Insert after Position")

print("4. Delete from Beginning")

print("5. Delete from End")

print("6. Delete at Position")

print("7. Display Linked List")

print("8. Copy Linked List")

print("9. Display Copied Linked List")

print("10. Exit")

choice = input("Enter your choice: ")

if choice == '1':

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

student = Student(student_id, name, grade)

ll.insert_at_beginning(student)

elif choice == '2':

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

student = Student(student_id, name, grade)

ll.insert_at_end(student)

elif choice == '3':

position = int(input("Enter position after which to insert: "))

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

student = Student(student_id, name, grade)

ll.insert_after_position(position, student)

elif choice == '4':

ll.delete_from_beginning()

elif choice == '5':

ll.delete_from_end()

elif choice == '6':

position = int(input("Enter position to delete: "))

ll.delete_at_position(position)

elif choice == '7':

ll.display()

elif choice == '8':

copied_ll = ll.copy_list()

elif choice == '9':

if copied_ll:

copied_ll.display()

else:

print("No copied list available.")

elif choice == '10':

print("Exiting...")

break

else:

print("Invalid choice! Please try again.")

if __name__ == "__main__":

main()

4.2. Explanation

Student Class:

Represents a student record with student_id, name, and grade.
The __str__ method provides a readable string representation of the student.

Node Class:

Represents a node in the linked list containing a Student object and a reference to the next node.

LinkedList Class:

Manages the linked list operations.
Insertion Methods:

insert_at_beginning: Inserts a student at the start of the list.
insert_at_end: Inserts a student at the end of the list.
insert_after_position: Inserts a student after a specified position.

Deletion Methods:

delete_from_beginning: Removes the first student in the list.
delete_from_end: Removes the last student in the list.
delete_at_position: Removes a student from a specified position.

Display Method:

display: Prints all student records with their positions.

Copy Method:

copy_list: Creates a deep copy of the current linked list by creating new Student and Node instances.

Main Function:

Provides a menu-driven interface for performing linked list operations.
Allows the user to copy the linked list and display the copied list separately.

4.3. Example Run

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 1

Enter Student ID: S301

Enter Student Name: Liam

Enter Student Grade: A

Inserted at beginning: ID: S301, Name: Liam, Grade: A

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 2

Enter Student ID: S302

Enter Student Name: Mia

Enter Student Grade: B

Inserted at end: ID: S302, Name: Mia, Grade: B

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 3

Enter position after which to insert: 1

Enter Student ID: S303

Enter Student Name: Noah

Enter Student Grade: A-

Inserted after position 1: ID: S303, Name: Noah, Grade: A-

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 7

Linked List elements:

Position 1: ID: S301, Name: Liam, Grade: A

Position 2: ID: S303, Name: Noah, Grade: A-

Position 3: ID: S302, Name: Mia, Grade: B

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 4

Deleted from beginning: ID: S301, Name: Liam, Grade: A

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 7

Linked List elements:

Position 1: ID: S303, Name: Noah, Grade: A-

Position 2: ID: S302, Name: Mia, Grade: B

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 8

Inserted at end: ID: S303, Name: Noah, Grade: A-

Inserted at end: ID: S302, Name: Mia, Grade: B

Linked List copied successfully.

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 9

Linked List elements:

Position 1: ID: S303, Name: Noah, Grade: A-

Position 2: ID: S302, Name: Mia, Grade: B

--- Linked List Operations Menu ---

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Delete from Beginning

5. Delete from End

6. Delete at Position

7. Display Linked List

8. Copy Linked List

9. Display Copied Linked List

10. Exit

Enter your choice: 10

Exiting...

5. Sorting and Searching

Problem Statement

Write Python programs to perform Sequential (Linear) and Binary searches, as well as Quick Sort, Merge Sort, Bubble Sort, and Selection Sort on student records.

Description

This section includes implementations of fundamental searching and sorting algorithms applied to student records. Each algorithm includes a Python program with comments and explanations. The student records consist of Student ID, Name, and Grade.

5.1. Searching Algorithms

5.1.1. Linear (Sequential) Search

Description: Linear search traverses the list sequentially to find the target student based on Student ID.

Implementation:

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

def linear_search(students, target_id):

for index, student in enumerate(students):

if student.student_id == target_id:

return index

return -1

def main():

print("Linear Search for Student Records")

n = int(input("Enter number of students: "))

students = []

for _ in range(n):

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

students.append(Student(student_id, name, grade))

target_id = input("Enter Student ID to search: ")

index = linear_search(students, target_id)

if index != -1:

print(f"Student found at index {index}: {students[index]}")

else:

print(f"Student with ID {target_id} not found.")

if __name__ == "__main__":

main()

Example Run:

Linear Search for Student Records

Enter number of students: 3

Enter Student ID: S401

Enter Student Name: Olivia

Enter Student Grade: A

Enter Student ID: S402

Enter Student Name: Liam

Enter Student Grade: B+

Enter Student ID: S403

Enter Student Name: Emma

Enter Student Grade: A-

Enter Student ID to search: S402

Student found at index 1: ID: S402, Name: Liam, Grade: B+

5.1.2. Binary Search

Description: Binary search efficiently finds the target student based on Student ID by repeatedly dividing the sorted list in half. Note: The list must be sorted by Student ID before performing binary search.

Implementation:

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

def binary_search(students, target_id):

left = 0

right = len(students) - 1

while left <= right:

mid = left + (right - left) // 2

if students[mid].student_id == target_id:

return mid

elif students[mid].student_id < target_id:

left = mid + 1

else:

right = mid - 1

return -1

def main():

print("Binary Search for Student Records (List must be sorted by Student ID)")

n = int(input("Enter number of students: "))

students = []

for _ in range(n):

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

students.append(Student(student_id, name, grade))

# Sorting the list by Student ID to prepare for binary search

students.sort(key=lambda x: x.student_id)

print("\nStudents sorted by Student ID:")

for student in students:

print(student)

target_id = input("\nEnter Student ID to search: ")

index = binary_search(students, target_id)

if index != -1:

print(f"Student found at index {index}: {students[index]}")

else:

print(f"Student with ID {target_id} not found.")

if __name__ == "__main__":

main()

Example Run:

Binary Search for Student Records (List must be sorted by Student ID)

Enter number of students: 3

Enter Student ID: S501

Enter Student Name: Sophia

Enter Student Grade: A

Enter Student ID: S503

Enter Student Name: Jackson

Enter Student Grade: B

Enter Student ID: S502

Enter Student Name: Ava

Enter Student Grade: A-

Students sorted by Student ID:

ID: S501, Name: Sophia, Grade: A

ID: S502, Name: Ava, Grade: A-

ID: S503, Name: Jackson, Grade: B

Enter Student ID to search: S502

Student found at index 1: ID: S502, Name: Ava, Grade: A-

5.2. Sorting Algorithms

5.2.1. Bubble Sort

Description: Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order based on Student ID.

Implementation:

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

def bubble_sort(students):

n = len(students)

for i in range(n):

swapped = False

for j in range(0, n-i-1):

if students[j].student_id > students[j+1].student_id:

students[j], students[j+1] = students[j+1], students[j]

swapped = True

if not swapped:

break

def display_students(students):

for student in students:

print(student)

def main():

print("Bubble Sort for Student Records")

n = int(input("Enter number of students: "))

students = []

for _ in range(n):

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

students.append(Student(student_id, name, grade))

print("\nStudents before sorting:")

display_students(students)

bubble_sort(students)

print("\nStudents after Bubble Sort by Student ID:")

display_students(students)

if __name__ == "__main__":

main()

Example Run:

Bubble Sort for Student Records

Enter number of students: 3

Enter Student ID: S601

Enter Student Name: Isabella

Enter Student Grade: A

Enter Student ID: S603

Enter Student Name: Ethan

Enter Student Grade: B+

Enter Student ID: S602

Enter Student Name: Mia

Enter Student Grade: A-

Students before sorting:

ID: S601, Name: Isabella, Grade: A

ID: S603, Name: Ethan, Grade: B+

ID: S602, Name: Mia, Grade: A-

Students after Bubble Sort by Student ID:

ID: S601, Name: Isabella, Grade: A

ID: S602, Name: Mia, Grade: A-

ID: S603, Name: Ethan, Grade: B+

5.2.2. Selection Sort

Description: Selection Sort divides the list into a sorted and unsorted region. It repeatedly selects the smallest Student ID from the unsorted region and moves it to the end of the sorted region.

Implementation:

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

def selection_sort(students):

n = len(students)

for i in range(n):

min_idx = i

for j in range(i+1, n):

if students[j].student_id < students[min_idx].student_id:

min_idx = j

if min_idx != i:

students[i], students[min_idx] = students[min_idx], students[i]

def display_students(students):

for student in students:

print(student)

def main():

print("Selection Sort for Student Records")

n = int(input("Enter number of students: "))

students = []

for _ in range(n):

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

students.append(Student(student_id, name, grade))

print("\nStudents before sorting:")

display_students(students)

selection_sort(students)

print("\nStudents after Selection Sort by Student ID:")

display_students(students)

if __name__ == "__main__":

main()

Example Run:

Selection Sort for Student Records

Enter number of students: 3

Enter Student ID: S701

Enter Student Name: Lucas

Enter Student Grade: B

Enter Student ID: S703

Enter Student Name: Charlotte

Enter Student Grade: A

Enter Student ID: S702

Enter Student Name: Amelia

Enter Student Grade: A-

Students before sorting:

ID: S701, Name: Lucas, Grade: B

ID: S703, Name: Charlotte, Grade: A

ID: S702, Name: Amelia, Grade: A-

Students after Selection Sort by Student ID:

ID: S701, Name: Lucas, Grade: B

ID: S702, Name: Amelia, Grade: A-

ID: S703, Name: Charlotte, Grade: A

5.2.3. Insertion Sort

Description: Insertion Sort builds the sorted list one student at a time by repeatedly picking the next student and inserting it into the correct position based on Student ID.

Implementation:

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

def insertion_sort(students):

for i in range(1, len(students)):

key_student = students[i]

j = i - 1

while j >= 0 and students[j].student_id > key_student.student_id:

students[j + 1] = students[j]

j -= 1

students[j + 1] = key_student

def display_students(students):

for student in students:

print(student)

def main():

print("Insertion Sort for Student Records")

n = int(input("Enter number of students: "))

students = []

for _ in range(n):

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

students.append(Student(student_id, name, grade))

print("\nStudents before sorting:")

display_students(students)

insertion_sort(students)

print("\nStudents after Insertion Sort by Student ID:")

display_students(students)

if __name__ == "__main__":

main()

Example Run:

Insertion Sort for Student Records

Enter number of students: 3

Enter Student ID: S801

Enter Student Name: Mason

Enter Student Grade: B+

Enter Student ID: S803

Enter Student Name: Harper

Enter Student Grade: A

Enter Student ID: S802

Enter Student Name: Ella

Enter Student Grade: A-

Students before sorting:

ID: S801, Name: Mason, Grade: B+

ID: S803, Name: Harper, Grade: A

ID: S802, Name: Ella, Grade: A-

Students after Insertion Sort by Student ID:

ID: S801, Name: Mason, Grade: B+

ID: S802, Name: Ella, Grade: A-

ID: S803, Name: Harper, Grade: A

5.2.4. Quick Sort

Description: Quick Sort is a divide-and-conquer algorithm that selects a 'pivot' student and partitions the list into sublists of students with Student ID less than and greater than the pivot, then recursively sorts the sublists.

Implementation:

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

def partition(students, low, high):

pivot = students[high].student_id

i = low - 1

for j in range(low, high):

if students[j].student_id < pivot:

i += 1

students[i], students[j] = students[j], students[i]

students[i + 1], students[high] = students[high], students[i + 1]

return i + 1

def quick_sort(students, low, high):

if low < high:

pi = partition(students, low, high)

quick_sort(students, low, pi - 1)

quick_sort(students, pi + 1, high)

def display_students(students):

for student in students:

print(student)

def main():

print("Quick Sort for Student Records")

n = int(input("Enter number of students: "))

students = []

for _ in range(n):

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

students.append(Student(student_id, name, grade))

print("\nStudents before sorting:")

display_students(students)

quick_sort(students, 0, len(students) - 1)

print("\nStudents after Quick Sort by Student ID:")

display_students(students)

if __name__ == "__main__":

main()

Example Run:

Quick Sort for Student Records

Enter number of students: 3

Enter Student ID: S901

Enter Student Name: Benjamin

Enter Student Grade: A-

Enter Student ID: S903

Enter Student Name: Abigail

Enter Student Grade: B

Enter Student ID: S902

Enter Student Name: Lucas

Enter Student Grade: A

Students before sorting:

ID: S901, Name: Benjamin, Grade: A-

ID: S903, Name: Abigail, Grade: B

ID: S902, Name: Lucas, Grade: A

Students after Quick Sort by Student ID:

ID: S901, Name: Benjamin, Grade: A-

ID: S902, Name: Lucas, Grade: A

ID: S903, Name: Abigail, Grade: B

5.2.5. Merge Sort

Description: Merge Sort is a divide-and-conquer algorithm that divides the list into halves, recursively sorts each half, and then merges the sorted halves.

Implementation:

class Student:

def __init__(self, student_id, name, grade):

self.student_id = student_id

self.name = name

self.grade = grade

def __str__(self):

return f"ID: {self.student_id}, Name: {self.name}, Grade: {self.grade}"

def merge(left, right):

merged = []

i = j = 0

while i < len(left) and j < len(right):

if left[i].student_id <= right[j].student_id:

merged.append(left[i])

i += 1

else:

merged.append(right[j])

j += 1

# Append remaining elements

merged.extend(left[i:])

merged.extend(right[j:])

return merged

def merge_sort(students):

if len(students) <= 1:

return students

mid = len(students) // 2

left = merge_sort(students[:mid])

right = merge_sort(students[mid:])

return merge(left, right)

def display_students(students):

for student in students:

print(student)

def main():

print("Merge Sort for Student Records")

n = int(input("Enter number of students: "))

students = []

for _ in range(n):

student_id = input("Enter Student ID: ")

name = input("Enter Student Name: ")

grade = input("Enter Student Grade: ")

students.append(Student(student_id, name, grade))

print("\nStudents before sorting:")

display_students(students)

sorted_students = merge_sort(students)

print("\nStudents after Merge Sort by Student ID:")

display_students(sorted_students)

if __name__ == "__main__":

main()

Example Run:

Merge Sort for Student Records

Enter number of students: 3

Enter Student ID: S1001

Enter Student Name: Sophia

Enter Student Grade: A

Enter Student ID: S1003

Enter Student Name: Jackson

Enter Student Grade: B

Enter Student ID: S1002

Enter Student Name: Ava

Enter Student Grade: A-

Students before sorting:

ID: S1001, Name: Sophia, Grade: A

ID: S1003, Name: Jackson, Grade: B

ID: S1002, Name: Ava, Grade: A-

Students after Merge Sort by Student ID:

ID: S1001, Name: Sophia, Grade: A

ID: S1002, Name: Ava, Grade: A-

ID: S1003, Name: Jackson, Grade: B

5.3. Summary of Sorting Algorithms

Algorithm	Time Complexity (Average)	Space Complexity	Stability
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	No
Insertion Sort	O(n²)	O(1)	Yes
Quick Sort	O(n log n)	O(log n)	No
Merge Sort	O(n log n)	O(n)	Yes

6. References and Further Reading

Books:

"Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
"Data Structures and Algorithms in Python" by Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser.
"Algorithms in Python" by Robert Sedgewick.

Online Resources:

GeeksforGeeks: www.geeksforgeeks.org
TutorialsPoint: www.tutorialspoint.com
Coursera: Courses on Data Structures and Algorithms.
MIT OpenCourseWare: ocw.mit.edu offers free courses and materials.

Interactive Platforms:

LeetCode: leetcode.com for practicing coding problems.
HackerRank: www.hackerrank.com for algorithm challenges.

Documentation:

Wikipedia: Comprehensive articles on all data structures and algorithms.
Official Python Documentation: docs.python.org for language-specific details.

Knowledge for every one

Search This Blog