Explore
For Enterprise
Join for Free
Log In

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

Core: A Summary of Sorting

Loading...

Data Structures and Performance

Universidad de California en San Diego

4.8 (1,654 calificaciones) | 54K estudiantes inscritos

Curso 4 de 4 en Object Oriented Programming in Java Programa Especializado

How do Java programs deal with vast quantities of data? Many of the data structures and algorithms that work with introductory toy examples break when applications process real, large data sets. Efficiency is critical, but how do we achieve it, and how do we even measure it? This is an intermediate Java course. We recommend this course to learners who have previous experience in software development or a background in computer science, and in particular, we recommend that you have taken the first course in this specialization (which also requires some previous experience with Java). In this course, you will use and analyze data structures that are used in industry-level applications, such as linked lists, trees, and hashtables. You will explain how these data structures make programs more efficient and flexible. You will apply asymptotic Big-O analysis to describe the performance of algorithms and evaluate which strategy to use for efficient data retrieval, addition of new data, deletion of elements, and/or memory usage. The program you will build throughout this course allows its user to manage, manipulate and reason about large sets of textual data. This is an intermediate Java course, and we will build on your prior knowledge. This course is designed around the same video series as in our first course in this specialization, including explanations of core content, learner videos, student and engineer testimonials, and support videos -- to better allow you to choose your own path through the course!

Destrezas que aprenderás

Trees (Data Structures), Data Structure, Linked List, Binary Tree

Revisiones

4.8 (1,654 calificaciones)

5 stars
1,379 ratings
4 stars
239 ratings
3 stars
28 ratings
2 stars
5 ratings
1 star
3 ratings

AE

Dec 06, 2016

Very solid review of data structures. In fact, I learned a lot of new things along the way like how to benchmark test Java code and how to properly use JUnit and other unit testing frameworks.

YK

Jan 11, 2016

I really liked this course and the way it was taught. Although I am a CS major, I really learnt a lot of other stuff from this course apart from learning the core content of Data Structures.

De la lección

Efficiency Analysis and Benchmarking

Welcome to week 3! The text-editor application you worked with last week does something, but it doesn't do it particularly fast. This week we'll start talking about efficiency. We'll introduce the concept of "Big-O" notation, which sounds a little silly, but is really a powerful (and extremely common) way of analyzing a program's efficiency, independent of the system that it's running on and the exact details of how it's implemented. Then we'll go the other direction and dive into the details, talking about how to measure the actual running time of a piece of code to get an idea of how it really performs in practice.

Core: Our Motivation for Asymptotic Analysis8:28

Core: Counting Operations9:57

Core: Introduction to Asymptotic Analysis, Part 19:11

Core: Introduction to Asymptotic Analysis, Part 23:48

Core: Computing Big O with Consecutive Operations5:19

Core: Computing Big O with Nested Operations5:22

Concept Challenge: Classifying Functions using Big O7:52

Support: Analyzing Selection Sort8:41

Concept Challenge: Estimating Big O from Code6:08

Core: Worst, Best, and Average Cases8:16

In the Real World: Worst Case Analysis1:30

Core: Analyzing Search Algorithms6:25

Core: Analyzing Sorting Algorithms9:25

When I struggled: Algorithm performance1:31

Core: Merge Sort11:07

Core: A Summary of Sorting4:00

Core: Common Pitfalls in Asymptotic Analysis5:51

Impartido por:

Christine Alvarado
Associate Teaching Professor
Mia Minnes
Assistant Teaching Professor
Leo Porter
Associate Teaching Professor

Transcripción

[MUSIC] >> So we've looked at three different algorithms for solving the exact same problem, that of sorting. And so now let's step back and think about how would we choose which algorithm to use and how does their performance compare. So, by the end of this video, you'll be able to state the best case, worst case, and average case performance, in terms of run time for each of these sorting algorithms. And you'll be able to think a bit about which situations call for one of these algorithms rather than another. So let's think about our results so far, and this table encapsulates what we've been thinking through. And we've computed the best case and worst case performance of each of selection sort, insertion sort, and merge sort. And something to notice here is that we've got the n squared term, or the quadratic term, showing up in the first two algorithms that we talked about, and then this n log n performance for merge sort. And n log n is quite a bit better than quadratic. Now, I'm just going to stick another algorithm into the table. We haven't defined what quick sort is, how it works. It's another algorithm out of a huge collection of sorting algorithms out there. It's sort of a cottage industry of defining more and more sorting algorithms, and we'll talk a little bit more about why a little bit later. But just so you have a reference to another algorithm, the Quick Sort in the best case performs like n log n, and in the worst place can have quadratic performance, so On squared. So, so far we just have best case and worst case, but let's add in that average case performance in there, and then think about what this table is really telling us. So for example, we might look for which sort is going to be the fastest in the best case. So perhaps, we really just care about performance and we're willing to maybe put in some work to make sure that we lined in the best case as often as we can. And so, in that case we want to narrow in on the cell on the table that has the best performance. And linear time beats every other time in this cell, and grows more slowly than n log n, or than n squared. And so O of n time is really great. And so if we can have any sort of confidence that we might stay in the best case relatively often, then Insertion Sort might be the way to go. And in the next lesson Leo will be talking about some cases in which Insertion Sort might be really appealing. Okay. So, we've got this very optimistic, or aggressive, approach that we wanna get to the best case and stay there as well as we can. We might also wanna compare Merge Sort and Quick Sort because if we look at their best case and average case performance, they both perform like n log n. And so then we might focus in on the worst case and say, well, why would we ever, ever use Quick Sort if Merge Sort has the same best case performance, the same average case performance, and does, well, way better in the worst case than Quick Sort? Is there ever a reason in which we use Quick Sort rather than Merge Sort? Why did I even bother putting it in the table? And this leads us to the observation that the asymptotics, this performance bound that we've been computing of the big O class of the run timer, the number of operations that the algorithm performs, is really not the only measure of goodness of an algorithm. So this goes back to when we first started talking about sorting in the first course in the specialization. We talked about other properties that a sorting algorithm might have. It might be stable, or it might use very little auxiliary memory so it might have, it'd be very nimble. >> And so, when we're thinking about choosing a sorting algorithm we want to choose amongst the whole array of possible algorithms, taking run time performance as one indicator of which one to use, but also thinking about the use case and the actual real-world factors that influence which algorithm is going to be right for us.

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.

© 2019 Coursera Inc. Todos los derechos reservados.

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government
Para el campus

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados