COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 6-1 : Quadratic Sorting a List
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
How to sort a list Bubble sort
Selection sort Insertion sort
SORTING
The process of arranging items in a ordered list following a given criterion.
For example, sorting a list of integers in ascending order (from smallest to largest):
BEFORE AFTER
3 17 -5 -2 23 4
-5 -2 3
4 17 23
SORTING ALGORITHMS
There are many techniques for sorting a list Selection Sort
Bubble Sort
Insertion Sort
Random Sort 😛 Heap Sort
Merge Sort
Quick Sort
SORTING ALGORITHMS
There are many techniques for sorting a list Selection Sort
Bubble Sort
Insertion Sort
Heap Sort Merge Sort Quick Sort
Today 𝑂 𝑁2
Check out how different
algorithms compare:
https://www.youtube.com/w atch?v=ZZuD6iUe3Pc
Later 𝑂 𝑁 ⋅ log𝑁
OBAMA KNOWS ABOUT SORTING!
OBSERVATION
7
Today we are concerned with algorithms, not data structures.
The following algorithms are independent of whether we use an array list or a linked list.
BUBBLE SORT
BUBBLE SORT
Bubble sort is the simplest sorting algorithm.
Goal: order a list of integers in ascending order
IDEA: repeatedly iterate through the list and swap adjacent elements if they are in the wrong order.
BUBBLE SORT – PSEUDOCODE
for i from 0 to list.length-1 {
for j from 0 to list.length -2 {
if(list[j] > list[j+1]) {
swap(list[j], list[j+1])
} }
}
EXAMPLE – ONE ITERATION
5
1
4
2
8
EXAMPLE – ONE ITERATION
Iteration #1
• Compare all adjacent
elements.
• If needed, swap!
compare
5
1
4
2
8
EXAMPLE – ONE ITERATION
Iteration #1
• Compare all adjacent
elements.
• If needed, swap!
1
5
4
2
8
swap
EXAMPLE – ONE ITERATION
Iteration #1
• Compare all adjacent
elements.
• If needed, swap!
compare
1
5
4
2
8
EXAMPLE – ONE ITERATION
Iteration #1
• Compare all adjacent
elements.
• If needed, swap!
swap
1
4
5
2
8
EXAMPLE – ONE ITERATION
Iteration #1
• Compare all adjacent
elements.
• If needed, swap!
compare
1
4
5
2
8
EXAMPLE – ONE ITERATION
Iteration #1
• Compare all adjacent
elements.
• If needed, swap!
swap
1
4
2
5
8
EXAMPLE – ONE ITERATION
Iteration #1
• Compare all adjacent
elements.
• If needed, swap!
compare
1
4
2
5
8
WHAT CAN WE SAY AFTER THE FIRST ITERATION?
Q: Where is the largest element ? A:
Q: Where is the smallest element? A:
WHAT CAN WE SAY AFTER THE FIRST ITERATION?
Q: Where is the largest element ?
A: It must be at the end of the list (position N-1) Q: Where is the smallest element?
A: Anywhere (except position N-1)
WHAT CAN WE SAY AFTER THE FIRST ITERATION?
Q: Where is the largest element ?
A: It must be at the end of the list (position N-1)
Since each time we iterate through the list we ensure that the largest element is in the correct position.at each iteration we can stop comparing adjacent elements one step earlier.
BUBBLE SORT – PSEUDOCODE
for i from 0 to list.length-1 {
for j from 0 to list.length – i -2 {
if(list[j] > list[j+1]) {
swap(list[j], list[j+1])
} }
}
EXAMPLE
We left off at the end of Iteration #1
Unsorted Sorted
1
4
2
5
8
EXAMPLE
Iteration #2
• Compare all adjacent
elements up to index 3.
• If needed, swap!
Unsorted
Sorted
1
4
2
5
8
EXAMPLE
Iteration #2
• Compare all adjacent
elements up to index 3.
• If needed, swap!
compare
Unsorted
Sorted
1
4
2
5
8
EXAMPLE
Iteration #2
• Compare all adjacent
elements up to index 3.
• If needed, swap!
compare
Unsorted
Sorted
1
4
2
5
8
EXAMPLE
Iteration #2
• Compare all adjacent
elements up to index 3.
• If needed, swap!
swap
Unsorted
Sorted
1
2
4
5
8
EXAMPLE
Iteration #2
• Compare all adjacent
elements up to index 3.
• If needed, swap!
compare
Unsorted
Sorted
1
2
4
5
8
EXAMPLE
Iteration #3
• Compare all adjacent
elements up to index 2.
• If needed, swap!
Unsorted
Sorted
1
2
4
5
8
Note: now the list is sorted, but the algorithm does not know that.
When can the algorithm infer that the list is sorted?
EXAMPLE
Iteration #3
• Compare all adjacent
elements up to index 2.
• If needed, swap!
compare
Unsorted
Sorted
1
2
4
5
8
EXAMPLE
Iteration #3
• Compare all adjacent
elements up to index 2.
• If needed, swap!
compare
Unsorted
Sorted
No swap was needed in this iteration the list is sorted!
1
2
4
5
8
EXAMPLE
No swap was needed in the last iteration. We can stop comparing. The list is sorted!
1
2
4
5
8
BUBBLE SORT – PSEUDOCODE
sorted = false i=0
while (!sorted) {
sorted = true
for j from 0 to list.length – i -2 { if(list[j] > list[j+1]) {
swap(list[j], list[j+1])
sorted = false
} }
i++
}
SELECTION SORT
SELECTION SORT
Goal: order a list of integers in ascending order
Idea: consider the list as if it was divided into two parts, one sorted and the other unsorted. (note: at the beginning the sorted part is empty)
Procedure:
Select the smallest element in the unsorted part of the list
Swap that element with the element in the initial position of the unsorted array
Change where you divide the array from the sorted part to the unsorted part.
EXAMPLE
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select • Swap
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select • Swap
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select
• Swap
• Updatedelimiter
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select • Swap
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select • Swap
Sorted Unsorted
1
2
7
5
EXAMPLE
• Select • Swap
• Update
Sorted Unsorted
1
2
7
5
EXAMPLE
• Select
Sorted Unsorted
1
2
7
5
EXAMPLE
• Select • Swap
Sorted Unsorted
1
2
7
5
EXAMPLE
• Select • Swap
Sorted Unsorted
1
2
5
7
EXAMPLE
• Select • Swap
• Update
Sorted Unsorted
1
2
5
7
EXAMPLE
1
2
5
• Done!
7
SELECTION SORT – PSEUDOCODE
for delim from 0 to N-2 {
min = delim
for i from delim+1 to N-1 {
if(list[i] < list[min]) {
min = i
} }
if(min != delim) {
swap(list[min], list[delim])
}
Repeat until list is all sorted (~N times)
Find the index of the min element in the unsorted part of the list
Swap the min element in the first position of the unsorted part of the list.
}
SELECTION SORT
for delim from 0 to N-2
for i from delim+1 to N-1
...
How many times does the inner loop iterate?
51
SELECTION SORT
for delim from 0 to N-2
for i from delim+1 to N-1
...
How many times does the inner loop iterate? N-1 + N-2 + N-3 +...+ 2 + 1
52
SELECTION SORT
for delim from 0 to N-2
for i from delim+1 to N-1
...
How many times does the inner loop iterate? N-1 + N-2 + N-3 +...+ 2 + 1 = N*(N-1)/2
53
COMPARISON
Bubblesort
while(!sorted)
for j from 0 to N – 2 – i
Selection sort
for delim from 0 to N-2
for i from delim+1 to N-1
We can terminate outer loop if there are no swaps during a pass.
00 11
:: : Best :
Dark area denotes which elements of the list need to be examined at each iteration of the outer loop.
N-1
N-1
00 11
:: : Wor st :
case
case
N-1
N-1
Outer loop
Outer loop
INSERTION SORT
INSERTION SORT
Goal: order a list of integers in ascending order
Idea: consider the list as if it was divided into two parts, one sorted and the other unsorted. (note: at the beginning the sorted part is empty)
Procedure:
Select the first element of the unsorted part of the list
Insert such element into its correct position in the sorted part of the list.
Change where you divide the array from the sorted part to the unsorted part.
EXAMPLE
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select • Insert
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select • Insert
• Update
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select • Insert
Sorted Unsorted
5
1
7
2
EXAMPLE
• Select • Insert
• Update
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select • Insert
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select • Insert
• Update
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select
Sorted Unsorted
1
5
7
2
EXAMPLE
• Select • Insert
Sorted Unsorted
1
5
7
2
EXAMPLE
1
2
5
• Done!
7
INSERTING
Mechanism is similar to inserting (adding) an element to an array list:
Shift all elements ahead by one position to make a hole, and then fill the hole.
INSERTION SORT – PSEUDOCODE
Repeat until list is all sorted (~N times)
Find where the element should be inserted in the sorted part of the list + make space for it (shift all the larger elements to the right)
Insert the element in the sorted part of the list.
for i from 0 to N-1 {
element = list[i]
k =i
while(k>0 && element