Algorithms and Concepts:
Concrete Examples
Here are concrete examples for each of the algorithms and concepts
discussed.
A. Bubble Sort Example
Initial List: [6, 4, 1, 8, 3]
Pass 1:
Compare (6, 4) -> Swap -> [4, 6, 1, 8, 3]
Compare (6, 1) -> Swap -> [4, 1, 6, 8, 3]
Compare (6, 8) -> No swap -> [4, 1, 6, 8, 3]
Compare (8, 3) -> Swap -> [4, 1, 6, 3, 8] (8 "bubbles" to the end)
Pass 2:
Compare (4, 1) -> Swap -> [1, 4, 6, 3, 8]
Compare (4, 6) -> No swap -> [1, 4, 6, 3, 8]
Compare (6, 3) -> Swap -> [1, 4, 3, 6, 8] (6 "bubbles" closer)
Pass 3:
Compare (1, 4) -> No swap -> [1, 4, 3, 6, 8]
Compare (4, 3) -> Swap -> [1, 3, 4, 6, 8]
Compare (4, 6) -> No swap -> [1, 3, 4, 6, 8]
Pass 4:
Compare (1, 3) -> No swap -> [1, 3, 4, 6, 8]
Compare (3, 4) -> No swap -> [1, 3, 4, 6, 8]
No swaps occurred in this pass, so the algorithm terminates.
Final Sorted List: [1, 3, 4, 6, 8]
B. Quick Sort Example
Initial List: [10, 7, 8, 9, 1, 5]
Choose a Pivot: Let's pick the last element, 5.
Partition: We move all elements smaller than 5 to the left and all elements larger than 5 to the right.
[1, 5, 10, 7, 8, 9] -> After partitioning, the pivot 5 is in its final position.
Left Sub-array: [1]
Right Sub-array: [10, 7, 8, 9]
Recursively Sort Right Sub-array: [10, 7, 8, 9]
Pivot: Let's pick 9.
Partition:
[7, 8, 9, 10] -> The pivot 9 is in its final position.
Left Sub-array: [7, 8]
Right Sub-array: [10]
Recursively Sort [7, 8]:
Pivot: 8
Partition:
[7, 8] -> 7 is less than 8, so the list is already partitioned.
The sub-array is now sorted.
Combine: The sorted sub-arrays are merged back together.
[1]
[7, 8]
[9]
[10]
Final Sorted List: [1, 5, 7, 8, 9, 10]
C. Merge Sort Example
Initial List: [8, 3, 1, 7, 0, 10, 2] Divide (recursive split):
[8, 3, 1, 7] and [0, 10, 2]
[8, 3] and [1, 7] and [0, 10] and [2]
[8] [3] [1] [7] [0] [10] [2] (now we have sub-lists of size 1,
which are sorted)
Merge (combine sorted sub-lists): Final Sorted List: [0, 1, 2, 3, 7, 8, 10]
Merge [8] and [3] -> [3, 8]
Merge [1] and [7] -> [1, 7]
Merge [0] and [10] -> [0, 10]
[2] remains separate.
Now we have [3, 8], [1, 7], [0, 10], [2]
Merge [3, 8] and [1, 7] -> [1, 3, 7, 8]
Merge [0, 10] and [2] -> [0, 2, 10]
Finally, merge [1, 3, 7, 8] and [0, 2, 10]
We compare 1 and 0 (take 0). List is [0].
We compare 1 and 2 (take 1). List is [0, 1].
We compare 3 and 2 (take 2). List is [0, 1, 2].
We compare 3 and 10 (take 3). List is [0, 1, 2, 3].
...and so on, until the list is fully merged.
2. Examples for the Travelling Salesman Problem (TSP) Search Tree
Let's use a small example with four cities: A, B, C, and D. The distances between cities are given in a matrix.
Distance Matrix:
A - 10 15 20
B 10 - 35 25
C 15 35 - 30
D 20 25 30 -
Brute-Force Search Tree Walkthrough:
Let's start the tour at City A. The possible tours are permutations of the remaining cities (B, C, D). There are (4-1)! = 3! = 6
possible tours.
1. Tour 1: A -> B -> C -> D -> A
Distance: A to B (10) + B to C (35) + C to D (30) + D to A (20) = 95
2. Tour 2: A -> B -> D -> C -> A
Distance: A to B (10) + B to D (25) + D to C (30) + C to A (15) = 80
3. Tour 3: A -> C -> B -> D -> A
Distance: A to C (15) + C to B (35) + B to D (25) + D to A (20) = 95
4. Tour 4: A -> C -> D -> B -> A
Distance: A to C (15) + C to D (30) + D to B (25) + B to A (10) = 80
5. Tour 5: A -> D -> B -> C -> A
Distance: A to D (20) + D to B (25) + B to C (35) + C to A (15) = 95
6. Tour 6: A -> D -> C -> B -> A
Distance: A to D (20) + D to C (30) + C to B (35) + B to A (10) = 95
Result: After evaluating all 6 possible tours, we see that the shortest tours have a total distance of 80. These tours are A -> B ->
D -> C -> A and A -> C -> D -> B -> A.
This simple example shows how the brute-force search tree works: you generate every possible path and calculate its cost,
then you find the minimum among all the costs. For a real-world problem with many cities, this approach is not practical due
to the enormous number of paths to check.
1. Programs for Sorting Algorithms
A. Bubble Sort Program
This program implements the Bubble Sort algorithm. The outer loop controls the number of passes, and the inner loop
handles the comparisons and swaps of adjacent elements.
def bubble_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n - i - 1):
# Traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Example usage
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print("Sorted array using Bubble Sort is:", my_list)
B. Quick Sort Program
This program implements the Quick Sort algorithm recursively. It uses a partition function to place the pivot in its correct
sorted position and then recursively sorts the sub-arrays.
def partition(arr, low, high):
i = (low - 1) # index of smaller element
pivot = arr[high] # pivot
for j in range(low, high):
# If current element is smaller than or equal to pivot
if arr[j] <= pivot:
i=i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
# pi is the partitioning index, arr[pi] is now at right place
pi = partition(arr, low, high)
# Recursively sort elements before partition and after partition
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
# Example usage
my_list = [10, 7, 8, 9, 1, 5]
n = len(my_list)
quick_sort(my_list, 0, n - 1)
print("Sorted array using Quick Sort is:", my_list)
C. Merge Sort Program
This program implements the Merge Sort algorithm, which is a classic example of a divide-and-conquer approach. It
recursively splits the list and then merges the sorted halves.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements into 2 halves
R = arr[mid:]
merge_sort(L) # Sorting the first half
merge_sort(R) # Sorting the second half
i=j=k=0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Check for any remaining elements
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# Example usage
my_list = [12, 11, 13, 5, 6, 7]
merge_sort(my_list)
print("Sorted array using Merge Sort is:", my_list)
2. Program for the Travelling Salesman Problem (Brute Force)
This program uses the brute-force approach to solve the TSP. It leverages the itertools library to generate all possible
permutations of cities and then calculates the total distance for each tour to find the minimum.
import math
from itertools import permutations
# Define the cities and their coordinates
# You can change these to your own cities
cities = {
'A': (0, 0),
'B': (10, 0),
'C': (15, 15),
'D': (0, 10),
}
# Create a list of city names
city_names = list(cities.keys())
n = len(city_names)
# Function to calculate the Euclidean distance between two points
def distance(city1, city2):
x1, y1 = cities[city1]
x2, y2 = cities[city2]
return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
def tsp_brute_force():
# Initialize variables to track the best tour
min_distance = float('inf')
best_tour = None
# Start at a fixed city (e.g., the first one) to reduce permutations
start_city = city_names[0]
remaining_cities = city_names[1:]
# Generate all permutations of the remaining cities
for tour_permutation in permutations(remaining_cities):
current_tour = (start_city,) + tour_permutation
current_distance = 0
# Calculate the distance for the current tour
for i in range(n - 1):
current_distance += distance(current_tour[i], current_tour[i+1])
# Add the distance from the last city back to the start city
current_distance += distance(current_tour[-1], start_city)
# Update the minimum distance and best tour if a better one is found
if current_distance < min_distance:
min_distance = current_distance
best_tour = current_tour
return best_tour, min_distance
# Run the algorithm and print the result
best_tour, min_dist = tsp_brute_force()
print(f"The best tour is: {' -> '.join(best_tour)} -> {best_tour[0]}")
print(f"The minimum distance is: {min_dist:.2f}")
Note: The TSP brute-force program will become extremely slow with more than about 10-12 cities due to the factorial time
complexity. For larger numbers of cities, you would need to use more advanced algorithms like dynamic programming (Held-
Karp) or heuristics.
