11.

Sorting
Data Structures and Algorithms EEE2020-01
Prof. Jongyoo Kim
 Sorting
§ In computer science, a sorting algorithm arranges the elements of a list into a specific order.
• This process reduces the complexity of various problems.

§ Applications
• Arranging datasets for printing in a desired order.
• Efficiently retrieving the k-th smallest or k-th largest element in O(1) time after sorting.
• Facilitating efficient searching in large datasets using algorithms like Binary Search, which
requires sorted data. Thus, sorting becomes crucial.
• Serving as a fundamental step in solving more advanced problems in both software
development and conceptual problem-solving.

Multimedia AI Lab. 2
 Key Properties
q Stability:
§ A sorting algorithm is stable if it:
• Preserves the relative order of records with equal keys (values).
• Maintains the original order of equal elements in the sorted output.
• Important when the original order of equal elements has meaning.

3 2 (a) 2 (b) 1 1 2 (a) 2 (b) 3

q In-place Sorting:
§ An in-place sorting algorithm:
• Requires minimal extra memory space beyond the original input.
• Typically uses O(1) or O(logn) auxiliary space (for recursive calls).
• Does not create copies of the input or use temporary arrays proportional to the input size.

Multimedia AI Lab. 3
 Types of Sorting Techniques
q Comparison-based:
§ Algorithms that rely on comparisons
between elements to determine their order.

q Non-comparison-based:
§ Algorithms that do not compare elements
but use other properties of the data to sort.

Multimedia AI Lab. 4
 Contents
q Bubble Sort
q Selection Sort
q Insertion Sort
q Merge Sort
q Quick Sort
q Radix Sort

Multimedia AI Lab. 5
Bubble Sort
 Bubble Sort
§ One of the simplest comparison-based sorting algorithms.
§ Repeatedly compares and swaps adjacent elements to bubble larger values to the end of the
list.

q Procedure:
§ Start at the beginning of the array.
§ Compare each pair of adjacent elements.
§ If they are in the wrong order, swap them.
§ Repeat for each pair until the end of the array.
§ Continue passes until no swaps are needed.

Multimedia AI Lab. 7
 Bubble Sort
q Example

Step 1

3 2 4 1
Step 1 3 2 4 1 2 3 4 1
2 3 1 4
Step 2 2 3 4 1 2 3 4 1
2 1 3 4
Step 3
2 3 4 1 2 3 1 4
1 2 3 4
Result 2 3 1 4

Multimedia AI Lab. 8
 Bubble Sort
q Example

Step 2

3 2 4 1
Step 1 2 3 1 4 2 3 1 4
2 3 1 4
Step 2
2 3 1 4 2 1 3 4
2 1 3 4
Step 3

1 2 3 4 Result 2 1 3 4

Multimedia AI Lab. 9
 Bubble Sort
q Example

Step 3

3 2 4 1
Step 1
2 1 3 4 1 2 3 4
2 3 1 4
Step 2

2 1 3 4
Step 3
Result 1 2 3 4
1 2 3 4

Multimedia AI Lab. 10
 Bubble Sort
q Implementation

Multimedia AI Lab. 11
 Bubble Sort
q Implementation
§ Add termination condition check

Multimedia AI Lab. 12
 Bubble Sort
q Time Complexity:
§ Best: Ω 𝑛 (when the list is already sorted)
§ Average: 𝑂 𝑛!
§ Worst: 𝑂 𝑛! (when the list is in reverse order)

q Space Complexity:
§ 𝑂 1

q Stability: Stable
q In-place?: Yes.

Multimedia AI Lab. 13
 Bubble Sort
q Advantages:
§ Simple to understand and implement.
§ Requires no significant additional memory space (in-place).
§ Stable sorting algorithm.

q Disadvantages:
§ Very slow for large datasets.

Multimedia AI Lab. 14
Selection Sort
 Selection Sort
§ Repeatedly selects the smallest element from the unsorted portion and places it at the
beginning.

q Procedure
§ Start with the first element as the minimum.
§ Scan the unsorted portion to find the smallest element.
§ Swap the smallest element with the first unsorted element.
§ Move the boundary of the sorted portion one element forward.
§ Repeat until the entire array is sorted.

