Python OOP

 

Python OOP – Deeper Concepts Explained with Examples

Introduction: Going Beyond the Basics of Python OOP

Have you ever wondered how Python can be used to create real-world applications such as banking systems, school management software, online shopping websites, and games?

One important answer is Object-Oriented Programming (OOP).

In our earlier Python tutorials, we learned about classes, objects, inheritance, encapsulation, and polymorphism. These concepts help us organise programs and reuse code.

But Python OOP has several more useful concepts that help us write cleaner, more reusable, and maintainable programs.

In this tutorial, we will learn:

1. Constructors and __init__()

2. The meaning of self

3. Instance variables and class variables

4. Instance methods

5. Class methods

6. Static methods

7. Method overriding

8. The super() function

9. Abstract classes

10. Composition

11. Association

12. Aggregation

We will understand each concept using simple explanations, Python code, and real-world examples.

1. Constructors in Python

What is a constructor?

A constructor helps initialise an object when it is created.

In Python, the special method __init__() is commonly called the constructor, although technically it is the initialisation method. Python creates the object first using __new__(), and then calls __init__() to initialise it.

Consider a school application that stores student information. Whenever we create a new student, we want to assign a name and class.

Without initialisation, we might have to assign these values separately after creating the object.

Example: Using __init__()

class Student:
    def __init__(self, name, class_name):
        self.name = name
        self.class_name = class_name

    def display(self):
        print("Name:", self.name)
        print("Class:", self.class_name)


s1 = Student("Rahul", "9")
s1.display()

Output:

Name: Rahul
Class: 9

How does it work?

• class Student: defines a class.

• __init__() runs automatically when a new object is initialised.

• name and class_name are values supplied when the object is created.

• self.name and self.class_name store those values in the object.

• s1.display() displays the stored information.

Important: Unlike some other programming languages, Python does not support multiple constructors simply by defining several __init__() methods in the same class. The last definition replaces earlier definitions. Optional arguments and class methods are common ways to support alternative creation patterns.

2. Understanding self in Python

What is self?

self refers to the current object on which an instance method is operating.

Imagine a classroom with 30 students. Every student has a name, but each student has a different name. Python needs a way to know which student's information is being accessed.

That is where self helps.

Example

class Student:
    def __init__(self, name):
        self.name = name

    def introduce(self):
        print("My name is", self.name)


s1 = Student("Aman")
s2 = Student("Priya")

s1.introduce()
s2.introduce()

Output:

My name is Aman
My name is Priya

When s1.introduce() is called, self refers to s1.

When s2.introduce() is called, self refers to s2.

Therefore, the same method can work with different objects.

Is self a Python keyword?

No. self is a naming convention, not a reserved keyword. However, Python programmers almost always use this name for the first parameter of an instance method.

You normally do not pass it explicitly. Python supplies the object automatically when you call a method through an instance.

3. Instance Variables vs Class Variables

Variables in a class can belong to individual objects or be shared by all objects of that class.

Understanding this difference is essential for writing correct OOP programs.

Instance variables

Instance variables store information specific to an individual object.

For example, each student has a different name and roll number.

Class variables

Class variables are defined directly inside the class, outside its instance methods. They are shared through the class unless an object creates its own attribute with the same name.

For example, all students in a particular school might share the same school name.

Example

class Student:
    school = "ABC Public School"  # Class variable

    def __init__(self, name, roll_no):
        self.name = name           # Instance variable
        self.roll_no = roll_no     # Instance variable


s1 = Student("Aman", 101)
s2 = Student("Priya", 102)

print(s1.name)
print(s2.name)

print(s1.school)
print(s2.school)
print(Student.school)

Output:

Aman
Priya
ABC Public School
ABC Public School
ABC Public School

Difference between instance and class variables

Feature	Instance variable	Class variable
Belongs to	An individual object	The class
Typical definition	self.name	school = "ABC"
Values	Can differ between objects	Shared through the class
Access	s1.name	Student.school

Important point

If you write:

s1.school = "XYZ School"

you create or update an attribute on s1; you do not change Student.school or the value seen through other objects that have not overridden the attribute.

To change the shared class variable, use:

Student.school = "XYZ School"

Use class variables for genuinely shared information, not for mutable data that should be independent for each object.

4. Instance Methods

An instance method operates on a particular object. Its first parameter is conventionally named self.

Instance methods can access or modify instance variables and can also use class-level information.

Example: A Bank Account

class BankAccount:
    def __init__(self, owner, balance):
        self.owner = owner
        self.balance = balance

    def deposit(self, amount):
        self.balance += amount

    def show_balance(self):
        print("Account holder:", self.owner)
        print("Balance:", self.balance)


account = BankAccount("Rahul", 5000)

account.deposit(1500)
account.show_balance()

Output:

Account holder: Rahul
Balance: 6500

Explanation

• deposit() modifies the balance of the particular account.

• show_balance() displays information about that account.

• Both methods use self to access the object's attributes.

If another bank account is created, its balance remains independent.

When should you use instance methods?

Use them whenever an operation depends on the data of a specific object, such as withdrawing money from an account, calculating a student's marks, or moving a game character.

5. Class Methods

A class method works with the class rather than a particular object's state.

It uses the @classmethod decorator, and its first parameter is conventionally named cls. This parameter refers to the class on which the method is called.

Example

class Student:
    school = "ABC Public School"

    def __init__(self, name):
        self.name = name

    @classmethod
    def change_school(cls, new_school):
        cls.school = new_school


s1 = Student("Aman")
s2 = Student("Priya")

Student.change_school("Delhi Public School")

print(s1.school)
print(s2.school)

Output:

Delhi Public School
Delhi Public School

Explanation

The method change_school() changes the shared class variable.

The cls parameter refers to the class, so cls.school accesses the class attribute.

A useful application: Alternative object creation

Class methods can also create objects using alternative input formats.

class Student:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    @classmethod
    def from_string(cls, data):
        name, age = data.split(",")
        return cls(name, int(age))


s1 = Student.from_string("Aman,15")

print(s1.name)
print(s1.age)

Output:

Aman
15

Here, from_string() acts as an alternative way to create a student object.

When should you use class methods?

Use them to work with class-level data or provide alternative ways of creating objects.

6. Static Methods

A static method is a function placed inside a class because it is logically related to that class.

It uses the @staticmethod decorator.

Unlike instance methods and class methods, a static method does not automatically receive self or cls.

Example: Checking Eligibility

class Student:
    @staticmethod
    def is_eligible(age):
        return age >= 14


print(Student.is_eligible(15))
print(Student.is_eligible(12))

Output:

True
False

Explanation

The method checks whether an age meets a condition.

It does not need to access any student object or class variable. Therefore, a static method is suitable.

Instance method vs class method vs static method

Feature	Instance method	Class method	Static method
Decorator	None required	@classmethod	@staticmethod
First parameter	self	cls	No automatic parameter
Main purpose	Work with an object	Work with the class	Related utility operation
Access to object state	Through self	Not automatically	Not automatically

Remember this simple rule:

• Instance method: Works with an object.

• Class method: Works with the class.

• Static method: Performs a related operation without automatically receiving the object or class.

7. Method Overriding

Method overriding occurs when a child class provides its own implementation of a method inherited from its parent class.

It is an important part of runtime polymorphism.

Real-world example

Consider a school application that calculates the way different types of students receive awards.

The basic student class can have a method called award(). A sports student and an academic student can override that method to provide different behaviour.

Example

class Student:
    def award(self):
        print("Student receives a certificate.")


class SportsStudent(Student):
    def award(self):
        print("Student receives a sports trophy.")


class AcademicStudent(Student):
    def award(self):
        print("Student receives an academic medal.")


