Sorting

Given: numList = [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]

Concept: In Bubble Sort, in each pass we compare adjacent elements and swap them if they are in the wrong order. After pass $k$, the $k$ largest elements are placed at the end in their correct positions.

---

Pass 1:

Start: [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]

- Compare 7, 11 → no swap → [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]
- Compare 11, 3 → swap → [7, 3, 11, 10, 17, 23, 1, 4, 21, 5]
- Compare 11, 10 → swap → [7, 3, 10, 11, 17, 23, 1, 4, 21, 5]
- Compare 11, 17 → no swap → [7, 3, 10, 11, 17, 23, 1, 4, 21, 5]
- Compare 17, 23 → no swap → [7, 3, 10, 11, 17, 23, 1, 4, 21, 5]
- Compare 23, 1 → swap → [7, 3, 10, 11, 17, 1, 23, 4, 21, 5]
- Compare 23, 4 → swap → [7, 3, 10, 11, 17, 1, 4, 23, 21, 5]
- Compare 23, 21 → swap → [7, 3, 10, 11, 17, 1, 4, 21, 23, 5]
- Compare 23, 5 → swap → [7, 3, 10, 11, 17, 1, 4, 21, 5, 23]

After Pass 1: [7, 3, 10, 11, 17, 1, 4, 21, 5, 23]

---

Pass 2:

Start: [7, 3, 10, 11, 17, 1, 4, 21, 5, 23]

- Compare 7, 3 → swap → [3, 7, 10, 11, 17, 1, 4, 21, 5, 23]
- Compare 7, 10 → no swap → [3, 7, 10, 11, 17, 1, 4, 21, 5, 23]
- Compare 10, 11 → no swap → [3, 7, 10, 11, 17, 1, 4, 21, 5, 23]
- Compare 11, 17 → no swap → [3, 7, 10, 11, 17, 1, 4, 21, 5, 23]
- Compare 17, 1 → swap → [3, 7, 10, 11, 1, 17, 4, 21, 5, 23]
- Compare 17, 4 → swap → [3, 7, 10, 11, 1, 4, 17, 21, 5, 23]
- Compare 17, 21 → no swap → [3, 7, 10, 11, 1, 4, 17, 21, 5, 23]
- Compare 21, 5 → swap → [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]
- Compare 21, 23 → no swap → [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]

After Pass 2: [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]

---

Pass 3:

Start: [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]

- Compare 3, 7 → no swap → [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]
- Compare 7, 10 → no swap → [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]
- Compare 10, 11 → no swap → [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]
- Compare 11, 1 → swap → [3, 7, 10, 1, 11, 4, 17, 5, 21, 23]
- Compare 11, 4 → swap → [3, 7, 10, 1, 4, 11, 17, 5, 21, 23]
- Compare 11, 17 → no swap → [3, 7, 10, 1, 4, 11, 17, 5, 21, 23]
- Compare 17, 5 → swap → [3, 7, 10, 1, 4, 11, 5, 17, 21, 23]
- Compare 17, 21 → no swap → [3, 7, 10, 1, 4, 11, 5, 17, 21, 23]

After Pass 3: [3, 7, 10, 1, 4, 11, 5, 17, 21, 23]

---

Final Answer: After three complete passes of Bubble Sort, the partially sorted list is:
$$[3, 7, 10, 1, 4, 11, 5, 17, 21, 23]$$

Given: List = [63, 42, 21, 9]

---

### Bubble Sort

Concept: Compare adjacent elements and swap if out of order. Count swaps and comparisons.

Pass 1: (n−1 = 3 comparisons)
- Compare 63, 42 → swap → [42, 63, 21, 9] — Swap 1
- Compare 63, 21 → swap → [42, 21, 63, 9] — Swap 2
- Compare 63, 9 → swap → [42, 21, 9, 63] — Swap 3

Pass 2: (2 comparisons)
- Compare 42, 21 → swap → [21, 42, 9, 63] — Swap 4
- Compare 42, 9 → swap → [21, 9, 42, 63] — Swap 5

Pass 3: (1 comparison)
- Compare 21, 9 → swap → [9, 21, 42, 63] — Swap 6

Bubble Sort:
- Total Swaps = 6
- Total Comparisons = $3 + 2 + 1 =$ 6

---

### Selection Sort

Concept: Find the minimum element from the unsorted part and swap it with the first element of the unsorted part.

Pass 1: Find minimum in [63, 42, 21, 9] → min = 9 (index 3)
- Comparisons: 3 (compare 63 with 42, 21, 9)
- Swap 63 and 9 → [9, 42, 21, 63] — Swap 1