Multimedia AI Lab. 16
 Selection Sort
q Example
§ Naïve way 3 2 4 1
• Additional space
needed 3 2 4 1

3 4 1 2

4 1 2 3

1 2 3 4

Multimedia AI Lab. 17
 Selection Sort
q Example
§ Improved version! 3 2 4 1
• In-place swap

3 2 4 1 1 2 4 3

1 2 4 3 1 2 4 3

1 2 4 3 1 2 3 4

Multimedia AI Lab. 18
 Selection Sort
q Implementation

Multimedia AI Lab. 19
 Selection Sort
q Time Complexity
§ Best: Ω 𝑛!
§ Average: 𝑂 𝑛!
§ Worst: 𝑂 𝑛!

q Space Complexity
§ 𝑂 1

q Stability: Unstable
q In-place?: Yes

Multimedia AI Lab. 20
 Selection Sort
q Advantages:
§ Simple to understand and implement.
§ Performs a minimal number of swaps.

q Disadvantages:
§ Inefficient for large datasets.
§ Not stable.

Multimedia AI Lab. 21
Insertion Sort
 Insertion Sort
§ Builds a sorted array by inserting each element into its correct position in the sorted portion.

q Procedure:
§ Consider the first element as the sorted portion.
§ Take the next element from the unsorted portion.
§ Shift elements in the sorted portion to make space for the new element.
§ Insert the new element in its correct position.
§ Repeat until all elements are processed.

Multimedia AI Lab. 23
 Insertion Sort
q Example
Step 1
5 3 2 4 1

Step 1
5 3 2 4 1
3 5 2 4 1

Step 2 3

2 3 5 4 1 5 2 4 1

Step 3
3
2 3 4 5 1
3 5 2 4 1
Step 4

1 2 3 4 5

Multimedia AI Lab. 24
 Insertion Sort
q Example
Step 2
5 3 2 4 1

Step 1 3 5 2 4 1

3 5 2 4 1
2
Step 2
3 5 4 1
2 3 5 4 1
Step 3
2
2 3 4 5 1 3 5 4 1
Step 4

1 2 3 4 5 2
2 3 5 4 1

Multimedia AI Lab. 25
 Insertion Sort
q Exmaple Step 3

5 3 2 4 1 2 3 5 4 1

Step 1

3 5 2 4 1 4

Step 2 2 3 5 1

2 3 5 4 1
Step 3 4

2 3 4 5 1 2 3 5 1

Step 4

1 2 3 4 5 4
2 3 4 5 1

Multimedia AI Lab. 26
 Insertion Sort
Step 4

q Example 2 3 4 5 1
5 3 2 4 1 1
Step 1 2 3 4 5
3 5 2 4 1
1
Step 2
2 3 4 5
2 3 5 4 1
1
Step 3
2 3 4 5
2 3 4 5 1
1
Step 4
2 3 4 5
1 2 3 4 5
1
1 2 3 4 5
Multimedia AI Lab. 27
 Insertion Sort
q Implementation

Multimedia AI Lab. 28
 Insertion Sort
q Time Complexity:
§ Best: Ω 𝑛 (when the list is already sorted)
§ Average: 𝑂 𝑛!
§ Worst: 𝑂 𝑛! (when the list is in reverse order)

q Space Complexity:
§ 𝑂 1

q Stability: Stable
q In-place?: Yes

Multimedia AI Lab. 29
 Insertion Sort
q Advantages:
§ Simple to understand and implement.
§ Efficient for small lists and nearly sorted lists (adaptive).
§ Stable.
§ In-place.

q Disadvantages:
§ Inefficient for large unsorted datasets.

Multimedia AI Lab. 30
Merge Sort
 Merge Sort
§ Divides the array into smaller subarrays, sorts them, and merges them back into a sorted
array.
• Divide-and-conquer approach

q Procedure
§ Divide the array into two halves.
§ Recursively sort each half.
§ Merge the sorted halves:
• Compare elements from both halves.
• Place smaller elements into a result array.
• Continue until all elements are merged.
§ Repeat until the entire array is sorted.

Multimedia AI Lab. 32
 Merge Sort
q Overview
8 2 3 7 1 5 4 6

