2.2.1 Sorting Algorithms

Introduction

Sorting algorithms are used to arrange data in a useful manner, such as ascending or descending order. When data is sorted, it becomes easier to search, analyze, and understand. Sorting is one of the most fundamental operations in computer science, and many other algorithms depend on data being sorted.

Definition

Sorting algorithms are methods used to arrange data in a specific order (such as ascending or descending) so that it becomes more useful and easier to work with.

In simple words, sorting means putting things in order — like arranging books on a shelf from shortest to tallest, or arranging numbers from smallest to largest.

Main Idea

• Insertion Sort algorithm
• Bubble Sort algorithm

Each sorting algorithm has its own approach, advantages, and disadvantages. The choice of which sorting algorithm to use depends on the specific requirements of the problem.

Core Concept

Sorting works by comparing elements and rearranging them until they are in the correct order. The two basic sorting algorithms discussed here are:

• Insertion Sort: Builds a sorted portion of the array one element at a time by inserting each new element into its correct position.
• Bubble Sort: Repeatedly compares and swaps adjacent elements until the largest elements "bubble" to the end of the array.

Detailed Explanation

a) Insertion Sort Algorithm

In Insertion sort, we compare adjacent elements and sort them if they are not in correct order. While comparison, the smallest element is selected and swapped with the element that is placed at first location. This is the first iteration, and we will continue until all elements are sorted. At the end, we have an array of sorted elements.

Working of Insertion Sort Algorithm

Consider the following array of unsorted elements which need to be sorted in ascending order. For ease, let's use four colors to represent four different things in the given array:

• Yellow color for unsorted array
• Blue color for elements to be compared in the unsorted array
• Green color for sorted array
• Red color for elements that are not correct in the sorted part of array

At the start, all elements are colored yellow.

Initial array: 12, 31, 25, 8, 32, 17

Step 1: Assuming first element (12) is already sorted.

Step 2: Compare 31 with 12. Because 31 is larger than 12, it means that first element is already in correct order.

Step 3: Now, move to the next element (25) and compare it with adjacent element in the sorted array (25 with 31). Here, 25 is smaller as compared to 31. It means, 31 is not at its correct position, therefore, swap both the elements (25 with 31).

Step 4: Along with swapping, we also need to check and compare it with all elements in the sorted array. Till now, the sorted array contains one element (12). So, 25 will be compared with 12. Here, 25 is greater than 12. So, the sorted array remains same.

Step 5: We now move forward to next element that is 8 and compare it with its adjacent element in the sorted array (31). Here, 31 is greater than 8, so swap them.

Step 6: After the above swapping, you will note that elements 25 and 8 are not in its correct order. So, accordingly swap them.

Step 7: The elements 12 and 8 are also not in its correct order. So, accordingly swap them.

Step 8: Now we move to the next elements that is 32 and compare it with adjacent element in sorted array that is 31. Similarly 32 will be compared with previous element in the sorted array; there will be no change because they are already sorted. No swapping is required because they are already sorted.

Step 9: Next, compare 32 with 17. 32 is greater than 17. So, swap them. This swapping will make 31 and 17 unsorted. So, swap them too. Now, this will make 25 and 17 unsorted. So, swapping them again.

Step 10: Now, the sorting process is complete as the array is in correct order.

Final sorted array: 8, 12, 17, 25, 31, 32

Insertion Sort in Context of Computational Thinking

Decomposition: - Sub-processes: Compare adjacent elements, shift larger elements, insert current element

• Repetition: The process involves repeating the steps for each item.
• Building Order: The algorithm focuses on building a sorted collection incrementally.
• Ordered Comparison: It employs comparisons to determine the correct position of each item.

Algorithmic Design

• Start with the second element: Begin with the second element of the array (assuming the first element is already "sorted").
• Pick the current element: Pick the current element and remember it.
• Compare with sorted elements: Compare the current element with the elements in the "sorted" part of the array.
• Shift larger elements to the right: If the current element is smaller than the elements in the "sorted" part, shift those larger elements to the right to create space.
• Insert the current element: Insert the current element into its correct position in the "sorted" part.
• Repeat for each element: Repeat these steps for each element in the array, gradually expanding the "sorted" part.

b) Bubble Sort Algorithm

In Bubble Sort algorithm, we repeatedly compare and swap the adjacent elements if they are not in correct order.

If we need to sort the array in ascending order, then bubble sort algorithm starts by taking first element of the array and compare it with the second element first iteration. Suppose if the first element is greater than the second then it will swap these elements, and then move forward to compare the second element with the third element, and it continues until the largest element reaches the last place in the array.

We need to repeat this process (iteration) until the complete list is sorted.

Working of Bubble Sort Algorithm

Consider the following array of elements:

Initial array: 13, 32, 26, 35, 10