s1 = SportsStudent()
s2 = AcademicStudent()

s1.award()
s2.award()

Output:

Student receives a sports trophy.
Student receives an academic medal.

Explanation

Both child classes inherit from Student, but each provides its own version of award().

When the method is called, Python uses the implementation appropriate to the object's class.

Why is method overriding useful?

It allows related classes to share a common interface while implementing behaviour differently.

You can use the same method name for different payment methods, vehicles, reports, or employee types.

8. Using super() in Python

The super() function provides access to methods defined in the next class in Python's method resolution order (MRO).

It is commonly used in a child class to call a parent class's implementation.

Example

class Person:
    def __init__(self, name):
        self.name = name

    def display(self):
        print("Name:", self.name)


class Student(Person):
    def __init__(self, name, roll_no):
        super().__init__(name)
        self.roll_no = roll_no

    def display(self):
        super().display()
        print("Roll number:", self.roll_no)


s1 = Student("Aman", 101)
s1.display()

Output:

Name: Aman
Roll number: 101

What happens here?

1. Student inherits from Person.

2. super().__init__(name) calls the next implementation of __init__() in the method resolution order.

3. The parent's initialisation code sets self.name.

4. The child class sets self.roll_no.

5. super().display() calls the inherited implementation before displaying the roll number.

Without super(), you might duplicate code from the parent class.

Does super() always mean "call my parent"?

In simple single inheritance, this description is often sufficient. More precisely, super() follows the method resolution order. This is especially important when working with multiple inheritance.

Best practice: When extending an inherited method, use super() where appropriate rather than unnecessarily repeating the parent class's code.

9. Abstract Classes in Python

An abstract class defines a common structure that its subclasses are expected to implement.

Python supports abstract classes through the abc module.

An abstract class can contain ordinary methods as well as abstract methods. An abstract method declares behaviour that concrete subclasses must provide before they can be instantiated.

Example: Different Payment Methods

Suppose an online shopping application supports card payments and UPI payments.

Both payment types should have a pay() method, but their implementations are different.

from abc import ABC, abstractmethod


class Payment(ABC):
    @abstractmethod
    def pay(self, amount):
        pass


class CardPayment(Payment):
    def pay(self, amount):
        print("Paid", amount, "using card")


class UPIPayment(Payment):
    def pay(self, amount):
        print("Paid", amount, "using UPI")


p1 = CardPayment()
p2 = UPIPayment()

p1.pay(1000)
p2.pay(500)

Output:

Paid 1000 using card
Paid 500 using UPI

What does ABC mean?

ABC stands for Abstract Base Class.

The @abstractmethod decorator marks a method as abstract.

A class that still has unimplemented abstract methods cannot normally be instantiated.

For example:

payment = Payment()

This raises a TypeError because Payment has an unimplemented abstract method.

Why are abstract classes useful?

They help enforce a common interface across related classes.

For example, every payment type in an application can be required to implement pay(). This makes the application easier to extend and maintain.

10. Composition in Python

Composition describes a strong whole-part relationship in which one object owns or manages another object's lifecycle as part of its design.

Consider a computer. It contains components such as a processor. A computer object can create and manage its processor object.

Example

class Processor:
    def start(self):
        print("Processor started")


class Computer:
    def __init__(self):
        self.processor = Processor()

    def start_computer(self):
        self.processor.start()
        print("Computer started")


computer = Computer()
computer.start_computer()

Output:

Processor started
Computer started

Explanation

• Processor is a separate class.

• Computer creates a Processor object during initialisation.

• The computer uses that processor to perform its operation.

The processor is created and managed internally in this example, illustrating a simple form of composition.

When is composition useful?

Composition is useful when a class needs the services of other objects.

Examples include:

• A car containing an engine object.

• A shopping cart managing cart-item objects.

• A computer using processor and memory objects.

Composition helps us build complex applications by combining smaller, reusable classes.

Important: Composition is a design relationship, not a special Python keyword. The exact strength of ownership depends on how the application creates, shares, and manages its objects.

11. Association in Python

Association is a relationship between two objects that interact with each other.

Neither object necessarily owns the other.

Consider a teacher and a student. A teacher teaches a student, but the teacher does not own the student, and both objects can exist independently.

Example

class Teacher:
    def __init__(self, name):
        self.name = name

    def teach(self, student):
        print(self.name, "is teaching", student.name)


class Student:
    def __init__(self, name):
        self.name = name


teacher = Teacher("Mr Sharma")
student = Student("Aman")

teacher.teach(student)

Output:

Mr Sharma is teaching Aman

Explanation

The teach() method receives a Student object as an argument.

The teacher interacts with the student, but the teacher does not create or own that student.

Both objects are created independently.

Where is association used?

• A doctor treating a patient.

• A teacher teaching a student.

• A customer interacting with a bank employee.

• A driver driving a vehicle.

Association represents interaction or a connection between objects.

12. Aggregation in Python

Aggregation is a specialised form of association that represents a whole-part relationship in which the parts can exist independently of the whole.

Consider a department and its teachers. A department has teachers, but a teacher can exist independently and may be associated with another department later.

Example

class Teacher:
    def __init__(self, name):
        self.name = name


class Department:
    def __init__(self, name, teachers):
        self.name = name
        self.teachers = teachers

    def show_teachers(self):
        print("Department:", self.name)

        for teacher in self.teachers:
            print(teacher.name)


t1 = Teacher("Mr Sharma")
t2 = Teacher("Ms Verma")

teachers = [t1, t2]

department = Department("Computer Science", teachers)
department.show_teachers()

Output:

Department: Computer Science
Mr Sharma
Ms Verma

Explanation

• The teacher objects are created independently.

• The department receives a list containing existing teacher objects.

• The department refers to those objects but does not create them itself.

• The teachers can continue to exist even if the department object is no longer used.

This illustrates aggregation.

Composition vs Association vs Aggregation

Concept	Relationship	Object independence	Example
Association	Objects interact	Both can exist independently	Teacher and student
Aggregation	Weak whole-part relationship	Parts can exist independently	Department and teachers
Composition	Strong whole-part ownership	Parts are managed as components of the whole	Computer and its internally created processor

Remember: Python does not have separate syntax for association, aggregation, and composition. These are object-oriented design concepts. The relationship depends on how objects are created, owned, shared, and managed.

13. Mini Project: Student Management System

Now let's combine several of the concepts we have learned into one small project.

This program demonstrates:

• A constructor using __init__().

• self and instance variables.

• A class variable.

• Instance methods.

• A class method.

• A static method.

• Inheritance and method overriding.

• super().

Complete Python program

class Student:
    school = "ABC Public School"

    def __init__(self, name, marks):
        self.name = name
        self.marks = marks

    def display(self):
        print("Name:", self.name)
        print("Marks:", self.marks)
        print("School:", self.school)

    @classmethod
    def change_school(cls, new_school):
        cls.school = new_school

    @staticmethod
    def is_pass(marks):
        return marks >= 33


class SportsStudent(Student):
    def __init__(self, name, marks, sport):
        super().__init__(name, marks)
        self.sport = sport

    def display(self):
        super().display()
        print("Sport:", self.sport)


student = Student("Aman", 78)
sports_student = SportsStudent("Priya", 85, "Basketball")

student.display()
print("Pass:", Student.is_pass(student.marks))

print()

sports_student.display()

print()
Student.change_school("Delhi Public School")
print("Updated school:", student.school)

Expected output

Name: Aman
Marks: 78
School: ABC Public School
Pass: True

Name: Priya
Marks: 85
School: ABC Public School
Sport: Basketball

Updated school: Delhi Public School