8 2 3 7 1 5 4 6
Divide
8 2 3 7 1 5 4 6

8 2 3 7 1 5 4 6

8 2 3 7 1 5 4 6

2 8 3 7 1 5 4 6
Merge
2 3 7 8 1 4 5 6

1 2 3 4 5 6 7 8

Multimedia AI Lab. 33
 Merge Sort
q Details for one merge step
• Compare the values at the current indices of both sequences.
2 3 7 8 1 4 5 6 • Place the smaller value into the merged array and increment the
index of its sequence.
L R

2 3 7 8 4 5 6

L R

1
3 7 8 4 5 6
Repeat until one sequence is empty.
L R …
1 2 7 8

L R

1 2 3 4 5 6

L R Append any remaining values from the non-empty

sequence to the merged array to complete the sorting.
1 2 3 4 5 6 7 8
Multimedia AI Lab. 34
 Merge Sort
q Implementation

Multimedia AI Lab. 35
 Merge Sort
q Time Complexity:
§ Best: Ω 𝑛 log 𝑛
§ Average: 𝑂 𝑛 log 𝑛
§ Worst: 𝑂 𝑛 log 𝑛

q Space Complexity:
§ 𝑂 𝑛

q Stability: Stable
q In-place?: No
§ (typically requires extra space for merging)

Multimedia AI Lab. 36
 Merge Sort
q Advantages:
§ Efficient for large datasets.
§ Stable.
§ Well-suited for external sorting.

q Disadvantages:
§ Requires extra memory space.

Multimedia AI Lab. 37
Quick Sort
 Quick Sort
§ Picks a pivot, partitions the array around it, and recursively sorts the subarrays.

q Procedure
§ Choose a pivot (e.g., first or last element).
§ Partition the array:
• Move elements smaller than the pivot to the left.
• Move elements larger than the pivot to the right.
• Place the pivot in its final position.
§ Recursively apply steps to the left and right subarrays.
§ Continue until subarrays have one or fewer elements.

Multimedia AI Lab. 39
 Quick Sort
q Partition function
§ Rearranging a sub-array around a chosen pivot element.
§ It returns the final index of the pivot after the partitioning is complete.

q Lomuto Partition Scheme

§ A relatively simple and easy-to-understand method for partitioning.

q Hoare's Partition Scheme

§ Often more efficient (performs fewer swaps)
§ It uses two pointers that move towards each other from the opposite ends

Multimedia AI Lab. 40
 Quick Sort – Lomuto Partition
q Initialization

i j pivot

5 3 8 4 9 1 6 2 7
low high

§ Parameters:
• pivot : typically the last element.
• low : start of the subarray being partitioned.
• high : end of the subarray being partitioned.
• i : low - 1
• j : low

Multimedia AI Lab. 41
 Quick Sort – Lomuto Partition
q Example
i j pivot i,j pivot

5 3 8 4 9 1 6 2 7 arr[j] < pivot → 5 3 8 4 9 1 6 2 7

i j i,j

5 3 8 4 9 1 6 2 7 arr[j] < pivot → 5 3 8 4 9 1 6 2 7

i j

5 3 8 4 9 1 6 2 7 j .

i j i j

5 3 8 4 9 1 6 2 7 arr[j] < pivot → 5 3 4 8 9 1 6 2 7

i j

5 3 4 8 9 1 6 2 7

Multimedia AI Lab. 42
 Quick Sort – Lomuto Partition
q Example
i j pivot i j pivot

5 3 4 8 9 1 6 2 7 arr[j] < pivot → 5 3 4 1 9 8 6 2 7

i j i j

5 3 4 1 9 8 6 2 7 arr[j] < pivot → 5 3 4 1 6 8 9 2 7

i j i j

5 3 4 1 6 8 9 2 7 arr[j] < pivot → 5 3 4 1 6 2 9 8 7

i j

5 3 4 1 6 2 9 8 7 j == high → 5 3 4 1 6 2 7 8 9
Place pivot in the correct position

Multimedia AI Lab. 43
 Quick Sort – Lomuto Partition
q Example
5 3 4 1 6 2 7 8 9
pivot Divide into two