First Iteration:

• Take the first element and compare it with its adjacent element. Here, the first element (13) is smaller than the second element (32), so it is already sorted.
• Now, take the second element and compare it with next adjacent element (e.g. 32 with 26). Here, 32 is greater than 26. So, we need to swap them both.
• After the swapping, array will look like: 13, 26, 32, 35, 10
• Now, we will compare 35 with 10. Here, 35 is greater than 10 and need swapping.
• The element 35 has reached at the last place of the array.
• At the end of first iteration, the array will look like: 13, 26, 32, 10, 35

Second Iteration:

• In second iteration, we will follow the same process.
• Here, 32 is greater than 10. So, perform swapping operation.
• Similarly, next iteration will be done.

Third Iteration:

• In third iteration, we will follow the same process again.
• Here, 26 is greater than 10. So, perform the swapping again.
• Now, move to next iteration.

Fourth Iteration:

- Again follow the same process; the array is completely sorted now.

Final sorted array: 10, 13, 26, 32, 35

Bubble Sort in Context of Computational Thinking

Abstraction: Organize a collection of items by repeatedly comparing and swapping adjacent items until the entire collection is sorted. It will perform iterative comparison and swapping to achieve order.

• Adjacent Comparison: Compare each pair of adjacent items.
• Swap Logic: If a pair is out of order, swap them.
• Iteration: Repeat the process until the collection is sorted.

• Pairwise Comparison: The algorithm focuses on comparing and adjusting adjacent pairs.
• Iterative Process: The sorting process is achieved through multiple iterations.
• Repeating Patterns: The comparison and swapping steps are repeated until the entire collection is in order.

Algorithmic Design

• Start from the first element of the array.
• Compare the first element with the adjacent element.
• Move to the next pair of elements and repeat the comparison and swapping process. Continue this process until you reach the end of the array for the first iteration.
• After the first iteration, the largest element is guaranteed to be at the end of the array. You don't need to consider this element in the subsequent passes since it is already in its correct position.
• Repeat the above steps for the remaining elements (excluding the ones that are already sorted). In each iteration, the next largest unsorted element will be placed in its correct position.
• Continue this process until the entire array is sorted. The number of iterations required is one less than the total number of elements in the array.

Insertion Sort vs Bubble Sort

Both Insertion Sort and Bubble Sort are basic sorting algorithms. The choice of sorting algorithm depends on the specific requirements of your problem.

Example — Sorting a Shelf of Books:

Imagine you have a shelf of books that you want to arrange in alphabetical order. Compare different methods:

• Insertion Sort: Pick up each book one by one. Insert each book into its correct position on the shelf relative to the books you're already holding.
• Bubble Sort: Compare each pair of adjacent books from left to right. If a pair is out of order, swap their positions. Continue this process, moving from left to right, until the entire shelf is sorted.

Algorithm Evaluation → Efficiency: The time it takes and the number of movements represent the efficiency of the sorting algorithm.

Intermediate Level

Comparison Table — Insertion Sort vs Bubble Sort

Why Sorting is Useful

Sorting is useful because:

• It makes searching faster (especially Binary Search)
• It makes data easier to understand
• It helps in finding duplicates
• It makes data easier to analyze
• It is required for many other algorithms

How Insertion Sort Works — Step by Step

For an array of n elements:

• Start with the second element (index 1).
• Store the current element in a temporary variable.
• Compare with elements in the sorted part (index 0 to i-1).
• Shift all larger elements one position to the right.
• Insert the current element into its correct position.
• Repeat for all elements from index 1 to n-1.

How Bubble Sort Works — Step by Step

For an array of n elements:

• Start from the first element (index 0).
• Compare with the next element (index 1).
• If the first is greater, swap them.
• Move to the next pair (index 1 and 2).
• Continue until the end of the array.
• After one full pass, the largest element is at the last position.
• Repeat for the remaining elements (n-1 passes in total).

Formula / Mathematical Form

Insertion Sort (conceptual):

``` For i from 1 to n-1: key = array[i] j = i - 1 While j >= 0 and array[j] > key: array[j+1] = array[j] j = j - 1 array[j+1] = key ```

Bubble Sort (conceptual):

``` For i from 0 to n-2: For j from 0 to n-i-2: If array[j] > array[j+1]: Swap array[j] and array[j+1] ```

Solved Example

Example — Insertion Sort on [12, 31, 25, 8, 32, 17]