Pass 2: Find minimum in [42, 21, 63] → min = 21 (index 2)
- Comparisons: 2
- Swap 42 and 21 → [9, 21, 42, 63] — Swap 2

Pass 3: Find minimum in [42, 63] → min = 42 (index 2)
- Comparisons: 1
- No swap needed (already in place) — Swap 0

Selection Sort:
- Total Swaps = 2
- Total Comparisons = $3 + 2 + 1 =$ 6

---

### Comparison Table

| Technique | Swaps | Comparisons |
|---|---|---|
| Bubble Sort | 6 | 6 |
| Selection Sort | 2 | 6 |

Conclusion: Both techniques require the same number of comparisons (6). However, Selection Sort is better because it requires only 2 swaps compared to 6 swaps in Bubble Sort. Fewer swaps mean less data movement, making Selection Sort more efficient for this list.

Given:
- List 1: [2, 3, 5, 7, 11] (already sorted in ascending order)
- List 2: [11, 7, 5, 3, 2] (sorted in descending order — worst case)

Concept: In Insertion Sort, each element is picked and inserted at its correct position in the already-sorted portion. If the list is already sorted, each new element only needs 1 comparison (with its immediate predecessor). If the list is in reverse order, each new element needs to be compared with all elements in the sorted portion.

---

### List 1: [2, 3, 5, 7, 11] — Already Sorted (Best Case)

| Pass | Element Picked | Sorted Portion | Comparisons | Result |
|---|---|---|---|---|
| 1 | 3 | [2] | 1 (3 > 2, no shift) | [2, 3, 5, 7, 11] |
| 2 | 5 | [2, 3] | 1 (5 > 3, no shift) | [2, 3, 5, 7, 11] |
| 3 | 7 | [2, 3, 5] | 1 (7 > 5, no shift) | [2, 3, 5, 7, 11] |
| 4 | 11 | [2, 3, 5, 7] | 1 (11 > 7, no shift) | [2, 3, 5, 7, 11] |

Total Comparisons for List 1 = 1 + 1 + 1 + 1 = 4

---

### List 2: [11, 7, 5, 3, 2] — Reverse Sorted (Worst Case)

| Pass | Element Picked | Sorted Portion | Comparisons | Result |
|---|---|---|---|---|
| 1 | 7 | [11] | 1 (7 < 11, shift 11) | [7, 11, 5, 3, 2] |
| 2 | 5 | [7, 11] | 2 (5 < 11, 5 < 7, shift both) | [5, 7, 11, 3, 2] |
| 3 | 3 | [5, 7, 11] | 3 (3 < 11, 3 < 7, 3 < 5, shift all) | [3, 5, 7, 11, 2] |
| 4 | 2 | [3, 5, 7, 11] | 4 (2 < 11, 2 < 7, 2 < 5, 2 < 3, shift all) | [2, 3, 5, 7, 11] |

Total Comparisons for List 2 = 1 + 2 + 3 + 4 = 10

---

Conclusion: List 1 makes the minimum number of comparisons (4) because it is already sorted in ascending order, which is the best case for Insertion Sort. List 2 requires 10 comparisons as it is in reverse order (worst case).

In general:
- Best case complexity of Insertion Sort = $O(n)$ → when list is already sorted.
- Worst case complexity of Insertion Sort = $O(n^2)$ → when list is in reverse order.

Concept:
- Sort the list using Bubble Sort.
- If the number of elements $n$ is odd, median = element at index $n // 2$.
- If $n$ is even, median = average of elements at indices $n//2 - 1$ and $n//2$.

Program:

```python
def bubbleSort(lst):
n = len(lst)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # compare adjacent elements
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j] # swap
return lst

def findMedian(lst):
sortedList = bubbleSort(lst)
n = len(sortedList)
if n % 2 != 0: # odd number of elements
median = sortedList[n // 2]
else: # even number of elements
mid1 = sortedList[n // 2 - 1]
mid2 = sortedList[n // 2]
median = (mid1 + mid2) / 2
return median

# Main program
numbers = []
n = int(input("Enter the number of elements: "))
for i in range(n):
num = int(input("Enter element " + str(i + 1) + ": "))
numbers.append(num)

result = findMedian(numbers)
print("Sorted List:", numbers)
print("Median =", result)
```

Sample Output 1 (Odd count):
```
Enter the number of elements: 5
Enter element 1: 7
Enter element 2: 3
Enter element 3: 1
Enter element 4: 9
Enter element 5: 5
Sorted List: [1, 3, 5, 7, 9]
Median = 5
```

