Explore
For Enterprise
Join for Free
Log In

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

Core: Selection Sort Implementation

Loading...

Object Oriented Programming in Java

Universidad de California en San Diego

4.7 (3,637 calificaciones) | 170K estudiantes inscritos

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

Welcome to our course on Object Oriented Programming in Java using data visualization. People come to this course with many different goals -- and we are really excited to work with all of you! Some of you want to be professional software developers, others want to improve your programming skills to implement that cool personal project that you’ve been thinking about, while others of you might not yet know why you’re here and are trying to figure out what this course is all about. 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. Our goal is that by the end of this course each and every one of you feels empowered to create a Java program that’s more advanced than any you have created in the past and that is personally interesting to you. In achieving this goal you will also learn the fundamentals of Object Oriented Programming, how to leverage the power of existing libraries, how to build graphical user interfaces, and how to use some core algorithms for searching and sorting data. And this course is project-based, so we’ll dive right into the project immediately! We are excited to be offering a unique course structure, designed to support learners of different backgrounds in succeeding at their own pace. The first module explains how this will work and if this course is right for you. We also recommend taking a few minutes to explore the course site. A good place to start is the navigation bar on the left. Click Course Content to see what material we’ll cover each week, as well preview the assignments you’ll need to complete to pass the course. Click Discussions to see forums where you can discuss the course material with fellow students taking the class. Be sure to introduce yourself to everyone in the Meet and Greet forum. This course should take about 6 weeks to complete. You can check out the recommended course schedule below to see a quick overview of the lessons and assignments you’ll complete each week. We’re excited you’re here learning with us. Let’s get started!

Destrezas que aprenderás

Logic Programming, Java Programming, Object-Oriented Programming (OOP), Sorting Algorithm

Revisiones

4.7 (3,637 calificaciones)

5 stars
2,787 ratings
4 stars
702 ratings
3 stars
97 ratings
2 stars
27 ratings
1 star
24 ratings

KP

Feb 21, 2016

Enroll this course if you intend to become a programmer and need fundamental knowledge in Object Oriented Programming. Here you can study the subject and apply new things in a real curious project.

HW

Mar 21, 2016

It is good!!! I learnt a bit of Java beforehand but not the object oriented concept. Would definitely attend the courses by UC San Diego again as well as pay for the course when I can afford it!

De la lección

Searching and Sorting: From Code to Algorithms

You've come a long way in this course, and you've got a great project to show for it. In this last module we'll shift gears a bit to talk about some very exciting and fundamental algorithms for finding and sorting data in an array. Searching and sorting algorithms are not only fundamental to computer science, but also ideal for beginning to explore issues of algorithm efficiency. We will only begin to touch on issues of algorithm efficiency here. We will say much more about it in the next course in this specialization, so we hope you will continue with us. We'll also apply sorting to your project, and you'll wrap things up by finishing your project with an extension of your own choosing.

Core: Introduction to Sorting7:39

Core: Selection Sort Algorithm3:51

Core: Selection Sort Implementation7:00

Core: Selection Sort Analysis5:13

Concept Challenge: Selection Sort4:59

Core: Mystery Sort13:20

Core: Java's Built-In Sort4:18

Core: Comparable Interface, Revisited7:58

Concept Challenge: Which Sort?3:16

Impartido por:

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

Transcripción