5 3 4 1 6 2 8 9
Partition
1 2 4 5 6 3 8 9
Divide into two
1 4 5 6 3 8
Partition
3 5 6 4

Divide into two

Final: …
1 2 3 4 5 6 7 8 9
Multimedia AI Lab. 44
 Quick Sort – Hoare’s Partition
q Initialization

low high

5 3 8 4 9 1 6 2 7
i pivot j

§ Parameters:
• pivot : typically the first element
• low : start of the subarray being partitioned.
• high : end of the subarray being partitioned.
• i : low - 1
• j : high + 1

Multimedia AI Lab. 45
 Quick Sort – Hoare’s Partition
q Example Pivot value = 5
i j i j

5 3 8 4 9 1 6 2 7 i < j → 2 3 8 4 9 1 6 5 7

i j i j

2 3 8 4 9 1 6 5 7 i < j → 2 3 1 4 9 8 6 5 7

j i

2 3 1 4 9 8 6 5 7 i >= j → return j

Multimedia AI Lab. 46
 Quick Sort – Hoare’s Partition
q Example
2 3 1 4 9 8 6 5 7
Divide into two

Pivot value = 2 2 3 1 4 9 8 6 5 7 Pivot value = 9

Partition
1 3 2 4 7 8 6 5 9
Divide into two
1 3 2 4 7 8 6 5 9
Partition
2 3 4 5 6 8 7

Divide into two

Final: 1 2 3 4 5 6 7 8 9 …

Multimedia AI Lab. 47
 Quick Sort
q Implementation

Multimedia AI Lab. 48
 Quick Sort
q Time Complexity:
§ Best: Ω 𝑛 log 𝑛
§ Average: 𝑂 𝑛 log 𝑛
§ Worst: 𝑂 𝑛! (if the pivot selection is consistently poor)

q Space Complexity:
§ 𝑂 log 𝑛 (average, due to recursion depth)
§ 𝑂 𝑛 (worst)

q Stability: Unstable (typically)

q In-place?: Yes
§ (with careful implementation of the partitioning step)

Multimedia AI Lab. 49
 Quick Sort
q Advantages:
§ Generally very fast in practice (average case).
§ Low overhead.
§ Can be implemented in-place.

q Disadvantages:
§ Worst-case time complexity can be 𝑂 𝑛! .
§ Typically not stable.

Multimedia AI Lab. 50
Radix Sort
 Radix Sort
§ Radix sort is a non-comparative integer sorting algorithm.
§ The sorting order is not determined by comparing the data
§ However, applicable data is very restricted
• It is easy to sort data that has the same length

“In ascending order, sort the numbers 1, 7, 9, 5, 2 and 6!”

“In dictionary order, sort the words, red, why, zoo and box!”
=> Radix sort is applicable!

“In ascending order, sort the numbers, 21, -9, 125, 8, -136 and 45!”
“In dictionary order, sort the words, professionalism, few, hydroxyproline and simple!”
=> Radix sort is not applicable!

Multimedia AI Lab. 52
 Radix Sort
q Principle of Radix Sorting
§ When sorting the data, there is no comparison between the data because the data simply
goes in and out of the bucket
Bucket 0

Bucket 1

Bucket 2
Save according to value Take out in order
Bucket 3

Bucket 4

Bucket 5

Bucket 6

Bucket 7

Bucket 8

Bucket 9
Multimedia AI Lab. 53
 Radix Sort
q Counting Sort
§ A non-comparison-based sorting algorithm. It is particularly efficient when the range of
input values is small compared to the number of elements to be sorted.
§ 𝑂 𝑛 + 𝑘 , Stable
• where 𝑛 is the number of inputs, 𝑘 is the size of count array
§ Example
• [3 0 5 1 0 5]

Count array

Count array
(after cumulation)
Count array
Output array
(after -1)
Multimedia AI Lab. 54
 Radix Sort
q Counting Sort Implementation

Multimedia AI Lab. 55
 Radix Sort
q Least Significant Digit
§ Sort the lowest digit
§ The data is sorted until the highest digit is sorted

1 3 4 2 3 2 1 2 2 1 2 2
2 2 4 1 2 2 2 2 4 1 3 4
2 3 2 1 3 4 2 3 2 2 2 4
1 2 2 2 2 4 1 3 4 2 3 2

