1 of 19

Sorting

CSE 332 – Section 6 (11/2/23)

Slides by James Richie Sulaeman

2 of 19

Announcements

  • P2 Checkpoint 2 due on Friday NEXT WEDNESDAY @ 11:59 PM
    • Maximum of 2 late days per checkpoint and 4 late days total per quarter
    • Checkpoints are only worth 1 point each
  • EX06 and EX07 also due next Wednesday @ 11:59 PM
    • No late days

3 of 19

Sorting

4 of 19

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.

  • In-place and stable.
  • Best case: O(n)
  • Worst case: O(n2)

Insertion Sort

3

2

11

12

Original Input:

3

2

11

12

Step 1:

2

3

11

12

Step 2:

11

2

3

12

Step 3:

11

12

2

3

Final output:

unsorted

curr elt

sorted

5 of 19

Builds a sorted subarray at the front of the original array. Takes the smallest element of the unsorted subarray and inserts it at the end of the sorted subarray.

  • In-place but not stable.
  • Best case: O(n2)
  • Worst case: O(n2)

Selection Sort

31

32

2

1

Original Input:

1

32

2

31

Step 1:

1

2

32

31

Step 2:

1

2

32

31

Step 3:

1

2

32

31

Final output:

sorted

unsorted

6 of 19

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

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

Merge Sort

mergeSort(input) -> sorted input:

1. sortedLeft = mergeSort(left half of input)

2. sortedRight = mergeSort(right half of input)

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

4

2

6

0

4

2

4

6

0

2

6

0

2

4

0

6

0

2

4

6

7 of 19

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.

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

Quick Sort

quickSort(input) -> void:

1. pick pivot

2. partition input into ‘lessThanPivot’ and

‘greaterThanPivot’ parts

3. quickSort(lessThanPivot)

4. quickSort(greaterThanPivot)

10

15

1

2

6

12

5

7

1

2

6

5

12

15

10

7

pivot

12

15

10

1

2

5

6

pivot

pivot

8 of 19

Problem 0

9 of 19

Sorting Algorithm

Asymptotic Runtime

Explanation

Insertion Sort

O(n)

Insertion Sort will traverse the array, but since it is already ‘sorted’, no extra computation is necessary.

Selection Sort

O(n2)

Selection Sort always has O(n2) runtime since it has to find the smallest item in the unsorted subarray n times.

Merge Sort

O(n log n)

Merge Sort always has O(n log n) runtime. You can prove this using recurrences!

Quick Sort

O(n2)

This is the worst case for Quick Sort. Since all the elements are the same, all items will end up on the same side of each partition.

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

​

​

​

​

​

​

​

​

​

​

​

​

10 of 19

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

Sorting Algorithm

Asymptotic Runtime

Explanation

Insertion Sort

O(n)

Insertion Sort will traverse the array, but since it is already ‘sorted’, no extra computation is necessary

Selection Sort

O(n2)

Selection Sort always has O(n2) runtime since it has to find the smallest item in the unsorted subarray n times

Merge Sort

O(n log n)

Merge Sort always has O(n log n) runtime. You can prove this using recurrences!

Quick Sort

O(n2)

This is the worst case for Quick Sort. Since all the elements are the same, all items will end up on the same side of each partition.

11 of 19

Non-Comparison Sorts

12 of 19

Bucket Sort

* can be used only when values to be sorted are integers between 1 and K (or any small range)

bucketSort(input):

  • Create array of size K
    • If data is only integers, each bucket stores count
    • Otherwise, each bucket stores a list
  • Put each element in its proper bucket
  • Output result via linear pass through array

Count array

1

​

2

​

3

​

4

​

5

​

K = 5

Input = 5, 1, 3, 4, 3, 2, 1, 1, 5, 4, 5

Bucket Sort

13 of 19

(Recap) Bucket Sort

