CSE 332 Section 6�Sorting

Original slides by James Richie Sulaeman

Revised by Rubee Zhao & Vicky Ye

Properties: How to choose sorting method?

• Comparison-based / non-comparison-based: <, >, =
• Stable: preserve the given order if =
• In-place: no need for extra data structure to store values
• Online: begin with an incomplete list
• Adaptive: better running time for nearly sorted input
• Running Time 🏃🕙

​

​

Comparison-based Sorting

Insertion Sort

Insertion sort builds a sorted subarray at the front of the original array. Takes the first element of the unsorted subarray and inserts it into the sorted subarray.

Properties:

• In-place and stable
• Best-case runtime: O(n)
• Worst-case runtime: O(n²)

Selection Sort

Selection sort builds a sorted subarray at the front of the original array. Takes the first element of the unsorted subarray and swaps it into the correct location at the end of the sorted subarray.

Properties:

• In-place and not usually stable
• Can be made stable if you shift instead of swapping and break ties by selecting the left-most element
• Best-case runtime: O(n²)
• Worst-case runtime: O(n²)

Merge Sort

Merge sort recursively splits an array into two halves, sorts them, and then merges them back together to obtain a sorted array.

Properties:

• Not in-place but stable
• Best-case runtime: O(n log n)
• Worst-case runtime: O(n log n)

mergeSort(input) -> sorted input:

1. sortedLeft = mergeSort(left half of input)

2. sortedRight = mergeSort(right half of input)

3. return (merged ‘sortedLeft’ and ‘sortedRight’)

Quick Sort

Quick sort recursively partitions an array based on a pivot element, sorts the subarrays on either side of the pivot, and merges them back together to obtain a sorted array.

Properties:

• In-place but not stable.
• Best-case runtime: O(n log n)
• Worst-case runtime: O(n²)

quickSort(input) -> void:

1. pick pivot

2. partition input into ‘lessThanPivot’ and

‘greaterThanPivot’ parts

3. quickSort(lessThanPivot)

4. quickSort(greaterThanPivot)

Problem 0

Problem 0

Suppose we sort an array of numbers, but it turns out every element of the array is the same (e.g. [17, 17, 17, …, 17]).

What is the asymptotic runtime of the following sorting algorithms?

​

Problem 0

Suppose we sort an array of numbers, but it turns out every element of the array is the same (e.g. [17, 17, 17, …, 17]).

What is the asymptotic runtime of the following sorting algorithms?

​

Problem 0: Solution

Problem 0: Solution

Problem 1

Problem 1

Given an array of integers as such: {11, 13, 55, 67, 79, 10, 8, 6, 4, 2}. Please answer the following questions (assume all sorts to be done in ascending order):

What is the asymptotic runtime of the following sorting algorithms?

Here, assume we choose the leftmost element as the pivot each time for QS.

Problem 1

Given an array of integers as such: {11, 13, 55, 67, 79, 10, 8, 6, 4, 2}.

Please answer the following questions (assume all sorts to be done in

ascending order):

What is the asymptotic runtime of the following sorting algorithms?

Here, assume we choose the leftmost element as the pivot each time for QS.

Non-Comparison Sorting

Bucket Sort

Distributes elements into their corresponding buckets. Buckets have an inherent ordering and are merged together in this ordering to produce the sorted array.

Properties:

• Not in-place but stable
• Runtime: O(n + B)
• Need to iterate over n elements and B buckets.
• Good when B << n or B ≈ n.
• Bad when B >> n.

bucketSort(input) -> sorted input:

1. create array of size B

2. put each element into their corresponding bucket

3. generate sorted array by iterating through the

buckets in order

Original Input:�[5₁, 1₁, 3₁, 4₁, 3₂, 2, 1₂, 1₃, 5₂, 4₂, 5₃]

Final output:

[1₁, 1₂, 1₃, 2, 3₁, 3₂, 4₁, 4₂, 5₁, 5₂, 5₃]

B: 5

Radix Sort - 1’s Digit

Radix Sort repeatedly runs bucket sort on the elements for each significant digit, from least significant to most significant.

Original input: [478, 537, 9, 721, 3, 38, 143, 67], b: 10

Bucket Sort on 1’s Digit

radixSort(input) -> sorted input:

1. create array of size b

2. for each significant digit:

3. run bucket sort on the elements using their

corresponding significant digit values

Bucket Sort on 10’s Digit

Radix Sort - 10’s Digit

Radix Sort repeatedly runs bucket sort on the elements for each significant digit, from least significant to most significant.

Original input: [478, 537, 9, 721, 3, 38, 143, 67], b: 10

Bucket Sort on 10’s Digit

radixSort(input) -> sorted input:

1. create array of size b

2. for each significant digit:

3. run bucket sort on the elements using their

corresponding significant digit values

• Notice how elements are now sorted with respect to their last two digits.
• By running bucket sort from the least to the most significant digit, the order of the more significant digits take precedence over the less significant digits.

Radix Sort - 100’s Digit

Radix Sort repeatedly runs bucket sort on the elements for each significant digit, from least significant to most significant.

Original input: [478, 537, 9, 721, 3, 38, 143, 67], b: 10

Bucket Sort on 10’s Digit

Bucket Sort on 100’s Digit

Radix Sort - Final Output

Radix Sort repeatedly runs bucket sort on the elements for each significant digit, from least significant to most significant.

Original input: [478, 537, 9, 721, 3, 38, 143, 67], b: 10

Bucket Sort on 100’s Digit

• Not in-place but stable
• Runtime: O(p(n + b))
• Bucket sort has O(n + b) runtime, and we’re running it p = log_b(max(n)) times.

Problem 2

Decision Tree

Decision Tree: Quick Introduction

• A decision tree is a tree-like model representing all possible decisions or comparisons in a process.
• Nodes: points where a comparison or decision is made.
• Branches: possible outcomes of that comparison.
• Leaves: final outcomes after all decisions.
• Useful for visualizing sorting, searching, or algorithm paths.

Decision Tree Example

a<b<c; a<c<b; b<a<c; b<c<a; c<b<a; c<a<b

a<b<c; a<c<b; c<a<b

b<a<c; b<c<a; c<b<a

Ask: is a < b?

a<b<c

a<c<b; c<a<b

b<a<c

b<c<a; c<b<a

a<c<b

c<a<b

b<c<a

c<b<a

Ask: is b<c?

Ask: is a<c?

Ask: is a<c?

Ask: is b<c?

yes

no

yes

no

yes

no

yes

no

yes

no

Decision Tree Example

Thank You!