Multimedia AI Lab. 56
 Radix Sort
q Most Significant Digit
§ Sort the data on the contrary to the sorting direction of LSD
§ The data completely sorted has to be distinguished from the data unsorted

1 3 4 1 3 4 1 2 2 1 2 2
2 2 4 1 2 2 2 2 4 2 3 2
2 3 2 2 2 4 1 3 4 2 2 4 ?
1 2 2 2 3 2 2 3 2 1 3 4

Sorting is not necessary anymore!

Multimedia AI Lab. 57
 Radix Sort
q Most Significant Digit
§ Sort the data on the contrary to the sorting direction of LSD
§ The data completely sorted has to be distinguished from the data unsorted

1 3 4 1 3 4 1 2 2
2 2 4 1 2 2 1 3 4
2 3 2 2 2 4 2 2 4
1 2 2 2 3 2 2 3 2

Sort the list of elements based on that digit,

grouping elements with the same digit into one bucket.
Multimedia AI Lab. 58
 Radix Sort
q LSD and MSD
§ In LSD, every data is sorted equally
§ On the other hand, the process ,that the sorted data has to be distinguished from the
unsorted data, is necessary in MSD
§ Therefore, LSD is easy to implement and its performance is not bad compared to MSD

1st digit from NUM: NUM / 1 % 10

2nd digit from NUM : NUM / 10 % 10
3rd digit from NUM NUM : / 100 % 10

Example implementation of LSD algorithm

Multimedia AI Lab. 59
 Radix Sort
q Implementation

Multimedia AI Lab. 60
 Radix Sort
q Time Complexity
§ 𝑂 𝑑⋅ 𝑛+𝑏
• where 𝑑 is the number of digits, 𝑛 is the number of elements, and 𝑏 is the base

q Space Complexity
§ 𝑂 𝑛+𝑏
• Additional space is required for the temporary array used during merging.

q Stability: Stable
§ (if the underlying sorting algorithm for digits is stable)

q In-place?: No

Multimedia AI Lab. 61
 Radix Sort
q Advantages:
§ Can achieve linear time complexity in certain cases.
§ Efficient for sorting integers or fixed-length strings.
§ Can be stable.

q Disadvantages:
§ Primarily applicable to integers or data that can be treated as sequences of fixed-size pieces.
§ Space complexity can be higher than in-place sorts.
§ Performance depends on key length and radix.

Multimedia AI Lab. 62
 Recap: Heap Sorting
§ Build a min heap from the input data.
§ Insert the array to the heap
§ While the min heap is not empty:
• Remove the minimum element from
the heap.

§ Big O Complexity:
• 𝑂 𝑛 log 𝑛

Multimedia AI Lab. 63
 Recap: Heap Sorting
q Actual implementation
§ No external min heap
§ In-place swap

Multimedia AI Lab. 64
 Summary

Time Complexity Time Complexity Time Complexity Space Complexity

Algorithm
Best Case Average Case Worst Case (Worst Case)

Bubble Sort Ω 𝑛 𝑂 𝑛! 𝑂 𝑛! 𝑂 1

Selection Sort Ω 𝑛! 𝑂 𝑛! 𝑂 𝑛! 𝑂 1

Insertion Sort Ω 𝑛 𝑂 𝑛! 𝑂 𝑛! 𝑂 1

Merge Sort Ω 𝑛 log 𝑛 𝑂 𝑛 log 𝑛 𝑂 𝑛 log 𝑛 𝑂 𝑛

𝑂 log 𝑛 (average),
Quick Sort Ω 𝑛 log 𝑛 𝑂 𝑛 log 𝑛 𝑂 𝑛!
𝑂 𝑛 (worst)

Heap Sort Ω 𝑛 log 𝑛 𝑂 𝑛 log 𝑛 𝑂 𝑛 log 𝑛 𝑂 1

Radix Sort Ω 𝑑⋅ 𝑛+𝑏 𝑂 𝑑⋅ 𝑛+𝑏 𝑂 𝑑⋅ 𝑛+𝑏 𝑂 𝑛+𝑏

Multimedia AI Lab. 65