What did we learn from the project?

1. The constructor initialises student objects.

2. self identifies the object whose details are being accessed.

3. name, marks, and sport are instance variables.

4. school is a class variable.

5. display() is an instance method.

6. change_school() is a class method.

7. is_pass() is a static method.

8. SportsStudent inherits from Student.

9. The child class overrides display().

10. super() reuses the parent's initialisation and display behaviour.

This is how different OOP concepts work together in a real program.

---

Practice Questions

Test your understanding with the following questions.

Beginner Level

Q1. What is the purpose of __init__() in Python?

Q2. What does self represent in an instance method?

Q3. Identify the instance variable and class variable:

class Employee:
    company = "Tech Solutions"

    def __init__(self, name):
        self.name = name

Q4. Which decorator is used to define a class method?

A. @static
B. @classmethod
C. @abstract
D. @instance

Intermediate Level

Q5. What is the difference between an instance method and a static method?

Q6. What is method overriding? Explain with an example.

Q7. Why do we use super() in inheritance?

Q8. Can an abstract class contain a normal method as well as an abstract method?

Q9. What is the difference between composition and aggregation?

Programming Challenges

Q10. Create a Book class with a constructor that stores the title, author, and price. Write a method to display these details.

Q11. Create an Employee class with a class variable company. Add a class method that changes the company name.

Q12. Create a Vehicle class with a method called start(). Create a Car child class that overrides start().

Q13. Create an abstract class called Shape with an abstract method area(). Implement it in Rectangle and Circle.

Q14. Create a Department class that stores a list of existing Teacher objects. Explain why this can be considered aggregation.

---

Conclusion

Python OOP is much more than creating classes and objects. Understanding constructors, self, instance and class variables, different types of methods, inheritance, method overriding, and super() helps you design programs that are easier to extend and maintain.

Abstract classes help define common interfaces, while association, aggregation, and composition help us model relationships between objects.

Once you understand these concepts, you can use them to develop practical projects such as student management systems, banking applications, inventory systems, and games.

Keep practising Python, experiment with the examples, and build your own projects. The best way to master OOP is to write code and understand how objects work together!

Further Reading

Explore our other Python Pebbles tutorials on:

• Python Classes and Objects

• Python Inheritance

• Python Encapsulation

• Python Polymorphism

• Python Functions and Modules

Suggested next tutorial: Python OOP Project – Build a Student Management System Using Classes, Inheritance, and File Handling.

---

About Python Pebbles

Python Pebbles helps students and beginners learn Python programming through simple explanations, practical examples, exercises, and hands-on projects. Keep exploring, keep coding, and take one small step towards mastering Python every day.

Python Algorithms

 

Python Algorithms for Beginners – Searching, Sorting and Essential Problem-Solving Techniques

Learn Linear Search, Binary Search, Sorting Algorithms, Frequency Counting, Prime Numbers, Fibonacci, GCD, LCM, Palindromes and Anagrams with Python

Have you ever wondered how a computer finds a name in a list of thousands of students, arranges marks from highest to lowest, or checks whether a number is prime?

The secret lies in algorithms!

In this Python Pebbles tutorial, we will explore some of the most useful algorithms that every Class 9–12 student should understand. You will learn not only how to write the code but also how to think like a programmer.

1. What Is an Algorithm?

An algorithm is a step-by-step procedure used to solve a problem.

Think of an algorithm like a recipe. A recipe explains how to prepare a dish step by step. Similarly, an algorithm explains how to solve a programming problem step by step.

Example: Finding the Largest Number

Suppose we have these numbers:

numbers = [12, 45, 7, 89, 34]

We want to find the largest number.

Our algorithm is:

1. Assume the first number is the largest.

2. Compare it with every other number.

3. If a larger number is found, update the largest value.

4. Display the result.

Python program:

numbers = [12, 45, 7, 89, 34]

largest = numbers[0]

for number in numbers:
    if number > largest:
        largest = number

print("Largest number:", largest)

Output:

Largest number: 89

Python Pebble: Before writing code, explain the solution in simple steps. This makes programming easier and helps you find mistakes.

---

Part 1: Searching Algorithms

Searching means finding whether a particular value exists in a collection and, if it does, where it is located.

Imagine looking for your name in a class attendance list. The method you use depends on how the list is organized.

2. Linear Search

Linear Search checks each element one by one until the target is found or the list ends.

It works on both sorted and unsorted lists.

Example

numbers = [15, 28, 7, 42, 19]
target = 42

found = False

for i in range(len(numbers)):
    if numbers[i] == target:
        print("Found at index:", i)
        found = True
        break

if not found:
    print("Number not found")

Output:

Found at index: 3

Remember that Python list indexing starts from 0.

How does it work?

For the list [15, 28, 7, 42, 19], searching for 42 follows these steps:

Step	Value checked	Result
1	15	Not found
2	28	Not found
3	7	Not found
4	42	Found!

Linear Search Using a Function

def linear_search(numbers, target):
    for i in range(len(numbers)):
        if numbers[i] == target:
            return i
    return -1

data = [10, 20, 30, 40, 50]

print(linear_search(data, 30))
print(linear_search(data, 90))

Output:

2
-1

Here, -1 indicates that the target was not found.

Time complexity: $O(n)$ in the worst case, because every element may need to be checked.

When should you use Linear Search?

• When the list is small.

• When the data is not sorted.

• When you need a simple search method.

3. Binary Search

Binary Search is a faster searching algorithm, but it requires the list to be sorted.

Instead of checking every element, it repeatedly divides the search area into two halves.

Imagine searching for a word in a dictionary. You would open the dictionary near the middle rather than reading every word from the beginning.

Example

Consider this sorted list:

numbers = [10, 20, 30, 40, 50, 60, 70]

We want to find 60.

1. Check the middle element: 40.

2. Since 60 is greater than 40, ignore the left half.

3. Check the middle of the remaining section.

4. Find 60.

Python Program

