Sorting Algorithms – Class XI CS
What is Sorting?
Sorting means arranging data in a specific order (ascending or descending).
Example:
Unsorted: 45, 12, 89, 33
Sorted (ascending): 12, 33, 45, 89
Importance of Sorting:
• Makes data easy to search
• Helps in data analysis and reporting
• Improves efficiency of other algorithms
1. Bubble Sort
Concept:
Repeatedly compare adjacent elements. If the first is greater than the second, swap them. After
each pass, the largest element “bubbles up” to the end.
Steps:
1. Start from the first element.
2. Compare it with the next element.
3. Swap if out of order.
4. Continue till the end of the list.
5. Repeat until no swaps are needed.
Example (Ascending Order): [5, 3, 4, 1]
• Pass 1: (5,3) → swap [3,5,4,1]; (5,4) → swap [3,4,5,1]; (5,1) → swap [3,4,1,5]
• Pass 2: (3,4) ok; (4,1) → swap [3,1,4,5]
• Pass 3: (3,1) → swap [1,3,4,5]
Sorted: [1,3,4,5]
Time Complexity:
• Worst: O(n²)
• Best: O(n)
Python Code:
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
data = [5, 3, 4, 1]
bubble_sort(data)
print("Bubble Sorted:", data)
2. Insertion Sort
Concept:
Builds the sorted list one element at a time. Takes the next element and inserts it into its correct
position in the sorted part.
Steps:
1. Start from the second element.
2. Compare it with previous elements.
3. Shift larger elements to the right.
4. Insert the element in the correct spot.
Example: [5,3,4,1]
Initially [5];
Insert 3 → [3,5];
Insert 4 → [3,4,5];
Insert 1 → [1,3,4,5]
Sorted: [1,3,4,5]
Time Complexity:
• Worst: O(n²)
• Best: O(n)
Python Code:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
data = [5, 3, 4, 1]
insertion_sort(data)
print("Insertion Sorted:", data)
3. Merge Sort (Divide and Conquer)
Concept:
Breaks the array into halves until each sub-array has one element, then merges them to form the
sorted array.
Steps:
1. Divide the array into two halves.
2. Recursively sort both halves.
3. Merge the two sorted halves.
Example: [5,3,4,1]
Divide [5,3], [4,1];
Sort left [3,5], right [1,4];
Merge [1,3,4,5]
Time Complexity:
• All cases: O(n log n)
4. Quick Sort (Divide and Conquer)
Concept:
Choose a pivot, partition the array into left (smaller) and right (larger), and recursively sort.
Steps:
1. Pick a pivot (first, last, or middle element).
2. Partition the array.
3. Recursively sort left and right parts.
Example: [5,3,4,1]
pivot=5; Left [3,4,1], Right [];
Sort left pivot=3; Left [1], Right [4];
Combine [1,3,4]+[5]=[1,3,4,5]
Time Complexity:
• Average: O(n log n)
• Worst: O(n²)