- Hey there.
Welcome to week seven of CS124 online,
Data Structures and Algorithms.
Well, let's see.
Last week we studied binary heaps and priority queues
and we started our study of sorting algorithms
with bubble sort.
And this week and next we'll continue our tour
of sorting algorithms.
We have a lot to go over.
So last week we saw the bubble sort was effective,
that is, it works, but that it's not very efficient.
And this week we'll see some similar algorithms,
algorithms that work by swapping elements,
that yield better performance than bubble sort.
These are selection sort and insertion sort.
Selection sort works
by scanning the unsorted portion of the vector,
finds the minimum value,
and then swaps it with the left-most unsorted element.
And in this way, it performs the smallest number of swaps.
That's what it's designed to do,
to perform the smallest number of swaps.
And that's where it gets its performance improvement
over bubble sort.
Now, whereas selection sort is designed to
perform the smallest number of swaps,
insertion sort is designed to work
with only one unsorted element at a time,
thus reducing the number of comparisons
that need to be made.
Finally, we'll learn about merge sort.
Now merge sort is a completely different kind of algorithm
than we've seen before.
It's a divide and conquer algorithm.
And divide and conquer algorithms work
by dividing the problem instance into smaller problems,
solving the smaller problems,
and then constructing a result by combining,
in one way or another depending on the algorithm,
combining those results to produce a complete solution.
A merge sort is much faster than bubble sort,
selection sort, or insertion sort.
Its time complexity is O of nLogn.
We'll explain how all these algorithms work
and we'll implement each one in C++.
So get started
with this week's video lectures and demonstrations
and the supplemental materials posted on Blackboard.
And don't forget the assigned reading in the textbook.
At the end of this week, like all the other weeks,
we'll have another quiz that'll cover this week's material
and some additional material that we covered last week.
So you should expect something on binary heaps
and all four sorting algorithms
that we'll have seen by the end of this week.
So that's all for now.
I'll see you on our Yellowdig discussion board
and have fun.