Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

OK. Today we are going to talk about a very interesting algorithm called Quicksort — — which was invented by Tony Hoare in 1962. And it has ended up being a really interesting algorithm from many points of view. And because of that, it turns out today's lecture is going to be both hard and fast. If you see the person next to you sleeping, you will want to say let's get going. It's a divide-and-conquer algorithm.

And it sorts, as they say, in place, meaning that it just rearranged the elements where they are. That is like insertion sort rearranges elements where they are. Mergesort does not. Mergesort requires extra storage in order to do the merge operation. To merge in linear time and place, it doesn't merge in place in linear time. It doesn't do it just by rearranging. It is nice because it is in place, so that means that it is fairly efficient in its use of storage. And it also happens to be very practical if you tune it a bit. The basic algorithm turns out, if you just implement that, it's not necessarily that efficient.

But if what you do was then do the standard kinds of things you do to goose up the runtime of something, and we'll talk a little about what those things are, then it can be very, very practical. So, it uses divide-and-conquer paradigm. First step is divide. And to do this basically it does it by partitioning. So, it partitions the input array into two subarrays around an element we call the pivot —

— such that elements in the lower subarray are less than or equal to x, are less than or equal to elements in the upper subarray. If we draw a picture of the input array, this partition step basically takes some element x and everything over here is less than or equal to x after the partition step and everything over here is greater than or equal to x. And so now the conquer step is pretty easy.

You just recursively sort the two subarrays. So, I recursively sort the elements less than or equal to x, I recursively sort the elements greater than or equal to x. And then combine is then just trivial. Because once I have sorted the things less than or equal to x, then sorted the things greater than or equal to x, the whole thing is sorted. So, there is nothing to do really for the combine. The key step in quicksort is this partition step. That is the thing that does all of the work. And so you can view quicksort of just as recursive partitioning. That's all it is.

Just as mergesort was recursive merging, quicksort sort of goes the other way around and does recursive partitioning. The key is the linear time, by which I mean theta n, partitioning subroutine. And here are some pseudocode for it. This is actually slightly different from the book. The book has one. In fact, there is a nice problem in the book that has even a different one, but they are all basically the same idea.

Partition (A, p, q). And what we are looking at, at this step of the recursion, is the subarray A from p to q. And basically we pick a pivot, which is we are going to just pick as the first element of the array A of p. And the book, just for your information, uses A of q. I use A of p. It doesn't really matter. And then we set an index to p and then we have a loop. This is the code. Basically the structure of it is a for loop with an "if" statement in the middle. And so the structure of the algorithm of this partitioning step looks as follows.

We set the pivot to be the first element. Here is p and here is q. This is going to be our invariant for the loop.

And it sorts, as they say, in place, meaning that it just rearranged the elements where they are. That is like insertion sort rearranges elements where they are. Mergesort does not. Mergesort requires extra storage in order to do the merge operation. To merge in linear time and place, it doesn't merge in place in linear time. It doesn't do it just by rearranging. It is nice because it is in place, so that means that it is fairly efficient in its use of storage. And it also happens to be very practical if you tune it a bit. The basic algorithm turns out, if you just implement that, it's not necessarily that efficient.

But if what you do was then do the standard kinds of things you do to goose up the runtime of something, and we'll talk a little about what those things are, then it can be very, very practical. So, it uses divide-and-conquer paradigm. First step is divide. And to do this basically it does it by partitioning. So, it partitions the input array into two subarrays around an element we call the pivot —

— such that elements in the lower subarray are less than or equal to x, are less than or equal to elements in the upper subarray. If we draw a picture of the input array, this partition step basically takes some element x and everything over here is less than or equal to x after the partition step and everything over here is greater than or equal to x. And so now the conquer step is pretty easy.

You just recursively sort the two subarrays. So, I recursively sort the elements less than or equal to x, I recursively sort the elements greater than or equal to x. And then combine is then just trivial. Because once I have sorted the things less than or equal to x, then sorted the things greater than or equal to x, the whole thing is sorted. So, there is nothing to do really for the combine. The key step in quicksort is this partition step. That is the thing that does all of the work. And so you can view quicksort of just as recursive partitioning. That's all it is.

Just as mergesort was recursive merging, quicksort sort of goes the other way around and does recursive partitioning. The key is the linear time, by which I mean theta n, partitioning subroutine. And here are some pseudocode for it. This is actually slightly different from the book. The book has one. In fact, there is a nice problem in the book that has even a different one, but they are all basically the same idea.

Partition (A, p, q). And what we are looking at, at this step of the recursion, is the subarray A from p to q. And basically we pick a pivot, which is we are going to just pick as the first element of the array A of p. And the book, just for your information, uses A of q. I use A of p. It doesn't really matter. And then we set an index to p and then we have a loop. This is the code. Basically the structure of it is a for loop with an "if" statement in the middle. And so the structure of the algorithm of this partitioning step looks as follows.

We set the pivot to be the first element. Here is p and here is q. This is going to be our invariant for the loop.

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил