Overview

Loading...

Del curso dictado por University of California San Diego

Algorithmic Toolbox

3585 calificaciones

University of California San Diego

Algorithmic Toolbox

3585 calificaciones

Curso 1 de 6 en SpecializationData Structures and Algorithms

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

De la lección

Divide-and-Conquer

In this module you will learn about a powerful algorithmic technique called Divide and Conquer. Based on this technique, you will see how to search huge databases millions of times faster than using naïve linear search. You will even learn that the standard way to multiply numbers (that you learned in the grade school) is far from the being the fastest! We will then apply the divide-and-conquer technique to design two efficient algorithms (merge sort and quick sort) for sorting huge lists, a problem that finds many applications in practice. Finally, we will show that these two algorithms are optimal, that is, no algorithm can sort faster!

Random Pivot13:04

Running Time Analysis (optional)15:32

Equal Elements6:31

Final Remarks8:12

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

Hello, and welcome to the next lesson in the Divide-and-Conquer model.

This lesson is going to be devoted to the quick sort algorithm, which is

one of the most efficient and commonly used in practice sorting algorithms.

Well, as usual, we start with the overview of this algorithm.

The algorithm is comparison based,

meaning that it sorts the n given elements by comparing pairs of them.

Its running time is also asymptotically n log n, but not in the worst case,

as was with the merge sort algorithm, for example, but on the average case.

This is because this algorithm is randomized,

so it uses random numbers to sort the given n objects.

Well, we will explain later in this lesson what this means.

Finally, as I said before, this algorithm is very efficient in practice and,

at the same time, not so difficult to implement.

This is a toy example explaining the main idea of the quick sort algorithm.

So given an array, in this case of size 11, let's take its first element.

In this case it is 6.

And let's do the following.

Let's rearrange all the elements in this array such

that the element 6 stays in its final position.

All the elements that go before it are actually at most 6.

And all the elements that go after 6, after this element, are greater than 6.

Well, we will show that this can be done by a single scan of the initial array.

This is how the resulting array looks like.

So once again, 6 stays in its final position.

All the elements before it are at most 6.

All the elements after it are greater than 6.

So we do not need to move 6 anymore.

It is already in its final position.

So what remains to be done is to sort all the elements that go before 6 and

all the elements that go after 6.

And this can be done just with two recursive calls to the same algorithm,

to the quick sort algorithm.

So we do this,

and immediately after these two recursive calls, we have a sorted array.

Well, in the next video we will explain all the details of this algorithm.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play