[MUSIC] In the previous video, we developed an algorithm for sorting a bunch of pieces of data and organizing them in some order from smallest to biggest. What we'd like to do in this video is translate that algorithm, or high-level description of the strategy, into Java. So, what we're going to do is think step by step about how to go from natural language descriptions of the strategy to actual code. And so let's start by thinking about what that strategy even was. And so we talked about Selection Sort. So Selection Sort has as its general approach, first of all, we think about the smallest element overall in the entire array. And we look for that smallest element and we try to put it first. Because that's where it's going to need to be at the end. And then we move on to the rest of the array and try to find the smallest element among those elements and then put it in the second position overall because that's its correct location at the end. And we keep going, and we keep going, etc. So, let's think about how we can translate this approach, the constructs that we know from programming. And so, let's start by thinking about the big picture. And what we're doing in Selection Sort is we're looping through all of the positions in the array and for each one of those positions, we try to find the true value in the sorted array. So, for each position i from the very beginning of the array all the way until the end, we are trying to find the right element to put in that position. But actually, not all the way until the end. Remember from the previous video, we talked about a small optimization that once we've sorted the first all but last elements of the array, then the last element is going to be in the correct position because there's really nowhere else for it to go. Okay, so we've got that little tweak and the big picture here, what's important, is that we've got a for-loop that looks over each position in the array and tries to find the right element there. And, it's also useful to keep in mind, that as we're going through this algorithm, we have an invariant property, a property that never changes. And that's the, once we've worked on position zero, position one, position two, then the elements in those positions are sorted, and they're never gonna change, at all. No matter how many more steps we have to go or how big the array is. Those positions are done and the correct elements in the sorted array are already there. And so what we have is this array where slowly, slowly, slowly, we're organizing the first bit of it and then we're focusing on the very next position, say position i, and looking for what element to put there. So, let's think about the body of the for-loop and what we need to do in that body of the for-loop. And so a way to think about that is to look for the smallest element in the not yet organized piece of the array. And whatever is the smallest element among the elements of the array that we haven't put in their correct position, that's the one that's going to need to be in position i. So we need to find the smallest element in all of the elements that remain, and then swap it with the element that's in position i so that that element is in its correct location. Okay, so let's formalize a little bit what it means to be in the still unorganized or unsorted part of the array. Well, those are all of the elements in position i through the end of the array, length- 1. All right, so as you can tell we're getting a little bit closer to coding up the solution. And what I like you to do now is pause the video, and try to write the code. Welcome back. Let's work through it together, and see if the code that we developed is similar to what you did on your own. So, you probably declared a method that is going to be called something like selectionSort, and takes as input the array of values that we wanted to sort. Now, in this method, the way that I've designed it, were not going to return any values. So the return is listed as void. Because what we're going to do is sort the elements of the array in place. So we're going to move them around in the array that we're given. And now, remember that we have the outer for-loop and that outer for-loop is looking at all positions i from the very beginning until the second last element. Okay, now for each of those positions we have to find the correct element to put in that position. And so now we have to implement that piece of the algorithm. And so what we are going to do is try to find the smallest element that has not yet been put in its correct location. And so we want to keep track of the index of that smallest element. The location of where that smallest element is in the list. So, at the beginning, we think well, maybe the smallest element is already in its correct location in i. So our first guess is that the smallest element is in the first place that we look at, namely position i. And then we want to step through all possible positions in that unsorted part of the array and compare the elements in those positions with the value of the element at our current best guess for where the smallest element is located. So, we're comparing the element at position indexMin with the element at position j. And if it so happens that the element at position, j, is smaller than the element at the position which is supposed to record the smallest element, well, we need to update what we think is going on. Now, in this case, we think that the smallest element is actually in position j. And now we have to keep on going, and keep on checking all of the elements to make sure that indexMin really records the position of the smallest element in that remaining piece of the array. So once we've gone through this inner for-loop, what we have is indexMin recording the position of the smallest element in the remaining part of the array. And then the last piece of our algorithm is to put that smallest element in its correct location, namely, in position i. And so we might have a helper method swap that we define somewhere else, and that's what method looks at the array vals, and it swaps the element at position indexMin with the element at position i. And so what that would do, is take the element that supposed to be in position i, and really put it there. Okay. And so, what we've done here is we've gone from the high level description of selection sort and we've now gone ahead and implemented it using Java. All right, so, before we leave this algorithm and say hoo, we've done it, pat on our back, we can stop thinking about it now. It's useful to probe further and always ask ourselves some questions. How do we know that this algorithm and this implementation always works, no matter what array we give it? And if we believe that it does work, how well does it work? And of course, as good engineers and scientists, we always want to do better and can we? So, in the next video we'll talk about some of these questions.

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