Algorithm Chapter 2 Sorting Notes, Polytechnic 3rd Sem Algorithm Notes

2. Sorting

Sorting is one of the most fundamental operations in computer science. Sorting algorithms arrange data in a specific order (ascending or descending). The efficiency of these algorithms is vital for large-scale data processing, as sorting is used in a wide range of applications, from database management to network routing.

2.1. The Sorting Problem

The sorting problem involves rearranging a collection of elements (numbers, strings, objects) into a specified order, typically in non-decreasing (ascending) or non-increasing (descending) order. The elements in a list or array are rearranged based on a comparison function, which determines whether one element is "less than," "greater than," or "equal to" another.

Key Considerations for Sorting:

• Time Complexity: How fast the algorithm sorts the elements (e.g., $O(n^2)$, $O(n \log n)$).
• Space Complexity: The amount of memory required by the algorithm.
• Stability: A sorting algorithm is stable if it preserves the relative order of equal elements in the sorted output.
• In-place Sorting: An algorithm is in-place if it sorts the data without requiring extra memory beyond a constant amount.

2.2. Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.

Algorithm Steps:

1. Starting from the first element, compare the current element with the next element.
2. If the current element is greater than the next element, swap them.
3. Move to the next element and repeat the process.
4. After each complete pass, the largest unsorted element is "bubbled" to the end of the list.
5. Repeat the steps until the entire list is sorted.

Time Complexity:

• Best case: $O(n)$ when the list is already sorted.
• Average and Worst case: $O(n^2)$, as it requires nested loops.

Space Complexity:

• In-place Sorting: Bubble sort uses $O(1)$ extra space.

Stability:

• Stable: Bubble sort preserves the relative order of equal elements.

Example:

Given the array: [5, 1, 4, 2, 8]

• First Pass: [1, 4, 2, 5, 8]
• Second Pass: [1, 2, 4, 5, 8]
• Third Pass: No swaps required, the array is sorted.

Advantages:

• Easy to understand and implement.
• Suitable for small datasets.

Disadvantages:

• Inefficient for large datasets due to its $O(n^2)$ time complexity.

2.3. Selection Sort

Selection Sort is another simple comparison-based sorting algorithm. It divides the input array into two parts: the sorted part and the unsorted part. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted part and swaps it with the first unsorted element.

Algorithm Steps:

1. Start by finding the smallest element in the entire array.
2. Swap it with the first element of the array.
3. Repeat the process for the remaining unsorted elements (i.e., find the next smallest and swap it with the second element, and so on).
4. Continue until the entire array is sorted.

Time Complexity:

• Best, Average, and Worst case: $O(n^2)$, because of the two nested loops.

Space Complexity:

• In-place Sorting: Selection sort uses $O(1)$ extra space.

Stability:

• Not Stable: Selection sort can disrupt the relative order of equal elements.

Example:

Given the array: [64, 25, 12, 22, 11]

• First Pass: [11, 25, 12, 22, 64]
• Second Pass: [11, 12, 25, 22, 64]
• Third Pass: [11, 12, 22, 25, 64]

Advantages:

• Easy to implement.
• Performs well for small arrays.

Disadvantages:

• Inefficient on large datasets due to $O(n^2)$ complexity.
• Makes unnecessary swaps, even when part of the list is already sorted.

2.4. Insertion Sort

Insertion Sort is a simple, intuitive algorithm where the array is virtually split into a sorted and unsorted part. Elements from the unsorted part are picked and placed into the correct position in the sorted part.

Algorithm Steps:

1. Start with the second element (assuming the first element is already sorted).
2. Compare the second element with the first and insert it into the correct position.
3. Move to the third element, compare it with the first two, and insert it in its correct position.
4. Repeat this process for all remaining elements.

Time Complexity:

• Best case: $O(n)$ when the array is already sorted.
• Average and Worst case: $O(n^2)$, since every insertion requires shifting elements.

Space Complexity:

• In-place Sorting: Insertion sort uses $O(1)$ extra space.

Stability:

• Stable: Insertion sort maintains the relative order of equal elements.

Example:

Given the array: [12, 11, 13, 5, 6]

• First Pass: [11, 12, 13, 5, 6]
• Second Pass: [5, 11, 12, 13, 6]
• Third Pass: [5, 6, 11, 12, 13]

Advantages:

• Efficient for small or nearly sorted datasets.
• Simple and intuitive to implement.

Disadvantages:

• Inefficient for large datasets due to its $O(n^2)$ time complexity.

2.5. Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into smaller subarrays, recursively sorts them, and then merges the sorted subarrays to produce the sorted output.

Algorithm Steps:

1. If the array has only one element or is empty, it is already sorted.
2. Divide the array into two halves.
3. Recursively apply merge sort to both halves.
4. Merge the two sorted halves into a single sorted array.

Time Complexity:

• Best, Average, and Worst case: $O(n \log n)$, since the array is divided in half at each step, and merging takes linear time.

Space Complexity:

• Not In-place Sorting: Merge sort requires $O(n)$ extra space for the auxiliary arrays used during merging.

Stability:

• Stable: Merge sort preserves the relative order of equal elements.

Example:

Given the array: [38, 27, 43, 3, 9, 82, 10]

• Divide: [38, 27, 43, 3] and [9, 82, 10]
• Further divide: [38, 27] and [43, 3], [9] and [82, 10]
• Merge: [27, 38] and [3, 43], [9] and [10, 82]
• Final Merge: [3, 9, 10, 27, 38, 43, 82]

Advantages:

• Efficient for large datasets.
• Guaranteed $O(n \log n)$ performance, regardless of the input distribution.

Disadvantages:

• Requires additional memory for merging, making it less suitable for in-place sorting when space is a concern.

2.6. Quicksort

Quicksort is another divide-and-conquer algorithm that selects a "pivot" element from the array and partitions the other elements into two subarrays—those less than the pivot and those greater than the pivot. The subarrays are then recursively sorted.

Algorithm Steps:

1. Select a pivot element (often the first, last, or middle element).
2. Rearrange the array such that elements smaller than the pivot are on its left, and elements greater than the pivot are on its right (this is called partitioning).
3. Recursively apply quicksort to the left and right subarrays.
4. Combine the sorted subarrays to produce the final sorted array.

Time Complexity:

• Best and Average case: $O(n \log n)$, when the pivot divides the array into relatively equal parts.
• Worst case: $O(n^2)$, if the pivot is poorly chosen and the array is not divided evenly.

Space Complexity:

• In-place Sorting: Quicksort is in-place but requires $O(\log n)$ additional space for recursive calls.

Stability:

• Not Stable: Quicksort does not preserve the relative order of equal elements unless explicitly modified.

Example:

Given the array: [10, 80, 30, 90, 40, 50, 70]

• Choose Pivot: 70
• Partition: [10, 30, 40, 50, 70, 80, 90]
• Recursively sort the left and right subarrays.

Advantages:

• Faster than merge sort for smaller or well-distributed datasets.
• Works well for in-place sorting, making it memory efficient.

Disadvantages:

• Worst-case performance can degrade to $O(n^2)$ if the pivot is poorly chosen.
• Not stable unless modified to handle equal elements properly.

---

These sorting algorithms form the foundation of more complex data processing techniques, and understanding their principles, performance, and trade-offs is key in selecting the right algorithm for different scenarios.