Section 1

Sorting Algorithms Exam - Cheatsheet 2

STUDY GUIDE

🎓 Sorting Algorithms Exam - Study Guide

📋 Course Structure


code
📚 Data Structures and Algorithms
├── 📖 Chapter 1: Bubble Sort
│   ├── 🔹 Bubble Sort Algorithm and Principle
│   ├── 🔹 Bubble Sort Pseudocode and Complexity
│   └── 🔹 Bubble Sort Stability
├── 📖 Chapter 2: Insertion Sort
│   ├── 🔹 Insertion Sort Algorithm and Principle
│   ├── 🔹 Insertion Sort Pseudocode and Complexity
│   └── 🔹 Insertion Sort Stability
├── 📖 Chapter 3: Quick Sort
│   ├── 🔹 Quick Sort Algorithm and Principle
│   ├── 🔹 Quick Sort Pseudocode and Complexity
│   └── 🔹 Quick Sort Stability
├── 📖 Chapter 4: Merge Sort
│   ├── 🔹 Merge Sort Algorithm and Principle
│   ├── 🔹 Merge Sort Pseudocode and Complexity
│   └── 🔹 Merge Sort Stability
└── 📖 Chapter 5: Radix Sort
    ├── 🔹 Radix Sort Algorithm and Principle
    ├── 🔹 Radix Sort Pseudocode and Complexity
    └── 🔹 Radix Sort Stability

Section 2

📖 Chapter 1: Bubble Sort

What this chapter covers: This chapter introduces the Bubble Sort algorithm, explaining its basic principle of repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. It covers the algorithm's stability, pseudocode, time and space complexity, and provides examples to illustrate the sorting process. Bubble sort is a comparison sort known for its simplicity, though it is inefficient for large datasets.

🔑 Essential Concepts & Formulas

Concept/Formula	Definition/Equation	When to Use	Quick Check
Basic Principle	Pairwise comparison and swap of adjacent elements.	Sorting small lists.	Check if largest element "bubbles" to the end in each pass.
Time Complexity (Worst/Avg)	$O(n^2)$	Unsorted or reverse-sorted lists.	Verify number of comparisons grows quadratically with input size.
Time Complexity (Best)	$O(n)$	Already sorted list.	Check if only one pass is needed with no swaps.
Space Complexity	$O(1)$	When memory usage is a concern.	Confirm it sorts in place without auxiliary data structures.
Stability	Stable	When maintaining the original order of equal elements is important.	Verify that equal elements retain their original order after sorting.

🛠️ Problem Types

Type A: Sorting a List of Numbers

Setup: "When you encounter a list of numbers that need to be sorted in ascending order using Bubble Sort."

Method: Iterate through the list multiple times, comparing adjacent elements and swapping them if they are in the wrong order. Repeat until no more swaps are needed.

Example: Sort the list: 5, 1, 4, 2, 8.

First Pass: (5, 1, 4, 2, 8) $\to$ (1, 5, 4, 2, 8) $\to$ (1, 4, 5, 2, 8) $\to$ (1, 4, 2, 5, 8) $\to$ (1, 4, 2, 5, 8)
Second Pass: (1, 4, 2, 5, 8) $\to$ (1, 4, 2, 5, 8) $\to$ (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8)
Third Pass: (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8) Sorted List: 1, 2, 4, 5, 8

Type B: Determining the Number of Passes

Setup: "If presented with a list and asked to determine the number of passes required to sort it using Bubble Sort."

Method: Perform Bubble Sort and count the number of times the outer loop iterates until no swaps occur in a pass.

Example: How many passes are required to sort the list: 3, 2, 1?

First Pass: (3, 2, 1) $\to$ (2, 3, 1) $\to$ (2, 1, 3)
Second Pass: (2, 1, 3) $\to$ (1, 2, 3) $\to$ (1, 2, 3) Two passes are required.

🧮 Solved Example

Problem: Sort the array [5, 1, 4, 2, 8] using Bubble Sort.

Given: Array: [5, 1, 4, 2, 8]

Steps:

First Pass: Compare and swap adjacent elements:
- (5, 1, 4, 2, 8) $\to$ (1, 5, 4, 2, 8)
- (1, 5, 4, 2, 8) $\to$ (1, 4, 5, 2, 8)
- (1, 4, 5, 2, 8) $\to$ (1, 4, 2, 5, 8)
- (1, 4, 2, 5, 8) $\to$ (1, 4, 2, 5, 8)
Second Pass:
- (1, 4, 2, 5, 8) $\to$ (1, 4, 2, 5, 8)
- (1, 4, 2, 5, 8) $\to$ (1, 2, 4, 5, 8)
- (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8)
- (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8)
Third Pass:
- (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8)
- (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8)
- (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8)
- (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8)

"

✅
Answer: Sorted array: [1, 2, 4, 5, 8]

⚠️ Common Mistakes

❌ Mistake 1: Incorrectly swapping elements during comparison.

✅ How to avoid: Double-check the comparison and ensure elements are swapped correctly to move larger elements towards the end.

❌ Mistake 2: Not optimizing for already sorted lists, leading to unnecessary passes.

✅ How to avoid: Implement a flag to check if any swaps occur during a pass. If no swaps occur, the list is sorted.

💡 Study Tip

Visualize the "bubbling" effect by manually tracing the algorithm on small lists. This helps understand how larger elements move towards their correct positions.

📖 Chapter 2: Insertion Sort

What this chapter covers: This chapter introduces the Insertion Sort algorithm, explaining how it works by iteratively building a sorted sublist. It covers the algorithm's stability, pseudocode, time and space complexity, and provides examples to illustrate the sorting process. Insertion sort is efficient for small datasets or nearly sorted data.

🔑 Essential Concepts & Formulas

Concept/Formula	Definition/Equation	When to Use	Quick Check
Basic Principle	Iteratively build a sorted sublist by inserting elements into their correct position.	Sorting small lists or nearly sorted lists.	Verify that the left portion of the array is always sorted.
Time Complexity (Worst/Avg)	$O(n^2)$	Unsorted or reverse-sorted lists.	Confirm number of comparisons grows quadratically with input size.
Time Complexity (Best)	$O(n)$	Already sorted list.	Check if only one pass is needed with minimal comparisons.
Space Complexity	$O(1)$	When memory usage is a concern.	Confirm it sorts in place without auxiliary data structures.
Stability	Stable	When maintaining the original order of equal elements is important.	Verify that equal elements retain their original order after sorting.

🛠️ Problem Types

Type A: Sorting a List of Numbers

Setup: "When you encounter a list of numbers that need to be sorted in ascending order using Insertion Sort."

Method: Iterate through the list, picking one element at a time and inserting it into the correct position in the sorted sublist.

Example: Sort the list: 5, 1, 4, 2, 8.

(5, 1, 4, 2, 8) $\to$ (1, 5, 4, 2, 8)
(1, 5, 4, 2, 8) $\to$ (1, 4, 5, 2, 8)
(1, 4, 5, 2, 8) $\to$ (1, 2, 4, 5, 8)
(1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8) Sorted List: 1, 2, 4, 5, 8

Type B: Identifying the Sorted Sublist

Setup: "If presented with a partially sorted list and asked to identify the sorted sublist at a particular step in Insertion Sort."

Method: Trace the execution of Insertion Sort and identify the portion of the list that is sorted at each step.

Example: What is the sorted sublist after the second iteration of Insertion Sort on the list: 3, 2, 1, 4?

(3, 2, 1, 4) $\to$ (2, 3, 1, 4)
(2, 3, 1, 4) $\to$ (1, 2, 3, 4) Sorted sublist after the second iteration: 1, 2, 3

🧮 Solved Example

Problem: Sort the array [5, 1, 4, 2, 8] using Insertion Sort.

Given: Array: [5, 1, 4, 2, 8]

Steps:

First Iteration:
- (5, 1, 4, 2, 8) $\to$ (1, 5, 4, 2, 8)
Second Iteration:
- (1, 5, 4, 2, 8) $\to$ (1, 4, 5, 2, 8)
Third Iteration:
- (1, 4, 5, 2, 8) $\to$ (1, 2, 4, 5, 8)
Fourth Iteration:
- (1, 2, 4, 5, 8) $\to$ (1, 2, 4, 5, 8)

"

✅
Answer: Sorted array: [1, 2, 4, 5, 8]

⚠️ Common Mistakes

❌ Mistake 1: Incorrectly shifting elements during insertion.

✅ How to avoid: Ensure elements are shifted correctly to make space for the element being inserted.

❌ Mistake 2: Not handling the case where the element being inserted is smaller than all elements in the sorted sublist.

✅ How to avoid: Ensure the element is inserted at the beginning of the sorted sublist if it is the smallest.

