程序代写代做代考 algorithm data structure COMP 250

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