Step 1: 12 is sorted. Array: [12, 31, 25, 8, 32, 17] Step 2: 31 > 12, no change. Array: [12, 31, 25, 8, 32, 17] Step 3: 25 < 31, swap. Array: [12, 25, 31, 8, 32, 17] Step 4: 25 > 12, no change. Array: [12, 25, 31, 8, 32, 17] Step 5: 8 < 31, swap. Array: [12, 25, 8, 31, 32, 17] Step 6: 8 < 25, swap. Array: [12, 8, 25, 31, 32, 17] Step 7: 8 < 12, swap. Array: [8, 12, 25, 31, 32, 17] Step 8: 32 > 31, no change. Array: [8, 12, 25, 31, 32, 17] Step 9: 17 < 32, swap. Array: [8, 12, 25, 31, 17, 32] Step 10: 17 < 31, swap. Array: [8, 12, 25, 17, 31, 32] Step 11: 17 < 25, swap. Array: [8, 12, 17, 25, 31, 32] Step 12: 17 > 12, no change. Array: [8, 12, 17, 25, 31, 32]

Final sorted array: [8, 12, 17, 25, 31, 32]

Example — Bubble Sort on [13, 32, 26, 35, 10]

• Compare 13 and 32: no swap → [13, 32, 26, 35, 10]
• Compare 32 and 26: swap → [13, 26, 32, 35, 10]
• Compare 32 and 35: no swap → [13, 26, 32, 35, 10]
• Compare 35 and 10: swap → [13, 26, 32, 10, 35]

• Compare 13 and 26: no swap → [13, 26, 32, 10, 35]
• Compare 26 and 32: no swap → [13, 26, 32, 10, 35]
• Compare 32 and 10: swap → [13, 26, 10, 32, 35]

• Compare 13 and 26: no swap → [13, 26, 10, 32, 35]
• Compare 26 and 10: swap → [13, 10, 26, 32, 35]

Iteration 4: - Compare 13 and 10: swap → [10, 13, 26, 32, 35]

Final sorted array: [10, 13, 26, 32, 35]

Important Points

• - Sorting algorithms arrange data in a useful manner (ascending or descending).
• - Insertion Sort compares adjacent elements and inserts each element into its correct position in the sorted part.
• - Bubble Sort repeatedly compares and swaps adjacent elements until the largest element reaches the end.
• - Both algorithms are basic and suitable for small or nearly sorted data.
• - Insertion Sort generally performs better than Bubble Sort.
• - Sorting makes searching faster and data easier to understand.
• - Efficiency is measured by time and number of movements.
• - For n elements, Bubble Sort requires n-1 iterations in the worst case.

Remember

• - Insertion Sort: Compare adjacent, insert into correct position.
• - Bubble Sort: Compare adjacent, swap if out of order; largest bubbles to end.
• - Insertion Sort = like sorting playing cards.
• - Bubble Sort = largest element bubbles to the end.
• - Both are basic sorting algorithms.
• - Insertion Sort generally has fewer swaps.
• - Bubble Sort requires n-1 iterations for n elements.
• - Sorting makes searching faster.

Common Mistakes

• - Confusing Insertion Sort with Bubble Sort: Insertion Sort inserts elements into a sorted part; Bubble Sort swaps adjacent elements repeatedly.
• - Thinking Bubble Sort is always bad: Bubble Sort is useful for small or nearly sorted data.
• - Not considering efficiency: For large data, both algorithms are slow; other algorithms are better.
• - Forgetting to compare with all elements in sorted part: In Insertion Sort, each element must be compared with all elements in the sorted part until its correct position is found.
• - Mixing up the steps: In Insertion Sort, elements are shifted and inserted; in Bubble Sort, adjacent elements are swapped.
• - Assuming one pass is enough: Bubble Sort requires multiple passes (n-1 in worst case).
• - Not recognizing when the array is already sorted: Both algorithms can detect this and stop early if optimized.

Quick Revision

Sorting algorithms are used to arrange data in a useful manner (such as ascending or descending order).

• Compares adjacent elements and sorts them if they are not in correct order.
• While comparison, the smallest element is selected and swapped with the element that is placed at first location.
• Continues until all elements are sorted.
• Like sorting a hand of playing cards.

• Repeatedly compares and swaps adjacent elements if they are not in correct order.
• Starts by taking first element and comparing it with the second element.
• If the first element is greater than the second, it swaps them and moves forward.
• Continues until the largest element reaches the last place in the array.
• Repeats this process until the complete list is sorted.

• Size of data
• Whether data is nearly sorted
• Efficiency requirements

60-Second Revision

• Sorting: Arrange data in order.
• Insertion Sort: Compare adjacent, insert into correct position. Like sorting playing cards.
• Bubble Sort: Compare adjacent, swap if out of order. Largest bubbles to end.
• Both: Basic algorithms, suitable for small or nearly sorted data.
• Insertion Sort: Generally fewer swaps, better performance.
• Bubble Sort: n-1 iterations for n elements.
• Efficiency: Time + number of movements.
• Warning: Both algorithms are slow for large data — other algorithms are better for large datasets.