* can be used only when values to be sorted are integers between 1 and K (or any small range)

  • Overall: O(N+K)
    • Good when K < N or K ≈ N
    • Bad when K >>> N
  • NOT in-place (O(N+K) extra space needed)
  • Stable

bucketSort(input):

  • Create array of size K
    • If data is only integers, each bucket stores count
    • Otherwise, each bucket stores a list
  • Put each element in its proper bucket
  • Output result via linear pass through array

Count array

1

3

2

1

3

2

4

2

5

3

K = 5

Input = 5, 1, 3, 4, 3, 2, 1, 1, 5, 4, 5

Output = 1, 1, 1, 2, 3, 3, 4, 4, 5, 5, 5

Bucket Sort

14 of 19

(Recap) Radix Sort

radixSort(input):

  • Create array of size B = radix = base of a number system

(eg. 10)

  • Bucket Sort each digit of elements, starting from least significant digit
  • Output result via linear pass through array

Bucket Sort on 1’s digit:

Bucket Sort on 10’s digit:

0

1

2

3

4

5

6

7

8

9

​

​

​

​

​

​

​

​

​

​

0

1

2

3

4

5

6

7

8

9

​

​

​

​

​

​

​

​

​

​

B = 10

Input = 478, 537, 9, 721, 3, 38, 143, 67

​

Radix Sort

15 of 19

(Recap) Radix Sort

radixSort(input):

  • Create array of size B = radix = base of a number system

(eg. 10)

  • Bucket Sort each digit of elements, starting from least significant digit
  • Output result via linear pass through array

B = 10

Input = 478, 537, 9, 721, 3, 38, 143, 67

​

Bucket Sort on 1’s digit:

Bucket Sort on 10’s digit:

0

1

2

3

4

5

6

7

8

9

​

721

​

3

143

​

​

​

537

67

478

38

9

0

1

2

3

4

5

6

7

8

9

​

​

​

​

​

​

​

​

​

​

Radix Sort

16 of 19

(Recap) Radix Sort

radixSort(input):

  • Create array of size B = radix = base of a number system

(eg. 10)

  • Bucket Sort each digit of elements, starting from least significant digit
  • Output result via linear pass through array

Bucket Sort on 1’s digit:

Bucket Sort on 10’s digit:

0

1

2

3

4

5

6

7

8

9

​

721

​

3

143

​

​

​

537

67

478

38

9

0

1

2

3

4

5

6

7

8

9

3

9

​

721

537

38

143

​

67

478

​

​

B = 10

Input = 478, 537, 9, 721, 3, 38, 143, 67

​

Radix Sort

17 of 19

(Recap) Radix Sort

radixSort(input):

  • Create array of size B = radix = base of a number system

(eg. 10)

  • Bucket Sort each digit of elements, starting from least significant digit
  • Output result via linear pass through array

Bucket Sort on 10’s digit:

Bucket Sort on 100’s digit:

0

1

2

3

4

5

6

7

8

9

3

9

​

721

537

38

143

​

67

478

​

​

0

1

2

3

4

5

6

7

8

9

​

​

​

​

​

​

​

​

​

​

B = 10

Input = 478, 537, 9, 721, 3, 38, 143, 67

​

Radix Sort

18 of 19

(Recap) Radix Sort

  • Overall: O(P(B+N))
    • P = # passes

= # digits

  • NOT in-place (O(N+B) extra space needed)
  • Stable

radixSort(input):

  • Create array of size B = radix = base of a number system

(eg. 10)

  • Bucket Sort each digit of elements, starting from least significant digit
  • Output result via linear pass through array

Bucket Sort on 10’s digit:

Bucket Sort on 100’s digit:

0

1

2

3

4

5

6

7

8

9

3

9

​

721

537

38

143

​

67

478

​

​

0

1

2

3

4

5

6

7

8

9

3

9

38

67

143

​

​

478

537

​

721

​

​

Output = 3, 9, 38, 67, 143, 478, 537, 721

Radix Sort

19 of 19

Thank You!