1 of 13

Sorting

CSE 332 (Section 6)

Original slides by: Louis Maliyam • Monty Nitschke • Kevin Pham

2 of 13

Announcements

  • Midterm this Friday!
    • @12:30-1:20PM in CSE2 G20
    • Same time and room as lecture!
  • Project 2 in progress!
    • Checkpoint 2 due today @ 11:59 PM
    • Final deadline (not using late days) is 11/10
      • Try to save some late days for P3

3 of 13

Comparison Sorts

Recap

4 of 13

(Recap) Insertion Sort

Original input:

3

2

11

12

* grey area is the unsorted part

Step 1:

3

2

11

12

Step 2:

2

3

11

12

Step 3:

11

2

3

12

Step 4:

11

12

2

3

  • Best case: O(N)
  • Worst case: O(N2)
  • In-place

No swaps needed

5 of 13

(Recap) Selection Sort

Original input:

31

32

2

1

* grey area is the unsorted part

Step 1:

1

32

2

31

Step 2:

1

2

32

31

Step 3:

1

2

32

31

Step 4:

1

2

32

31

  • Best case: O(N2)
  • Worst case: O(N2)
  • In-place

6 of 13

(Recap) Merge Sort

  • Best case: O(NlogN)
  • Worst case: O(NlogN)
  • NOT in-place (O(N) extra space needed)

mergeSort(input):

1) mergeSort on left half

2) mergeSort on right half

3) merge left half and right half

7 of 13

(Recap) Quick Sort

  • Best case: O(NlogN)
  • Worst case: O(N2)
  • If using Hoare’s partitioning algorithm
    • In-place
  • If using naive partitioning
    • NOT in-place (O(N) extra space needed)

* this example SIMPLY chooses the most right element to be a pivot. However, the lecture mentioned about a better way to choose a pivot–median of three.

Note: Sort not fully complete, one more division would occur for [1,2] and [12,15]

quickSort(input):

1) pick pivot

2) partition values into “less than pivot” part and “greater than pivot” part

3) quickSort on “less than pivot” part

4) quickSort on “greater than pivot” part

8 of 13

Problem 2

Sorting Hat

Discuss with neighbors

9 of 13

(Q2) Sorting Hat

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}. (So, in hindsight, the sorting is useless.)

In this case, what is the asymptotic running time of ...

Sorting Algorithm

Asymptotic Runtime

Explanation

Insertion Sort

O( )

​

Selection Sort

O( )

​

Merge Sort

O( )

​

Quick Sort

O( )

​

10 of 13

(Q2) Sorting Hat

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}. (So, in hindsight, the sorting is useless.)

In this case, what is the asymptotic running time of ...

Sorting Algorithm

Asymptotic Runtime

Explanation

Insertion Sort

O(N)

This is the best case runtime of insertion sort as it only requires one pass though the data.

Selection Sort

O( )

​

Merge Sort

O( )

​

Quick Sort

O( )

​

11 of 13

(Q2) Sorting Hat

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}. (So, in hindsight, the sorting is useless.)

In this case, what is the asymptotic running time of ...

Sorting Algorithm

Asymptotic Runtime

Explanation

Insertion Sort

O(N)

This is the best case runtime of insertion sort as it only requires one pass though the data.

Selection Sort

O(N^2)

Selection sort always has N^2 runtime since we have to scan to find the smallest item N times.

Merge Sort

O( )

​

Quick Sort

O( )

​

12 of 13

(Q2) Sorting Hat

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}. (So, in hindsight, the sorting is useless.)

In this case, what is the asymptotic running time of ...

Sorting Algorithm

Asymptotic Runtime

Explanation

Insertion Sort

O(N)

This is the best case runtime of insertion sort as it only requires one pass though the data.

Selection Sort

O(N^2)

Selection sort always has N^2 runtime since we have to scan to find the smallest item N times.

Merge Sort

O(NlogN)

Merge Sort is always NlogN

Quick Sort

O( )

​

13 of 13

(Q2) Sorting Hat

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}. (So, in hindsight, the sorting is useless.)

In this case, what is the asymptotic running time of ...

Sorting Algorithm

Asymptotic Runtime

Explanation

Insertion Sort

O(N)

This is the best case runtime of insertion sort as it only requires one pass though the data.

Selection Sort

O(N^2)

Selection sort always has N^2 runtime since we have to scan to find the smallest item N times.

Merge Sort

O(NlogN)

Merge Sort is always NlogN

Quick Sort

O(N^2)

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