CSE 373 SP25 Section AX Week 6
Sorting Algorithms
Leetcode Preview - Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Constraints:
1 <= nums.length <= 10^5
k is in the range [1, number of unique elements in the array]
It is guaranteed that the answer is unique (there is only one possible output)
💡Start thinking about how you would approach this problem💡
Exam Details
Micro-Teach: Sorting
Merge Sort
Merge Sort
needed to store the subarrays
during merging.
Quick Sort
Quick Sort
QuickSort
Counting Sort
Counting Sort
6
Radix Sort
Radix Sort
Sorting the integers according to units, tens, and hundreds place digits (LSD)
Radix Sort
In-Place vs. Out-of-Place Algorithms
An algorithm is considered in-place if it rearranges elements within the original data structure without requiring extra space proportional to the input size. It only uses a constant amount of extra memory (e.g., pointers, temporary variables)
In-Place vs. Out-of-Place Algorithms
An out-of-place algorithm requires extra space to store a copy of the input or intermediate results. The input array remains unchanged, and the output is written to a new array or data structure.
1. Sorting Hat
Suppose we sort an array of numbers, but it turns out every element of the array is the same, e.g., {13, 13, 13, …, 13}.
What is the asymptotic runtime for each sorting algorithm below? (in big-Θ notation)
1. Sorting Hat (Solution)
Suppose we sort an array of numbers, but it turns out every element of the array is the same, e.g., {13, 13, 13, …, 13}.
What is the asymptotic runtime for each sorting algorithm below? (in big-Θ notation)
2. PartitionHybridSort
Give the worst-case runtime for each of the function calls below. Give your answer as a function of N, the size of the input array (in big-Θ notation). Assume input=small integers
Explain how each subsort contributes to each of your runtimes.
// arr = array of integers
// lo = the lowest index in the array to be sorted
// hi = the highest index in the array to be sorted
// subsort = the sorting algorithm to use in Step 3
void PartitionHybridSort(arr, lo, hi, subsort) {
if (hi - lo <= 0) { // Step 1
return;
}
// Choose pivot element for partitioning, starting with arr[lo]
partition around arr[lo] of the current subproblem; // Step 2
// For future sorting runs, choose a new pivot element at index i (unknown)
sort the left from lo to i using subsort; // Step 3
sort the right from i + 1 to hi using subsort;
}
2. PartitionHybridSort (Solution)
PartitionHybridSort(arr, 0, N, InsertionSort) Θ( N2 )
All elements could be partitioned such that one of the partitions contains almost all the elements and the other contains a very small number of elements.
In this case, you run insertion sort on almost all elements, leading to quadratic runtime.
// arr = array of integers
// lo = the lowest index in the array to be sorted
// hi = the highest index in the array to be sorted
// subsort = the sorting algorithm to use in Step 3
void PartitionHybridSort(arr, lo, hi, subsort) {
if (hi - lo <= 0) { // Step 1
return;
}
// Choose pivot element for partitioning, starting with arr[lo]
partition around arr[lo] of the current subproblem; // Step 2
// For future sorting runs, choose a new pivot element at index i (unknown)
sort the left from lo to i using subsort; // Step 3
sort the right from i + 1 to hi using subsort;
}
2. PartitionHybridSort (Solution)
PartitionHybridSort(arr, 0, N, Mergesort) Θ( NlogN )
Step 2 results in linear runtime.
However, this is dominated by the log-linear runtime of merge sort.
// arr = array of integers
// lo = the lowest index in the array to be sorted
// hi = the highest index in the array to be sorted
// subsort = the sorting algorithm to use in Step 3
void PartitionHybridSort(arr, lo, hi, subsort) {
if (hi - lo <= 0) { // Step 1
return;
}
// Choose pivot element for partitioning, starting with arr[lo]
partition around arr[lo] of the current subproblem; // Step 2
// For future sorting runs, choose a new pivot element at index i (unknown)
sort the left from lo to i using subsort; // Step 3
sort the right from i + 1 to hi using subsort;
}
2. PartitionHybridSort (Solution)
PartitionHybridSort(arr, 0, N, CountingSort) Θ( N )
Since the inputs are small integers, CountingSort sorts the element in linear runtime.
Since step 2 also takes linear runtime, the combined worst-case runtime remains linear.
// arr = array of integers
// lo = the lowest index in the array to be sorted
// hi = the highest index in the array to be sorted
// subsort = the sorting algorithm to use in Step 3
void PartitionHybridSort(arr, lo, hi, subsort) {
if (hi - lo <= 0) { // Step 1
return;
}
// Choose pivot element for partitioning, starting with arr[lo]
partition around arr[lo] of the current subproblem; // Step 2
// For future sorting runs, choose a new pivot element at index i (unknown)
sort the left from lo to i using subsort; // Step 3
sort the right from i + 1 to hi using subsort;
}
2. PartitionHybridSort (Solution)
PartitionHybridSort(arr, 0, N, PartitionHybridSort) Θ( N2 )
Since the subsort is also PartitionHybridSort, this is just quicksort.
Worst case scenario is if our starting array is sorted highest to lowest when the end array we want is sorted from lowest to highest.
So the number of elements we have in our sub problem decreases by 1 each recursion (N-1) and we will have to recurse N times. T(N) = T(N-1) + N = Θ(N2).
// arr = array of integers
// lo = the lowest index in the array to be sorted
// hi = the highest index in the array to be sorted
// subsort = the sorting algorithm to use in Step 3
void PartitionHybridSort(arr, lo, hi, subsort) {
if (hi - lo <= 0) { // Step 1
return;
}
// Choose pivot element for partitioning, starting with arr[lo]
partition around arr[lo] of the current subproblem; // Step 2
// For future sorting runs, choose a new pivot element at index i (unknown)
sort the left from lo to i using subsort; // Step 3
sort the right from i + 1 to hi using subsort;
}
2. PartitionHybridSort (Solution Summary)
Give the worst-case runtime for each of the function calls below. Give your answer as a function of N, the size of the input array (in big-Θ notation). Assume input=small integers
Explain how each subsort contributes to each of your runtimes.
// arr = array of integers
// lo = the lowest index in the array to be sorted
// hi = the highest index in the array to be sorted
// subsort = the sorting algorithm to use in Step 3
void PartitionHybridSort(arr, lo, hi, subsort) {
if (hi - lo <= 0) { // Step 1
return;
}
// Choose pivot element for partitioning, starting with arr[lo]
partition around arr[lo] of the current subproblem; // Step 2
// For future sorting runs, choose a new pivot element at index i (unknown)
sort the left from lo to i using subsort; // Step 3
sort the right from i + 1 to hi using subsort;
}
Any Questions?
Code Challenges: Heaps/Hashing
Instructions
Each group of 3 or 4 students will be assigned the following problem:
Different Approaches to Use:
For instructions, search online for the problem by ID number, e.g. “LeetCode 347”.
We will have about 20 minutes for this activity:
NO NEED to write up code for this activity. Try to come up with solution approaches and how you would tackle the program on the high-level using specific data structures.
Different Approaches Available - Leetcode 347
Presentation Guidelines
Questions to Ask Yourself:
Presentation Guidelines
Complete the reflection activity in Gradescope and add your groupmates!
Example Solution 1 - LeetCode 347 (HashMap & Priority Queue)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> counter = new HashMap<>();
for (int n : nums) {
counter.put(n, counter.getOrDefault(n, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
(a, b) -> Integer.compare(b.getValue(), a.getValue())
);
for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
heap.offer(entry);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = Objects.requireNonNull(heap.poll()).getKey();
}
return res;
}
}
Example Solution 2 - LeetCode 347 (HashMap & Bucket-Sort)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> counter = new HashMap<>();
for (int n : nums) {
counter.put(n, counter.getOrDefault(n, 0) + 1);
}
List<Integer>[] freq = new ArrayList[nums.length + 1];
for (int i = 0; i < freq.length; i++) {
freq[i] = new ArrayList<>();
}
for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
int frequency = entry.getValue();
freq[frequency].add(entry.getKey());
}
int[] res = new int[k];
int idx = 0;
for (int i = freq.length - 1; i >= 0; i--) {
for (int num : freq[i]) {
res[idx++] = num;
if (idx == k) {
return res;
}
}
}
return new int[0];
}
}
Closing Announcements
Please don't hesitate to reach out if you have any
questions or concerns about the course, or if there's
anything else we can help you with! We're here to support
you however we can!