Sample Output 2 (Even count):
```
Enter the number of elements: 4
Enter element 1: 4
Enter element 2: 2
Enter element 3: 8
Enter element 4: 6
Sorted List: [2, 4, 6, 8]
Median = 5.0
```

Explanation:
- `bubbleSort()` sorts the list in ascending order using nested loops.
- `findMedian()` checks if $n$ is odd or even and returns the appropriate median value.

Concept:
- Sort the marks list using Selection Sort.
- Calculate index = $\text{round}\left(\dfrac{x}{100} \times n\right)$
- The value at that index in the sorted list is the $x^{th}$ percentile.

Program:

```python
import math

def selectionSort(lst):
n = len(lst)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if lst[j] < lst[min_idx]:
min_idx = j
# Swap the found minimum with the first element of unsorted part
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst

def calculatePercentile(marks, x):
# Step I: Sort the list using Selection Sort
sortedMarks = selectionSort(marks)
n = len(sortedMarks)

# Step II: Calculate index
index = (x / 100) * n

# Step III: Round to whole number
index = math.ceil(index) # using ceil to get the next whole number

# Ensure index is within valid range
if index >= n:
index = n - 1

# Step IV: Display the value at that index
print("Sorted Marks:", sortedMarks)
print("Index calculated:", index)
print("The", x, "th percentile value is:", sortedMarks[index])

# Main program
marks = []
n = int(input("Enter the number of students: "))
for i in range(n):
m = int(input("Enter marks of student " + str(i + 1) + ": "))
marks.append(m)

x = int(input("Enter the percentile to calculate (0-100): "))
calculatePercentile(marks, x)
```

Sample Output:
```
Enter the number of students: 5
Enter marks of student 1: 45
Enter marks of student 2: 78
Enter marks of student 3: 62
Enter marks of student 4: 90
Enter marks of student 5: 55
Enter the percentile to calculate (0-100): 90
Sorted Marks: [45, 55, 62, 78, 90]
Index calculated: 5
The 90 th percentile value is: 90
```

Explanation:
- `selectionSort()` sorts the marks in ascending order.
- Index = $\text{round}(0.90 \times 5) = \text{round}(4.5) = 5$, but since valid indices are 0–4, we use index 4 (last element).
- The value at that index is the $x^{th}$ percentile.

Identification of Sorting Technique:

The sorting technique being used here is Insertion Sort. In Insertion Sort, each new element is inserted at its correct position in the already-sorted portion of the list. Similarly, here, every time a new name is entered, it is inserted at the correct position in the already-sorted list of names.

---

Concept: Maintain a sorted list. When a new name is inserted, compare it with existing names from the end of the list and shift names that are greater than the new name one position to the right, then insert the new name at the correct position.

Program:

```python
def insertName(nameList, newName):
"""
Inserts newName into nameList at the correct
position to maintain ascending (alphabetical) order.
"""
# If list is empty, simply append
if len(nameList) == 0:
nameList.append(newName)
return nameList

# Find the correct position using Insertion Sort logic
i = len(nameList) - 1
nameList.append(None) # Extend list by one position

while i >= 0 and nameList[i] > newName:
nameList[i + 1] = nameList[i] # Shift element to the right
i -= 1

nameList[i + 1] = newName # Insert at correct position
return nameList

# Main program
studentNames = []
n = int(input("Enter the number of students: "))

for i in range(n):
name = input("Enter name of student " + str(i + 1) + ": ")
studentNames = insertName(studentNames, name)
print("Current sorted list:", studentNames)

print("\nFinal sorted list of student names:")
for name in studentNames:
print(name)
```

Sample Output:
```
Enter the number of students: 5
Enter name of student 1: Riya
Current sorted list: ['Riya']
Enter name of student 2: Amit
Current sorted list: ['Amit', 'Riya']
Enter name of student 3: Zara
Current sorted list: ['Amit', 'Riya', 'Zara']
Enter name of student 4: Meena
Current sorted list: ['Amit', 'Meena', 'Riya', 'Zara']
Enter name of student 5: Kiran
Current sorted list: ['Amit', 'Kiran', 'Meena', 'Riya', 'Zara']

Final sorted list of student names:
Amit
Kiran
Meena
Riya
Zara
```

Explanation:
- The function `insertName()` is called every time a new name is entered.
- It shifts all names that are alphabetically greater than the new name one position to the right.
- The new name is then placed at the correct position, maintaining ascending alphabetical order at all times.
- This is exactly how Insertion Sort works — inserting each element at its proper place in the sorted portion.