💡 Study Tip

Use physical cards to simulate the insertion process. This helps visualize how elements are moved to their correct positions in the sorted sublist.

📖 Chapter 3: Quick Sort

What this chapter covers: This chapter introduces the Quick Sort algorithm, explaining its divide-and-conquer approach. It covers the algorithm's pseudocode, time and space complexity, stability, and provides examples to illustrate the sorting process. Quick sort is known for its efficiency on average but can degrade to $O(n^2)$ in the worst case.

🔑 Essential Concepts & Formulas

Concept/Formula	Definition/Equation	When to Use	Quick Check
Basic Principle	Divide-and-conquer algorithm using a pivot to partition the array.	Sorting large lists efficiently (on average).	Verify that elements smaller than the pivot are to its left, and larger elements are to its right.
Time Complexity (Avg/Best)	$O(n \log n)$	Randomly ordered lists.	Check if the number of comparisons grows logarithmically with input size.
Time Complexity (Worst)	$O(n^2)$	Already sorted or reverse-sorted lists (with poor pivot choice).	Confirm number of comparisons grows quadratically with input size in worst-case scenarios.
Space Complexity	$O(\log n)$ (average)	When memory usage is a concern.	Confirm it uses a logarithmic amount of stack space due to recursion.
Stability	Unstable	When maintaining the original order of equal elements is not important.	Verify that equal elements may not retain their original order after sorting.

🛠️ Problem Types

Type A: Sorting a List of Numbers

Setup: "When you encounter a list of numbers that need to be sorted in ascending order using Quick Sort."

Method: Choose a pivot, partition the array around the pivot, and recursively apply Quick Sort to the sub-arrays.

Example: Sort the list: 7, 2, 1, 6, 8, 5, 3, 4 using the last element as the pivot.

Type B: Pivot Selection Strategies

Setup: "If presented with a list and asked to analyze the impact of different pivot selection strategies on the performance of Quick Sort."

Method: Compare the number of comparisons and swaps required for different pivot selection strategies (e.g., first element, last element, random element, median-of-three).

Example: Compare the performance of Quick Sort using the first element vs. the median-of-three as the pivot on the list: 1, 2, 3, 4, 5, 6, 7.

🧮 Solved Example

Problem: Sort the array [7, 2, 1, 6, 8, 5, 3, 4] using Quick Sort with the last element as the pivot.

Given: Array: [7, 2, 1, 6, 8, 5, 3, 4]

Steps:

First Partition (pivot = 4):
- [7, 2, 1, 6, 8, 5, 3, 4] $\to$ [2, 1, 3, 6, 8, 5, 7, 4]
Recursive calls on sub-arrays:
- [2, 1, 3] and [6, 8, 5, 7]
Continue partitioning and recursive calls until sorted.

"

✅
Answer: Sorted array: [1, 2, 3, 4, 5, 6, 7, 8]

⚠️ Common Mistakes

❌ Mistake 1: Choosing a poor pivot, leading to $O(n^2)$ time complexity.

✅ How to avoid: Use pivot selection strategies like random pivot or median-of-three to avoid worst-case scenarios.

❌ Mistake 2: Incorrectly partitioning the array around the pivot.

✅ How to avoid: Carefully compare elements with the pivot and swap them correctly to ensure elements smaller than the pivot are to its left, and larger elements are to its right.

💡 Study Tip

Practice partitioning the array manually with different pivot choices to understand how the pivot affects the sorting process.

4 more sections

Create a free account to import and read the full study notes — all 6 sections.

No credit card · 2 free imports included

Sorting Algorithms Exam - Cheatsheet 2

Study Notes Preview

Sorting Algorithms Exam - Cheatsheet 2

🎓 Sorting Algorithms Exam - Study Guide

📋 Course Structure

📖 Chapter 1: Bubble Sort

🔑 Essential Concepts & Formulas

🛠️ Problem Types

🧮 Solved Example

⚠️ Common Mistakes

💡 Study Tip

📖 Chapter 2: Insertion Sort

🔑 Essential Concepts & Formulas

🛠️ Problem Types

🧮 Solved Example

⚠️ Common Mistakes

💡 Study Tip

📖 Chapter 3: Quick Sort

🔑 Essential Concepts & Formulas

🛠️ Problem Types

🧮 Solved Example

⚠️ Common Mistakes

💡 Study Tip

4 more sections