def binary_search(numbers, target):
    low = 0
    high = len(numbers) - 1

    while low <= high:
        mid = (low + high) // 2

        if numbers[mid] == target:
            return mid
        elif numbers[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

data = [10, 20, 30, 40, 50, 60, 70]

print(binary_search(data, 60))
print(binary_search(data, 25))

Output:

5
-1

Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Data must be sorted?	No	Yes
Basic method	Check one by one	Divide the search range
Worst-case time	$O(n)$	$O(\log n)$
Best suited for	Small or unsorted data	Large, sorted data

Python Pebble: Binary Search is powerful because each step removes approximately half of the remaining search area.

---

Part 2: Sorting Algorithms

Sorting means arranging data in a particular order, such as ascending or descending.

For example:

Before sorting: [45, 12, 89, 23, 7]
After sorting:  [7, 12, 23, 45, 89]

Let's explore three classic sorting algorithms.

4. Bubble Sort

Bubble Sort compares adjacent elements and swaps them if they are in the wrong order.

After each complete pass through the list, the largest unsorted element moves to its correct position at the end.

Example

numbers = [5, 3, 8, 2]

for i in range(len(numbers)):
    for j in range(0, len(numbers) - i - 1):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = (
                numbers[j + 1], numbers[j]
            )

print(numbers)

Output:

[2, 3, 5, 8]

Understanding the First Pass

Starting list:

[5, 3, 8, 2]

Compare 5 and 3, then swap:

[3, 5, 8, 2]

Compare 5 and 8. No swap is needed.

Compare 8 and 2, then swap:

[3, 5, 2, 8]

The largest value, 8, has moved to the end.

Optimized Bubble Sort

We can stop early if a complete pass makes no swaps.

def bubble_sort(numbers):
    n = len(numbers)

    for i in range(n):
        swapped = False

        for j in range(n - i - 1):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = (
                    numbers[j + 1], numbers[j]
                )
                swapped = True

        if not swapped:
            break

    return numbers

print(bubble_sort([9, 4, 6, 2, 1]))

Output:

[1, 2, 4, 6, 9]

Worst-case time complexity: $O(n^2)$.

Use Bubble Sort to learn how comparisons, loops, and swaps work. For large real-world lists, Python's built-in sorting is generally a better choice.

5. Selection Sort

Selection Sort repeatedly finds the smallest element in the unsorted part of the list and places it at the beginning of that part.

Example

numbers = [29, 10, 14, 37, 13]

for i in range(len(numbers)):
    min_index = i

    for j in range(i + 1, len(numbers)):
        if numbers[j] < numbers[min_index]:
            min_index = j

    numbers[i], numbers[min_index] = (
        numbers[min_index], numbers[i]
    )

print(numbers)

Output:

[10, 13, 14, 29, 37]

How does it work?

• Find the smallest number in the entire list.

• Place it at index 0.

• Find the smallest number in the remaining unsorted section.

• Place it at index 1.

• Repeat until the list is sorted.

Worst-case time complexity: $O(n^2)$.

Key idea: Selection Sort selects the smallest remaining element on every pass.

6. Insertion Sort

Insertion Sort builds a sorted section one element at a time.

Think about arranging playing cards in your hand. You pick up one card and insert it into the correct position among the cards you are already holding.

Python Program

numbers = [8, 4, 6, 2, 5]

for i in range(1, len(numbers)):
    key = numbers[i]
    j = i - 1

    while j >= 0 and numbers[j] > key:
        numbers[j + 1] = numbers[j]
        j -= 1

    numbers[j + 1] = key

print(numbers)

Output:

[2, 4, 5, 6, 8]

How does it work?

1. Treat the first element as sorted.

2. Pick the next element as key.

3. Move larger elements one position to the right.

4. Insert the key into the empty position.

5. Continue until every element is processed.

Time complexity:

• Best case: $O(n)$, when the list is already sorted.

• Worst case: $O(n^2)$, when the list is in reverse order.

Compare the Three Sorting Algorithms

Algorithm	Main idea	Worst-case time
Bubble Sort	Swap adjacent elements	$O(n^2)$
Selection Sort	Select the smallest remaining value	$O(n^2)$
Insertion Sort	Insert each value into the sorted section	$O(n^2)$

7. Python's Built-in sort()

You do not always need to write a sorting algorithm yourself. Python provides a highly optimized sorting method.

The sort() method changes the original list.

marks = [78, 92, 65, 88, 71]

marks.sort()

print(marks)

Output:

[65, 71, 78, 88, 92]

Sorting in Descending Order

marks = [78, 92, 65, 88, 71]

marks.sort(reverse=True)

print(marks)

Output:

[92, 88, 78, 71, 65]

8. Python's sorted() Function

The sorted() function returns a new sorted list and leaves the original collection unchanged.

numbers = [40, 10, 30, 20]

result = sorted(numbers)

print("Original:", numbers)
print("Sorted:", result)

Output:

Original: [40, 10, 30, 20]
Sorted: [10, 20, 30, 40]

Difference Between sort() and sorted()

Feature	sort()	sorted()
Type	List method	Built-in function
Changes original list?	Yes	No
Returns	None	A new sorted list
Works with tuples?	No, not as a tuple method	Yes

9. Custom Sorting

Sometimes we want to sort data according to a special rule.

For example, suppose we have student names and marks. We want to sort the students by marks in descending order.

students = [
    ("Aman", 85),
    ("Riya", 92),
    ("Karan", 78),
    ("Meena", 92)
]

students.sort(key=lambda student: student[1], reverse=True)

print(students)

Output:

[('Riya', 92), ('Meena', 92), ('Aman', 85), ('Karan', 78)]

Here:

• student[0] represents the student's name.

• student[1] represents the student's marks.

• key=lambda student: student[1] tells Python to sort using marks.

Sorting by Name

students = [
    ("Aman", 85),
    ("Riya", 92),
    ("Karan", 78)
]

result = sorted(students, key=lambda student: student[0])

print(result)

Output:

[('Aman', 85), ('Karan', 78), ('Riya', 92)]

Python Pebble: Custom sorting is useful when working with student records, product prices, employee details, and competition results.

---

Part 3: Common Algorithms Every Student Should Know

10. Finding the Maximum and Minimum

Python provides max() and min() for finding the largest and smallest values.

numbers = [45, 12, 89, 23, 7]

print("Maximum:", max(numbers))
print("Minimum:", min(numbers))

Output:

Maximum: 89
Minimum: 7

Find Them Without Built-in Functions

numbers = [45, 12, 89, 23, 7]

largest = numbers[0]
smallest = numbers[0]

for number in numbers:
    if number > largest:
        largest = number

    if number < smallest:
        smallest = number

print("Maximum:", largest)
print("Minimum:", smallest)

Output:

Maximum: 89
Minimum: 7

This approach helps you understand how algorithms work internally.

11. Finding Sum and Average

The sum is the total of all values. The average is the sum divided by the number of values.

$$\text{Average}=\frac{\text{Sum of values}}{\text{Number of values}}$$

Python Program

marks = [80, 75, 90, 85, 70]

total = 0

for mark in marks:
    total += mark

average = total / len(marks)

print("Total:", total)
print("Average:", average)

Output:

Total: 400
Average: 80.0

Python also provides sum():

marks = [80, 75, 90, 85, 70]

print(sum(marks))
print(sum(marks) / len(marks))

Output:

400
80.0

Always check that a list is not empty before calculating its average, because division by zero is not allowed.

12. Frequency Counting

Frequency counting tells us how many times each value appears in a collection.

Suppose we want to count the votes received by candidates.

votes = ["A", "B", "A", "C", "B", "A"]

frequency = {}

for vote in votes:
    if vote in frequency:
        frequency[vote] += 1
    else:
        frequency[vote] = 1

print(frequency)

Output:

{'A': 3, 'B': 2, 'C': 1}

A Shorter Method Using Counter

from collections import Counter

votes = ["A", "B", "A", "C", "B", "A"]

frequency = Counter(votes)

print(frequency)
print(frequency["A"])

Output:

Counter({'A': 3, 'B': 2, 'C': 1})
3

Where is frequency counting useful?

• Counting votes.

• Counting words in an article.

• Analyzing examination scores.

• Finding the most common item in a dataset.

13. Duplicate Detection

A duplicate is a value that appears more than once.

Example

numbers = [10, 20, 30, 20, 40, 10, 50]

seen = set()
duplicates = set()

for number in numbers:
    if number in seen:
        duplicates.add(number)
    else:
        seen.add(number)

print("Duplicates:", sorted(duplicates))

Output:

Duplicates: [10, 20]

How does it work?

• seen stores values that have already appeared.

• If a value appears again, it is added to duplicates.

• A set stores each distinct value only once.

For typical integer or string data, set membership checks are $O(1)$ on average, so this is generally efficient.

14. Checking Prime Numbers

A prime number is a whole number greater than 1 that has exactly two positive divisors: 1 and itself.

Examples: 2, 3, 5, 7, 11, 13

Numbers such as 4, 6, 8, 9, 10 are not prime.

Python Program

def is_prime(n):
    if n < 2:
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

    return True

print(is_prime(17))
print(is_prime(21))

Output:

True
False

Why do we check only up to the square root?

If a number has a factor greater than its square root, it must also have a corresponding factor smaller than its square root. Therefore, if no divisor is found up to the square root, the number is prime.

Python Pebble: The % operator gives the remainder. If n % i == 0, then i divides n exactly.

15. Generating Fibonacci Numbers

The Fibonacci sequence is a sequence in which each new number is the sum of the previous two numbers.

A common starting sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Python Program

n = 10

a = 0
b = 1

for i in range(n):
    print(a, end=" ")
    a, b = b, a + b

Output:

0 1 1 2 3 5 8 13 21 34

Understanding the Update

a, b = b, a + b

Python evaluates the right-hand side first, then assigns both values together.

This means:

• The new a becomes the old b.

• The new b becomes the sum of the old a and b.

This iterative approach avoids the repeated work of a simple recursive Fibonacci program.

16. Calculating Factorial

The factorial of a non-negative integer is the product of all positive integers up to that number.

It is represented by an exclamation mark.

$$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$

By definition, $0! = 1$.

Python Program

n = 5
factorial = 1

for i in range(1, n + 1):
    factorial *= i

print("Factorial:", factorial)

Output:

Factorial: 120

Factorial Using a Function

def factorial(n):
    if n < 0:
        return None

    result = 1

    for i in range(1, n + 1):
        result *= i

    return result

print(factorial(5))
print(factorial(0))
print(factorial(-2))

Output:

120
1
None

The function returns None for negative input because factorial is not defined for negative integers in this context.

17. Finding GCD and LCM

What is GCD?

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both of them exactly.

For example, the GCD of 12 and 18 is 6.

What is LCM?

The Least Common Multiple (LCM) of two positive integers is the smallest positive integer divisible by both.

For example, the LCM of 12 and 18 is 36.

GCD Using Euclid's Algorithm

Euclid's algorithm repeatedly replaces a pair of numbers with the smaller number and their remainder until the remainder becomes zero.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b

    return abs(a)

print(gcd(12, 18))
print(gcd(48, 18))

Output:

6
6

LCM Using GCD

For positive integers $a$ and $b$:

$$\text{LCM}(a,b)=\frac{a \times b}{\text{GCD}(a,b)}$$

A Python implementation is:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

def lcm(a, b):
    if a == 0 or b == 0:
        return 0

    return abs((a // gcd(a, b)) * b)

print("GCD:", gcd(12, 18))
print("LCM:", lcm(12, 18))

Output:

GCD: 6
LCM: 36

Python also provides math.gcd() and, in modern Python versions, math.lcm().

18. Checking Palindromes

A palindrome is a word, number, or sequence that reads the same forward and backward.

Examples:

• madam

• level

• 121

• 1331

Python Program

text = "madam"

if text == text[::-1]:
    print("Palindrome")
else:
    print("Not a palindrome")

Output:

Palindrome

The expression text[::-1] creates a reversed copy of the string.

Palindrome Function

def is_palindrome(text):
    text = text.lower()
    return text == text[::-1]

print(is_palindrome("Madam"))
print(is_palindrome("Python"))

Output:

True
False

This version ignores letter case but not spaces or punctuation.

Challenge: Ignore Spaces and Punctuation

Can you modify the function so that a phrase such as "A man, a plan, a canal: Panama" is recognized as a palindrome?

Hint: Keep only alphanumeric characters using str.isalnum() before comparing the text with its reverse.

19. Checking Anagrams

Two words are anagrams if they contain exactly the same letters with the same frequencies, but in a different order.

Examples:

• listen and silent

• earth and heart

• race and care

Python Program

def are_anagrams(word1, word2):
    word1 = word1.replace(" ", "").lower()
    word2 = word2.replace(" ", "").lower()

    return sorted(word1) == sorted(word2)

print(are_anagrams("listen", "silent"))
print(are_anagrams("hello", "world"))

Output:

True
False

The program:

1. Converts both words to lowercase.

2. Removes spaces.

3. Sorts the characters in each word.

4. Compares the sorted results.

Anagram Detection Using Frequency Counting

from collections import Counter

def are_anagrams(word1, word2):
    word1 = word1.replace(" ", "").lower()
    word2 = word2.replace(" ", "").lower()

    return Counter(word1) == Counter(word2)

print(are_anagrams("earth", "heart"))

Output:

True

Frequency counting avoids sorting and is often a convenient way to compare character counts.

---

Part 4: Understanding Algorithm Efficiency

A program can produce the correct answer and still be inefficient when given a large amount of data.

Time complexity describes how the work performed by an algorithm grows as the input size increases.

Here is a beginner-friendly reference table.

Complexity	Common example	General interpretation
$O(1)$	Access a list element by index	Constant-time operation
$O(\log n)$	Binary Search	Grows slowly
$O(n)$	Linear Search	Work grows roughly with input size
$O(n\log n)$	Efficient general-purpose sorting	Scales well for many large lists
$O(n^2)$	Basic Bubble Sort	Can become slow as input grows

These are typical complexity descriptions; actual performance also depends on the data, implementation, and execution environment.

Why does it matter?

Suppose you have one million sorted numbers.

• Linear Search may need to inspect up to one million elements.

• Binary Search needs roughly 20 comparisons in the worst case for a list of that size.

That is why choosing the right algorithm matters.

---

Part 5: Mini-Projects for Practice

Project 1: Student Marks Analyzer

Goal: Analyze the marks of students in a class.

Your program should:

1. Store marks in a list.

2. Calculate the maximum and minimum marks.

3. Calculate the total and average.

4. Sort the marks in descending order.

5. Count how many students scored above 75.

6. Search for a particular mark.

Starter code:

marks = [78, 92, 65, 88, 92, 71, 56, 85]

print("Highest:", max(marks))
print("Lowest:", min(marks))
print("Average:", sum(marks) / len(marks))

print("Descending order:", sorted(marks, reverse=True))

above_75 = 0

for mark in marks:
    if mark > 75:
        above_75 += 1

print("Students scoring above 75:", above_75)

Expected output:

Highest: 92
Lowest: 56
Average: 78.375
Descending order: [92, 92, 88, 85, 78, 71, 65, 56]
Students scoring above 75: 5

Extension: Ask the user to enter a mark and use Binary Search to find it in a sorted list.

Project 2: Number Toolkit

Create a menu-driven program that allows a user to:

1. Check whether a number is prime.

2. Calculate factorial.

3. Generate Fibonacci numbers.

4. Check whether a number is a palindrome.

5. Find the GCD and LCM of two numbers.

Extension: Validate the user's input and allow the program to continue until the user selects Exit.

Project 3: Word Analyzer

Write a program that accepts a sentence and:

• Counts the frequency of each word.

• Identifies repeated words.

• Finds the longest word.

• Checks whether two entered words are anagrams.

• Checks whether the sentence is a palindrome after ignoring spaces and punctuation.

Extension: Display the five most frequently used words.

---

Part 6: Practice Questions

Try these questions before looking for solutions.

A. Conceptual Questions

1. What is an algorithm? Give one real-life example.

2. Why must the input list be sorted before applying Binary Search?

3. What is the main difference between Bubble Sort and Selection Sort?

4. What is the difference between list.sort() and sorted(list)?

5. What does $O(n)$ mean?

6. Why does Binary Search generally outperform Linear Search on large, sorted lists?

7. What is the purpose of the key parameter in Python's sorting functions?

8. Why is a set useful for detecting duplicates?

B. Programming Challenges

9. Write a Linear Search function that returns the index of the first occurrence of a target.

10. Implement Binary Search and test it with both present and absent values.

11. Write Bubble Sort to arrange a list in descending order.

12. Implement Selection Sort without using sort() or sorted().

13. Write Insertion Sort and count how many shifts are performed.

14. Sort a list of names alphabetically using sorted().

15. Sort student records by marks in descending order and use names alphabetically to break ties.

16. Find the second-largest distinct number in a list.

17. Count the frequency of each character in a string.

18. Identify all duplicate values in a list.

19. Print all prime numbers between 1 and 100.

20. Generate the first n Fibonacci numbers.

21. Calculate factorial using iteration.

22. Find the GCD and LCM of two numbers.

23. Check whether a phrase is a palindrome after ignoring case, spaces, and punctuation.

24. Check whether two phrases are anagrams after ignoring case and spaces.

25. Build a menu-driven program that combines at least five of the algorithms in this article.

---

Quick Revision: Algorithms Cheat Sheet

Problem	Useful approach
Search an unsorted list	Linear Search
Search a sorted list	Binary Search
Sort a list in Python	sort() or sorted()
Learn basic sorting logic	Bubble, Selection, Insertion Sort
Find maximum/minimum	max() / min() or a loop
Calculate total	sum() or accumulation
Count repeated values	Dictionary or Counter
Detect duplicates	Set
Test a prime number	Divisibility checks up to the square root
Generate Fibonacci numbers	Iterative updates
Calculate factorial	Multiplication loop
Find GCD	Euclid's algorithm
Find LCM	Use GCD
Check palindrome	Compare with reversed text
Check anagram	Compare sorted characters or frequencies

Final Thoughts

Algorithms are the foundation of problem-solving in programming. Once you understand how searching, sorting, counting, and number-based algorithms work, you will be better prepared to solve school programming questions, build useful projects, and explore more advanced topics such as data structures, competitive programming, and artificial intelligence.

Remember: Do not just memorize the code. Understand the steps, test different inputs, and try to improve your solution.

Your next Python Pebble challenge: Pick one algorithm from this tutorial, write it without looking at the example, test it on at least three inputs, and explain its logic in your own words.

Keep coding, keep experimenting, and keep collecting Python Pebbles!

Python Data Structures - Collections

 

Python Data Structures Beyond Basic Collections: Stack, Queue, Deque, Linked List, Searching and Sorting

Have you ever wondered how a browser remembers the pages you visited, how a printer manages multiple print requests, or how a shopping app sorts products by price?

These activities use ideas from data structures and algorithms.

In Python, you already know basic collections such as lists, tuples, sets, and dictionaries. But as programs become more advanced, you need to understand how to organize, access, search, and arrange data efficiently.

Welcome to this Python Pebbles tutorial, where we will explore six important topics for Class 9–12 students:

• Stack

• Queue

• Deque

• Linked list

• Searching algorithms

• Sorting algorithms

By the end, you will build a small Student Record Manager that uses searching and sorting.

---

1. What Is a Data Structure?

A data structure is a way of organizing and storing data so that a program can use it effectively.

Imagine your school library.

Books are not thrown randomly onto the floor. They are organized so that students and librarians can find them easily.

A computer program also needs a sensible way to organize information.

Examples:

Data Structure	Real-Life Example
Stack	A pile of plates
Queue	Students waiting in a line
Deque	A line where people can join or leave at either end
Linked list	A chain of connected links
Searching	Finding a student's roll number
Sorting	Arranging marks from lowest to highest

Python Pebble: Choosing the right way to organize data can make a program easier to understand and more efficient.

2. Stack – Last In, First Out (LIFO)

What is a Stack?

A stack is a data structure in which the last item added is the first item removed.

This rule is called LIFO — Last In, First Out.

Imagine placing three plates on top of one another.

       ┌───────────┐
       │  Plate C  │  ← Removed first
       ├───────────┤
       │  Plate B  │
       ├───────────┤
       │  Plate A  │
       └───────────┘

You normally remove Plate C first because it is on top.

Stacks are used in:

• Undo operations in text editors

• Browser history navigation

• Function calls

• Expression evaluation

• Backtracking problems

Stack Operations

Operation	Meaning
push	Add an item
pop	Remove the top item
peek	View the top item without removing it
is_empty	Check whether the stack is empty

Python lists can implement a simple stack.

Example 1: Creating a Stack

stack = []

stack.append("Book A")
stack.append("Book B")
stack.append("Book C")

print(stack)

Output:

['Book A', 'Book B', 'Book C']

Here, append() adds an item to the top of our stack.

Example 2: Removing an Item

stack = ["Book A", "Book B", "Book C"]

removed = stack.pop()

print("Removed:", removed)
print("Stack:", stack)

Output:

Removed: Book C
Stack: ['Book A', 'Book B']

The last item added is the first item removed.

Example 3: Complete Stack Program

stack = []

stack.append(10)
stack.append(20)
stack.append(30)

print("Stack:", stack)
print("Top item:", stack[-1])

removed = stack.pop()

print("Removed:", removed)
print("Updated stack:", stack)

Output:

Stack: [10, 20, 30]
Top item: 30
Removed: 30
Updated stack: [10, 20]

Notice that stack[-1] accesses the last element without removing it.

Mini Challenge 1

Create a stack of five subject names.

1. Add five subjects.

2. Display the stack.

3. Remove two subjects.

4. Display the updated stack.

Bonus: Print the last subject without removing it.

---

3. Queue – First In, First Out (FIFO)

What Is a Queue?

A queue is a data structure in which the first item added is the first item removed.

This rule is called FIFO — First In, First Out.

Imagine students waiting at a school canteen.

Front                         Rear
  ↓                             ↓
[Riya] → [Aman] → [Neha] → [Raman]
  ↑
Served first

Riya joined the line first, so she is served first.

Queues are used in:

• Printer job management

• Customer service systems

• Task scheduling

• Network message processing

• Breadth-first search in graphs

Queue Operations

Operation	Meaning
enqueue	Add an item at the rear
dequeue	Remove an item from the front
front	View the first item
is_empty	Check whether the queue is empty

Example 1: A Simple Queue

A Python list can demonstrate a queue for small examples.

queue = []

queue.append("Riya")
queue.append("Aman")
queue.append("Neha")

print(queue)

Output:

['Riya', 'Aman', 'Neha']

To remove the first item:

served = queue.pop(0)

print("Served:", served)
print("Waiting:", queue)

Output:

Served: Riya
Waiting: ['Aman', 'Neha']

This works, but removing the first item from a large list can be inefficient because the remaining items need to shift.

Example 2: The Recommended Queue Using deque

Python provides a double-ended queue in the collections module.

from collections import deque

queue = deque()

queue.append("Riya")
queue.append("Aman")
queue.append("Neha")

print(queue)

served = queue.popleft()

print("Served:", served)
print("Waiting:", queue)

Output:

deque(['Riya', 'Aman', 'Neha'])
Served: Riya
Waiting: deque(['Aman', 'Neha'])

popleft() efficiently removes an item from the front.

Mini Challenge 2

Create a queue for a school office.

• Add three student names.

• Remove the first student after their work is completed.

• Add one more student.

• Display the queue.

Question: Why should the first student be removed rather than the last student?

---

4. Deque – Insert and Remove at Both Ends

What Is a Deque?

A deque, pronounced “deck,” stands for double-ended queue.

Unlike a standard queue, a deque allows items to be added or removed at both ends.

Imagine a line where people are allowed to enter or leave from either the front or the rear.

Python provides deque through the collections module.

from collections import deque

Important Deque Operations

Operation	Meaning
append(x)	Add x at the right end
appendleft(x)	Add x at the left end
pop()	Remove from the right end
popleft()	Remove from the left end

Example 1: Adding Items at Both Ends

from collections import deque

numbers = deque([20, 30])

numbers.append(40)
numbers.appendleft(10)

print(numbers)

Output:

deque([10, 20, 30, 40])

Example 2: Removing Items at Both Ends

from collections import deque

numbers = deque([10, 20, 30, 40])

print(numbers.pop())
print(numbers.popleft())

print(numbers)

Output:

40
10
deque([20, 30])

Where Are Deques Useful?

Deques are useful when a program needs to add and remove items at either end.

Examples include:

• Sliding-window algorithms

• Recent-item history

• Palindrome checking

• Certain scheduling algorithms

• Implementing stacks and queues

Mini Challenge 3: Palindrome Checker

A palindrome reads the same forwards and backwards.

Examples:

LEVEL
MADAM
RADAR

Try writing a program that:

1. Takes a word from the user.

2. Places its characters into a deque.

3. Compares and removes characters from both ends.

4. Reports whether the word is a palindrome.

Hint: Compare popleft() with pop() until zero or one character remains.

---

5. Linked List – An Introduction

What Is a Linked List?

A linked list is a data structure made of nodes.

Each node stores:

1. Data

2. A reference to the next node

Unlike a Python list, whose elements are stored in a sequence managed by Python, a linked list connects its nodes through references.

Imagine a treasure hunt.

Each clue contains a message and tells you where to find the next clue.

[10 | next] → [20 | next] → [30 | None]

Each box represents a node.

The final node points to None, which indicates that there is no next node.

Creating a Node in Python

We can use a class to define a node.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Here:

• data stores the value.

• next stores a reference to the next node.

• None means there is no next node yet.

Example 1: Connecting Three Nodes

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


first = Node(10)
second = Node(20)
third = Node(30)

first.next = second
second.next = third

print(first.data)
print(first.next.data)
print(first.next.next.data)

Output:

10
20
30

We have created three nodes and connected them.

Example 2: Traversing a Linked List

Traversing means visiting each node one by one.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


first = Node(10)
second = Node(20)
third = Node(30)

first.next = second
second.next = third

current = first

while current is not None:
    print(current.data)
    current = current.next

Output:

10
20
30

The variable current moves from one node to the next until it reaches None.

A Simple Linked List Class

Let's make our code reusable.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        current = self.head

        while current.next is not None:
            current = current.next

        current.next = new_node

    def display(self):
        current = self.head

        while current is not None:
            print(current.data, end=" -> ")
            current = current.next

        print("None")


numbers = LinkedList()

numbers.append(10)
numbers.append(20)
numbers.append(30)

numbers.display()

Output:

10 -> 20 -> 30 -> None

Linked List vs Python List

Feature	Python List	Singly Linked List
Access by index	Fast, typically O(1)	Requires traversal, O(n)
Add at beginning	Typically O(n)	O(1) if the head is updated
Add at end	Usually amortized O(1) with append()	O(n) in our implementation without a tail reference
Memory layout	Managed sequence of references	Nodes connected by references
Built into Python	Yes	Usually implemented manually for learning

Python Pebble: Linked lists are excellent for learning how nodes and references work. For everyday Python programming, built-in lists are often the simpler choice.

Mini Challenge 4

Extend the linked list program to:

1. Add the numbers 5, 15, 25, and 35.

2. Display all nodes.

3. Count how many nodes exist.

Bonus: Write a method that searches for a particular value.

---

6. Searching Algorithms

What Is Searching?

Searching means finding whether a particular item exists in a collection and, if needed, identifying its position.

Imagine looking for your name in a class register.

A computer can use different searching algorithms depending on how the data is organized.

We will learn:

• Linear search

• Binary search

6.1 Linear Search

Linear search checks each element one by one until the target is found or the collection ends.

It works on both sorted and unsorted collections.

Example

numbers = [15, 8, 23, 42, 16]

target = 42
found = False

for i in range(len(numbers)):
    if numbers[i] == target:
        print("Found at index:", i)
        found = True
        break

if not found:
    print("Not found")

Output:

Found at index: 3

Remember that Python indexes start at zero.

The first element is at index 0, the second at index 1, and so on.

Linear Search as a Function

def linear_search(items, target):
    for index, item in enumerate(items):
        if item == target:
            return index

    return -1


numbers = [15, 8, 23, 42, 16]

print(linear_search(numbers, 42))
print(linear_search(numbers, 100))

Output:

3
-1

Here, -1 means that the target was not found.

Time Complexity

In the worst case, linear search may inspect every element.

Its time complexity is O(n), where n is the number of elements.

---

6.2 Binary Search

Binary search is a faster searching method, but there is one important condition:

The data must be sorted.

Imagine finding a word in a dictionary. Instead of reading every word, you open near the middle and decide which half to search.

Binary search follows the same idea.

Example

Sorted list:

[10, 20, 30, 40, 50, 60, 70]

Suppose we want to find 60.

1. Check the middle element: 40.

2. Since 60 is greater than 40, ignore the left half.

3. Check the middle of the remaining section: 60.

4. The target is found.

Python Program

def binary_search(items, target):
    low = 0
    high = len(items) - 1

    while low <= high:
        mid = (low + high) // 2

        if items[mid] == target:
            return mid

        elif items[mid] < target:
            low = mid + 1

        else:
            high = mid - 1

    return -1


numbers = [10, 20, 30, 40, 50, 60, 70]

print(binary_search(numbers, 60))
print(binary_search(numbers, 25))

Output:

5
-1

Time Complexity

Binary search halves the remaining search area at each step.

Its time complexity is O(log n).

For large sorted collections, this can be much faster than linear search.

Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Requires sorted data	No	Yes
Method	Check items one by one	Repeatedly halve the search range
Worst-case time	O(n)	O(log n)
Best for	Small or unsorted data	Large, sorted data

Mini Challenge 5

Write a program that searches for a student's roll number in this list:

roll_numbers = [101, 105, 108, 112, 120, 125, 130]

First use linear search.

Then use binary search.

Question: Why must the list be sorted before using binary search?

---

7. Sorting Algorithms

What Is Sorting?

Sorting means arranging data in a particular order.

Examples:

• Marks from lowest to highest

• Prices from lowest to highest

• Names in alphabetical order

• Scores from highest to lowest

Python provides built-in sorting tools, but understanding sorting algorithms helps you learn how they work.

We will explore:

• Bubble sort

• Selection sort

• Insertion sort

• Python's built-in sorting

7.1 Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them when they are in the wrong order.

Think of larger values gradually moving towards the end of the list.

Example

Original list:

[5, 3, 8, 2]

First pass:

• Compare 5 and 3: swap.

• Compare 5 and 8: no swap.

• Compare 8 and 2: swap.

The list becomes:

[3, 5, 2, 8]

After further passes, the list becomes:

[2, 3, 5, 8]

Python Program

def bubble_sort(numbers):
    numbers = numbers.copy()
    n = len(numbers)

    for i in range(n):
        swapped = False

        for j in range(0, n - i - 1):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = (
                    numbers[j + 1], numbers[j]
                )
                swapped = True

        if not swapped:
            break

    return numbers


data = [5, 3, 8, 2]

print(bubble_sort(data))

Output:

[2, 3, 5, 8]

Bubble sort has worst-case time complexity O(n²).

It is useful for learning, but it is generally not the best choice for sorting large datasets.

---

7.2 Selection Sort

Selection sort repeatedly finds the smallest remaining element and places it in the next position.

Example

Original list:

[29, 10, 14, 37, 13]

Steps:

1. Find the smallest value, 10, and place it first.

2. Find the smallest value among the remaining elements, 13.

3. Continue until the list is sorted.

Result:

[10, 13, 14, 29, 37]

Python Program

def selection_sort(numbers):
    numbers = numbers.copy()
    n = len(numbers)

    for i in range(n):
        min_index = i

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

        numbers[i], numbers[min_index] = (
            numbers[min_index], numbers[i]
        )

    return numbers


data = [29, 10, 14, 37, 13]

print(selection_sort(data))

Output:

[10, 13, 14, 29, 37]

Selection sort has worst-case time complexity O(n²).

---

7.3 Insertion Sort

Insertion sort builds a sorted section one element at a time.

Imagine arranging playing cards in your hand. You pick up a card and insert it into the correct position among the cards already arranged.

Example

Original list:

[5, 2, 4, 1]

The list is gradually arranged until it becomes:

[1, 2, 4, 5]

Python Program

def insertion_sort(numbers):
    numbers = numbers.copy()

    for i in range(1, len(numbers)):
        key = numbers[i]
        j = i - 1

        while j >= 0 and numbers[j] > key:
            numbers[j + 1] = numbers[j]
            j -= 1

        numbers[j + 1] = key

    return numbers


data = [5, 2, 4, 1]

print(insertion_sort(data))

Output:

[1, 2, 4, 5]

Insertion sort has worst-case time complexity O(n²). It can perform well on small or nearly sorted lists.

---

7.4 Python's Built-in Sorting

In real projects, Python's built-in sorting is usually the best starting point.

Using sort()

marks = [78, 92, 65, 88, 73]

marks.sort()

print(marks)

Output:

[65, 73, 78, 88, 92]

sort() changes the original list.

Using sorted()

marks = [78, 92, 65, 88, 73]

result = sorted(marks)

print("Original:", marks)
print("Sorted:", result)

Output:

Original: [78, 92, 65, 88, 73]
Sorted: [65, 73, 78, 88, 92]

sorted() returns a new sorted list.

Sorting in Descending Order

marks = [78, 92, 65, 88, 73]

print(sorted(marks, reverse=True))

Output:

[92, 88, 78, 73, 65]

Sorting Names Alphabetically

students = ["Riya", "Aman", "Neha", "Raman"]

print(sorted(students))

Output:

['Aman', 'Neha', 'Raman', 'Riya']

Python Pebble: Learn how algorithms work, but use Python's built-in sorting for most everyday applications.

Sorting Algorithm Comparison

Algorithm	Average/Worst-Case Time	Main Idea
Bubble sort	O(n²)	Compare adjacent elements
Selection sort	O(n²)	Select the smallest remaining element
Insertion sort	O(n²)	Insert into the sorted section
Python's built-in sort	O(n log n) worst case	Efficient, adaptive sorting

---

8. Searching and Sorting Together

Searching and sorting are often used together.

Imagine a teacher has marks for 10 students.

The teacher wants to:

1. Arrange the marks from lowest to highest.

2. Find whether a student scored 85.

3. Display the position of that score in the sorted list.

Complete Example

marks = [72, 85, 63, 91, 78, 85]

sorted_marks = sorted(marks)

print("Sorted marks:", sorted_marks)

target = 85

index = sorted_marks.index(target)

print("First occurrence of 85 is at index:", index)

Output:

Sorted marks: [63, 72, 78, 85, 85, 91]
First occurrence of 85 is at index: 3

Remember: .index() returns the first occurrence, and indexes start at zero.

If you use binary search instead, remember to provide sorted data.

---

9. Master Project – Student Record Manager

Now let's combine searching and sorting in a practical program.

Project Requirements

Create a program that:

1. Stores student names and marks.

2. Displays all students.

3. Sorts students by marks.

4. Searches for a student by name.

5. Displays the highest-scoring student.

Python Program

students = [
    {"name": "Riya", "marks": 88},
    {"name": "Aman", "marks": 76},
    {"name": "Neha", "marks": 95},
    {"name": "Raman", "marks": 82},
    {"name": "Arjun", "marks": 91}
]


def display_students(records):
    for student in records:
        print(student["name"], "-", student["marks"])


def sort_by_marks(records):
    return sorted(
        records,
        key=lambda student: student["marks"]
    )


def search_student(records, name):
    for student in records:
        if student["name"].lower() == name.lower():
            return student

    return None


print("All Students:")
display_students(students)

print("\nSorted by Marks:")
display_students(sort_by_marks(students))

name = input("\nEnter student name to search: ")
result = search_student(students, name)

if result is not None:
    print("Found:", result["name"], result["marks"])
else:
    print("Student not found")

topper = max(students, key=lambda student: student["marks"])

print("\nTopper:", topper["name"], topper["marks"])

Example output for a search for Neha:

All Students:
Riya - 88
Aman - 76
Neha - 95
Raman - 82
Arjun - 91

Sorted by Marks:
Aman - 76
Raman - 82
Riya - 88
Arjun - 91
Neha - 95

Enter student name to search: Neha
Found: Neha 95

Topper: Neha 95

Master Challenge

Extend the project by adding:

• A menu-driven interface.

• A stack to store the last few operations.

• A queue for students waiting to be processed.

• A deque to maintain a recent-history list.

• A linked list to store student records for practice.

• Linear and binary search options.

• Sorting by name or marks.

• Input validation for marks between 0 and 100.

For a more realistic application, you can keep student records in a list of dictionaries. Use a linked list as a separate exercise to understand node-based data structures.

---

10. Practice Questions

Level 1 – Concepts

1. What is a data structure?

2. What does LIFO stand for?

3. What does FIFO stand for?

4. Which data structure allows insertion and removal at both ends?

5. What information does a node in a singly linked list contain?

6. What is the difference between linear and binary search?

7. Why must data be sorted before binary search?

8. What is the purpose of sorting?

9. What does pop() do when used on a list as a stack?

10. What is the difference between sort() and sorted()?

Level 2 – Coding

11. Write a stack program that pushes five integers and pops two.

12. Create a queue using collections.deque.

13. Create a deque and add an item to each end.

14. Create three linked-list nodes and connect them.

15. Write a function for linear search.

16. Write a function for binary search on sorted data.

17. Implement bubble sort.

18. Implement selection sort.

19. Implement insertion sort.

20. Sort student records by marks using sorted().

Level 3 – Thinking Challenges

21. Which data structure would you choose for an undo feature? Explain why.

22. Which data structure would you use for a printer queue?

23. Why can binary search be faster than linear search?

24. Why is a linked list not as convenient as a Python list for accessing the element at index 100?

25. Which sorting algorithm would you choose for a small, nearly sorted list, and why?

26. How could a deque help check whether a word is a palindrome?

27. What happens when you pop from an empty list?

28. How would you avoid searching a student record list repeatedly?

29. How would you modify the Student Record Manager to sort marks in descending order?

30. Why should an algorithm's time complexity matter when working with thousands of records?

---

11. Quick Revision Table

Topic	Key Idea	Python Tool
Stack	Last In, First Out	list.append(), list.pop()
Queue	First In, First Out	collections.deque
Deque	Operations at both ends	appendleft(), popleft()
Linked list	Nodes connected by references	Classes and references
Linear search	Check items one by one	Loop
Binary search	Repeatedly halve sorted search range	Loop and indexes
Bubble sort	Compare adjacent elements	Nested loops
Selection sort	Select the smallest remaining item	Nested loops
Insertion sort	Insert into sorted section	Loop
Built-in sorting	Efficient general-purpose sorting	sort(), sorted()

---

12. Python Pebble

A good programmer knows how to store data. A great programmer also understands how to access, search, and organize it efficiently.

Stacks help manage the latest item first. Queues process items in arrival order. Deques work at both ends. Linked lists teach you how nodes connect. Searching finds information, and sorting organizes it.

Start with small examples, trace each step by hand, and then write your own programs.

Your next step: Complete the Student Record Manager, test it with different data, and experiment with the time complexity of your searching and sorting algorithms.