#### Transcripts

1. Introduction : Coding can be very challenging and yet extremely enjoyable At the same time. Hello everyone. I'm Hadi units and this is Programming for Everybody. Now, if you know nothing about programming, I think you should start with the two previous classes. And the first one we sold Java and Eclipse and learn about some basic concepts such as datatypes, decision-making, loops, and much more, but all in a general way. And in the second class with a deeper to these concepts from creating classes and objects, do using arrays and ArrayLists. Now, in this class, we'll explore some old and new concepts. Some of them are already mentioned in the first class that here we get to the bottom of them. With that being said, you can start and I hope you enjoy it.
2. Material : As usual, we'll start with our material. So what are we going to cover? First of all, we'll talk about inheritance, and then we'll introduce polymorphism and how to use it via inheritance. And then we'll introduce a new concept in programming, recursion and how to use it. After that will move out to sorting algorithms. So if we had, if we have an array or an array list of integers, strings, characters, we'll learn how to solve them. And then we'll talk about searching algorithms. So if we have a specific integer, for example, how to find it in a specific array. And lastly, we'll talk about Big Integer class. After that will solve some problems on each topic as usual. And lastly, we have our project. So this is it. And let's start.
3. Inheritance: First of all, we start with inheritance, fundamental technique for organizing and creating classes. It is a simple but powerful idea that implements is the way we design object oriented software. You can say that a class is to an object what a blueprint is to house. Many houses can be created from the same blueprint. They are essentially the same house in different locations with different people living in them. Now, suppose you want to house that is similar to another, but with some different or additional features. You want to start with the same basic blueprint, but modify it to suit new, slightly different needs. Many housing developments are creating this way. The houses in the development Have the same core layout, but they have unique features. For instance, they might all be split-level homes with the same basic groom configuration, but some have a fireplace or full basement, while others do not. Now, via inheritance, the new class automatically contains the variables and methods in the original class, and then they leave the class as needed. The programmer can add new variables and methods to the derived class or modify the inherited ones. The original class that is used to derive a new one is called the band class, superclass or base class. So here is the parent of Pictionary and the glass. The derived class is called a child class or subclass. And Java uses the reserved word extends to indicate that the new class is being derived from an existing class. Now, the process of inheritance should establish an is a relationship between two classes. So we have an is a relationship between book and dictionary. That is, the child class should be a more specific version of the parent class. For example, dictionary is a book, but not all books are dictionaries. Now, if such statement doesn't make sense, then this relationship is probably not an appropriate use of inheritance. So now lets demonstrate the use of an inherited method. For example, we have words, we have here our main method. And dictionary will have three methods. Computer issue, set definitions, get definitions, and a variable integer. And lastly, our parent class, the book. We have a variable n and two methods set pages and get peaches. Let's go ahead and create our three classes. We have Cook and V8 dictionary. And lastly, word. Glasses. So now let us start with book. So this is the parent class of derived class to use it to demonstrate inheritance. So we have vegetable and integers, let's say is protected and then will explain it later. And you pages equal to 1500 pages. And we have two methods. First of all, set page, which is pagers, give it a value of integer as a parameter, num, and that the pages equal to this value. So now instead the beaches and yet beaches, to return the value of pages. We just return pages. Now, what is the protected modified? As we've seen, the visibility modifiers are used to control access to the members of a class. This effect extends to the process of inheritance as well. So private methods and variables of the parent class cannot be referenced in the child class or through an object of the child class. And if we declare a variable with public visibility for that so that the derived class can reference it. We violate the principle of encapsulation. Therefore, Java provides a third visibility modifiers protected. So we're using protected. We can have access to this variable and our child class, dictionary. Now, it's good to dictionary. And here we have our dictionary class. So this class, dictionary, which is a book, they're derived from the book class. So let's save this classmen dictionary. We have three methods and a variable. Let's use private. Modify this definition to the equal to 2005500 for example. But we have 52,500 definitions. Now, let's create our first method to compute the JHU issue. Now, as we said, we can use and the book, because we said them as protected. And compute the ratios, we simply return a W definitions divided by the issue. I'm sorry, over how many pages, ages and issue we extended from work. And now we have both rest method. Now, method is set definitions. So as usual, nations with numb. And we said that clinicians to be equal to nine. And lastly, we have the get definitions to return how many definitions there is an integer def definition without and simply return definitions. So now these are our methods and let's go ahead and use them in our world-class. So he outward class. So this is our main method and our object dictionary in emitted W. Now let's work with it. So we have some method. Let's print the number of pages. So number of pages. And you're going to use get beaches. We have yet to finishing skip pages. And if we go ahead and run this code, get number of pages, one hundred and five hundred. And let's also print the number of different definitions. We'd say definitions and definitions. So we have 52,500 definitions. And lastly, let's compute them by simply definitions. So no how many definitions that is in the page and use W.com and print it out. We get definitions. Thirty-five definition. Now, remember we also have set Pages and set definition. So for example, if we want to change the pages, simply use W dot set. H is for example, ten and nations for quality. And if we print the Definitions, page one more time, another number which is equal to four. So this is it for this video. See you in the next one.
4. Super Reference : Now we also have a reference that we should be familiar with. This, the super reference. So the reserved word Super can be used in a class to refer to its parent class. So we can have access to a parent's member using the super reference. Now, the word super refers to depends on the class in which it is used. To. Now, lets demonstrate the use of superior reference will stay. With these examples. We have our world-class routes, we have our main method, and we have the dictionary, and we extended book. And lastly we have our class. Now, suppose we have in our book a constructor. So that set a constructor here, saying that public sector have the same name as glass. And let's give it a parameter of integers, which is number of bridges. And inside this constructor, reset the pages to be equal to the beaches given by the constructor. And now this is our constructor into book class. Now let's create another constructor into dictionary class. So we simply created outlet dictionary and we'll give it the value two pages and definitions. Let's change this to the So let's first of all the definitions equal to definition. And and so now I can invoke the super, the parent's constructor using the super reference. All right, super and give it the value of religious. And now we use the super. So the Dictionary constructor takes two integer values as parameters. We have pages and definitions representing a number of pages and a number of definitions in the book. So because the book class already has a constructor that performs the work to set up the path of the dictionary that were inherited. We rely on deck constructor to do that work. So instead of saying that pages equal to the, this basis, we simply rely on this constructor of the class, saying super. So it will go to the constructor into book class and said pages to be equal to this pages. Now, a charged constructor is responsible for calling its parent's constructor. Generally, the first-line of constructor should use the super reference call to the constructor of the pair. And if no such code exists, Java will automatically make a call to super At the beginning of the constructor. So this rule ensures that apparently initializes its variables before the child class constructor begins to execute. Using the super reference to invoke advance constructor can be done only the child constructor. And if included, it must be the first line of the constructor. So the super reference can also be used to reference other variables and methods defined in the parent class. And we use this technique data. Moving on to multiple inheritance, Java's approach to inheritance is called single inheritance. This term means that the derived class can have only one parent. Some object oriented languages allow a child class to have multiple bands. This approach is called multiple inheritance and is occasionally useful for describing objects that are in-between two categories of classes. For example, suppose we had a class and the class truck. And we wanted to create a new class called pickup truck. A pickup truck is somewhat like a car and somewhat like a truck. With single inheritance, we must decide whether it is a better, whether it is better to derive the new classroom guy by truck with multiple inheritance, it can be derived from both, as shown in this figure. Multiple inheritance works well in some situations, but it comes with a price when it, both truck and car have methods with the same name. Which method? Pickup truck inherit? The answer to this question is complex, and it depends on the rules of the language that supports multiple inheritance. The designers of the Java language explicitly decided not to support multiple inheritance. Instead, we can rely on inheritance and interfaces to provide the best features of multiple inheritance without the added complexity. Although a Java class can be derived from only one parent class, can implement multiple interfaces. Therefore, we can interact with a particular class in the specific ways with inheritance and interfaces, while inheriting the core information from one parent class and using interfaces. And we'll talk about interfaces later. So this is it for the super and multiple inheritance. And the next video, we'll learn how a child class can override the parents definition of an inherited method.
5. Overriding Methods : Moving on to overriding methods. When a child class defines a method with the same name and signature as a method in the parent class, we say that the child's virgin overrides the parent's version in favor of its own. The need for overriding occurs often in inheritance situations. So let's go ahead and demonstrate the use of an overridden method. Creates a new package, name it over. Right? And, and this package will create three classes. The first one we'll name it message. The second one will be at twice. And lastly, we'll create a class called thought. So we have three classes. And the message. Here we have our main method and we'll work it later on. But for now, we will connect vice and thought. So at the third is depend class and the advice class is the child extend. And let's create the same method. The same method and the two classes. So in thought, would create a public voice message with no parameter, simply print. This is the message from the parent. And the advice class would have the same method. Public, public message. With no parameter, it simply prints. This is a message from the class. And we'll use the super, super.message to explicitly invoke the parents virgin. Now, let's go ahead and use you have here an error undefined for the time. You need to save this and everything properly. And now let's go to our message. Let's use two objects. One for advice, you have advise, a new advice, and the same thing for the last name and the new. Now, we'll use the same method in the two pluses. So we say a.me and the message that's swap them, use first of all, that key and then print a line. So let's see what will happen. So we printed out that this is a message from the parent class and then aligned. So this is our output from D, that message. And then this is the output from a, that message. In a message will get, this is a message from the child class. And then since we used here, the Super, we invoked what? The message in the third class we have here. This is a message from the parent class, so we'll print out a message from the parent class. Now, a method can be defined with the final modifier. And then jet child Cass cannot override a final method. This technique is used to ensure that the derived class uses a particular definition of a method. And now we'll talk about shadowing variables. Although not recommended for inside class, to declare a variable with the same name as one that is inherited from the parent. Now, there is a difference between a declaring a variable and simply giving an inherited by a particular value. For example, if we have an integer variable here in the third class, we can give it a value in the advice class, but it is not recommended to redeclare it as, for example, a string or as a double. Now, this declaration creates confusion, and this confusion causes problems and serves no useful purpose. So array declaration of a particular variable name could change its style, but that is, and usually unnecessary and general shadowing variables should be avoided. So this is it for shadowing variables and overriding methods. See you in the next video.
6. Class Hierarchies: Now we'll talk about class hierarchies. Child cast derived from one parent can be the parent of its own childcare. So multiple classes can be derived from a single parent. Therefore, inheritance relationships often develop into class hierarchies. So here, this diagram shows us a class hierarchy that includes the inheritance relationship between mammal and host class, for example, bird and parrot, animal and birth. There is no limit to the number of children a class can have, or the number of levels to which the class hierarchy can extend to children the same parent are called siblings. So here, horse and bad are siblings. Although sibling shed the characteristics passed on by the common parent, they are not related by inheritance because one is not used to derive the other. In S hierarchies, features should be kept as high in the hierarchy as reasonably possible. That way, the only characteristic explicitly establish child cast are those that make the class distinct from its parent and from its siblings. So for example, if we have method in animal, let's say it. So all animals eat. So we'll keep it in the animal class. However, not all animals fly. So this method fly, we can created and the bird class. So this way also facilitates maintenance activities because when changes are made permanent, they are automatically reflected in the descendants. Always remember to maintain the is a relationship when building class hierarchies is no single best hierarchy organization for all situations. The decisions you make when you are designing a class hierarchy, restrict and guide more detailed design decisions and implementation options. So you must take them very carefully. Moving on to the object class in Java, all classes are derived ultimately from the object class of a class. Definition doesn't use the extends clause to derive itself explicitly from another class. And that class is automatically derived from the object class by default. So when we say in, for example, let's create a class. And let's name it. Thing will have a class called thing. This representation is equivalent to saying extends object. Because all classes are derived some object on public methods of an object are inherited by API Java class. They can be invoked through any object created and any Java program. The Object class is defined in the java.lang package of the Java's standard class library. So we have some methods in this object class, as it turned out, been using object methods while often in our examples, the toString method, for example, is defined in the object class. So the staining method can be called on any object. And this is why when we define a toString method and a class, we are actually overriding an inherited definition. The definition for toString that is provided by the object class. We also have another method that we view several times before. That equals it returns true if the object is an alias of the specified object. Classes often override the inherited definition of the.equals method in favor of a more appropriate definition. For instance, the String class overrides equals, so that it returns true only if both strings contain the same characters in the same order. So this is it for class hierarchies. See you in the next video.
7. Visibility: As we discussed earlier, all variables and methods, even private members that are defined in a parent class are inherited by the child clubs. They exist for an object of the derived class, even though they can't be referenced directly, they can be referenced indirectly. So let's look at an example that demonstrates this situation. Let's go ahead and create a new package, and let's name it. Visibility. And inside this package will have three classes. As usual. Let's create a class called food analyzer. And here we have our main method. And another class. Let's name it. For example, food item, Alaska's example. We'll name it beta. So now we have three classes. Put analyzer, food item and pizza. So the foot item is dependent glass and pizza extends. Foot is create some methods. So NPDES will create, for example, let's create a constructor. Simply public pizza, give it a value of GM and simply called the super method and put item that could create data. So this, for example, this super We'll take two parameters, the g that we get from the pizza method. And for example, let's say eight. And now we'll create the method in the food item so we understand it better. Now, here in the food item is create three integers. As create private galleries. 30 grams. Let's get it to nine. And another private. But grams. And lastly, create a protected. Now let's create our constructed and it will take two parameters. Let's name it food item. And you take two parameters. One number of petagrams, grams, and the second one is number of serving, serving. So now when we called the Super here, we actually called the constructor. And the food item class, it will take two parameters, so we have two parameters. Now. Let's go ahead and use it. We have fat grams and so banks. So just assigned fat grams equal to number of grams we already got from the user. And the same thing for the servings will number of servings. Now let's create some methods. For example, to return the calories, fat grams, multiplied by the calories per plant. And another method to compute the calories per serving, simply turn names, galleries, servings, and we simply calories and divided by the Serving. So we'll return galleries to to turn. Terrorists will have the method calories. We simply call it using batteries and divide it by the number of servings we have the number of servings in serving. And this is our calories per serving method. Now, let's go ahead and use this method and our main class. So we'll create a pizza. Pizza. Let's name it special pizza with a value of 275. And let's print out the calories per serving. Calories. That is per serving. And we'll get special calories per serving and run the code will get calories per serving, 309. Now, the pizza class is derived from the food item class, but it adds no special functionality or data. That's constructor calls the constructor of food item using the super reference, asserting that they are eight servings of pizza. The pizza object here called special, is in the main method and used to invoke the method calories per serving, which is defined as a public method of food item. Now, here our message should be private. And what we did here is that we could calories per serving, which is a public method. Then this calories per serving calls calories. Calories is a private method and galleries called fat grams and tellers per gram, and they are also private. So what we trying to say here that even though the pizza class cannot explicitly reference calories, calories per grams, and five grams. They are available for use in directly. And the pizza object needs cap. Bizarre object cannot be used tenfold the calories method, but it can call a method that can. So the foot item object was never created or needed. Now, since, for example, calories per gram is, we're absolutely sure that it is equal to nine. We can simply add here private, final and the chair. So what we're saying here is that this variable is finite and we cannot change it. Now, the other uses of the final modifier involved inheritance and can have significant influence and software design, especially the final modifier, can be used, curtail the ability is related to inheritance. So earlier we mentioned that the method can be declared as final, which means it cannot be overridden in any classes that extend that the one it is. The final method is often used to insist that the particular functionality be used in all tried classes. Now, the final modifier can also be applied to an entire class. Final class cannot be extended at all. So we can simply say that public class item. And now we'll have addressee saying that the type pizza cannot subclass the final class put item since it is finite and you cannot extend. So giving this declaration, this class cannot be used in the extends clause of an asset class. The compiler will generate an error message in such a case. Using the final modifier to restrict inheritance abilities is a key design decision and should be done in situations in which a child class could possibly be used to change functionality that you, as a designer, the civically wanted to be handled in a certain way. This issue comes up again and the discussion of polymorphism, and we'll discuss it later. So see you in the next video.
8. Polymorphism: Now we discuss polymorphism and other fundamental principle of object oriented software. Often the type of a reference variable matches the class of the object to which prefers Exactly. So when we're saying, for example, one equals new string. And say, now, what we did here is the type of reference variable is the same as the class object, which is now the term polymorphism then be defined as having many forms. A polymorphic reference is a reference variable that can refer to different types of objects at different points in time. The specific method invoked through a polymorphic reference can change from one invocation to the next. So suppose we have a method called duet. And if there's a reference object here is polymorphic, it can refer to different types of objects at different times. So if that line could discord, runs and then loop, or it is a method that is called more than once. That line of code could call a different version of the duet method. Each time it is invoked, we can create a polymorphic reference in Java in two ways, using inheritance and using interfaces. Let's look at each in turn, will start with Vodafone polymorphism via inheritance. So when we declare a reference variable using a particular class name can be used to refer to any object of that class. In addition, can also refer to any object of any class that is related. And it's declared type by inheritance. So for example, let's try this here we have our main method is create some classes here. For example, creating a class called mammal, another class creature. And the last class hosts. So we have three classes. The parent class, guess the creature, and it has a child class system Emile, it should extend. And this is the main mail, it should extend the creature. And and lastly, we have our course, which is a child class of domain, and it should extend it aswell. So now we have three glasses learned. Together with inheritance. Now, the main reference can be used to refer to any object of the class holds. So for example, if we say, let's name it H. So this is our object horse. And for example, we, for example, we can say equal to edge and to work properly. So this relationship works throughout the class hierarchy. So if the mammal class were derived from a cascode creature here, we can also say that Ranger, For example, let's limit c equal to nu. And that will work properly. And you can also sign into codes. Since Horus is the child of maybe. Now the reference variable SC can be polymorphic because at any point in time it can refer to an Animal object, creature to enable to the host. So suppose that all three of these classes have a method called move that is implemented in different ways and when this line is executed. So if creature currently refers to a creature object, if c refers to a creature object, the move method of the creature class is invoked. Likewise, if c guaranteed refers to a mammal object, the mainland version of MOOC is invoked. And finally, if C is currently country referring to a horse object, the horse, that the method in horse class will be invoked. So this is a general idea about polymorphism. And the next video, we'll do an example to understand it better.
9. Polymorphism Example part 1: Now let's take a look at another situation. So consider this class hierarchy. The classes in this hierarchy represent various types of employees that might be employed at a particular company. So let's explore an example that uses this hierarchy to pay a set of employees of various types. So first of all, we have the firm class contains in Maine, diverted creates a staff of employees and invokes the payday method to pay them call. The program. Output includes information about each employee and how much each is bad. If anything. This firm, we have the staff. It maintains an array of objects that represent individual employees of various kinds. So the area is declared to have to hold staff member references, but is actually filled with objects created from several other classes such as the employee volunteer, executive. And these classes are all descendants of the staff member class. And so the assignment are valid. The established array is filled with polymorphic references. So here in this staff member, we can access volunteer employee executive, undoubtedly. Polymorphic way. Now, each class has its specific characteristics. So all workers need to have name, address, and phone. But if a person is opponent td, it doesn't have to have a social security number or a pay rate. And this is where the volunteer is different from employee. And the same thing for executive and hourly. So executive have, has a bonus and hourly has worked out. So let's go ahead and create our classes. To start with. Let's create our package. So let's finish with an example, example polymorphism, and we'll create our class. We have here our main method. Let's go and create another class. Create the staff member would name it stuff. So we have our second class. Then. We also have let's go and see what. We have our staff, we have staff members. Create staff member class. Then we have volunteered employee Scott, this is the potentate in class. And then we also have executors, and these are the last two classes, executive. And lastly. So now that we have created all our classes, let's assign them together. So we have the staff member, volunteer, and employee that extend the staff member. So volunteered right here extends staff members. And the same thing with employee staff member. And as we can see in this class hierarchy, we have executive and child classes of employee. It's gonna go here and extend them from. And the same thing with extends. And let's start with staff member. As we can see here, we have a staff member, three variables, name, address, and phone, and to method's toString. And let's go ahead and create them. And ourselves. Give them a protected reference name, address. And we'll have our three variables. And now we can create our constructor to setup the staff member using the specified inflammation. So we have these three information to create. Our constructed these information as usual. And the three strings in the address bar. And simply assign them to look at variables. And for n equal to p. So this is our constructor. Now let's create our two methods. We have toString, toString, and it will print the name, address, and phone. Go ahead and create this. I called three, which we have name plus, plus. Let's create a new line by simply you line by simply typing n. So this is our Name. And on the second line, we would address. Address. And the address. The last line, phone number. So this is the phone number. And now we need to add a new line. So this is our toString method, and finally we return the result. Now, the last method we have in this class is the Dublin bay methods. Methods doubled. Every employee has a different payment method, will let the derived classes to define a method for each type of employee. So this method will not have any body. So this is why it will be abstract. And we should also assign the class to be abstract also. Since we have an abstract method. So this is our staff member class, and we continue with the other classes into next Purdue.
10. Polymorphism Example part 2: Now, since we're done with our staff member class, will move to our volunteer. So we have an adder here saying that the volunteer must implement the Inherited abstract method. Staff member. Now will inherited. But before, let's go to our class hierarchy and see we have an volunteer didn't just have a double B method. So let's go back and create our constructor. We have constructor volunteer, twill take as usual, three strengths. Spank and a address has to be performed. And our super constructor and give these three values. So now created our constructor. Let's create our method, which is B. And as a volunteer will not pay anything. We just returned 0. So this is our volunteer class. Now let's move on to our employee class represents a general paid employee. In this class. We have our constructor as usual, but let's go back to our class hierarchy. We can see that we have two new variables, social security number and bade aid. We have two methods to string and pay. So first of all, let's create our two variables. Protected string. We have the social security number, and another protected with a double type eight. Now again, create unconstructed public. And the parameter now we have five variables instead of three. We have the name, address, and phone. And we'll add social security number and period. Let's go ahead and into these five investing and for name, for the address, the phone, and ask for Social Security number. And lastly, a double standard played. And what we're going to do is to assign the three variables as usual to the super, using the super reference to the constructor class. And now we're done with the name, address, and phone. They are automatically. They went to the staff member and they are assigned here. And now would work with our social security number. Social security number, we'll give it a value of S. And the rate we have baited with a value of rate. Now, let's work with our methods. We have two methods that toString that we need to modify and the rate that debate. First of all, let's go and modify the two strands. Who's tank method? And if we use super D2 strain will get the toString method, what we store it here. So we get name, address, and phone number. So let's go ahead and use a tiered. We have. Let's create a slang called result and use the super to call the toString method and staff member supertype. To. Now we have all the information and the staff member as numbered address and foreign in here. And we'll add to our social security number by simply saying social security number with a value of social security number. And then return the result. To. Now, we're done with this method. Let's go ahead and work with our bay method, which is public and would return a value of theta. Now, this is our employee. Lets go and work with our executive. And now let's go back to our class hierarchy and we see that executive have bonus, the w variable, bonus and two methods, our bonus and they would go to the executive and a new private double bonus. Let's create our constructed now public executive and give you some values we have as usual, the name and the address is found, then the social security number, name address. And finally, there are eight. And as usual, we'll call the super, Give it a name. Address BY phone as social and raise. The bonus here will be equal to 0. So we set bonus equal to 0. Now this is our constructor. Let's create our two methods. We have awoid bonus, public, poet bonus. If you take a parameter of a tablet, Let's name it coronas, and we'll assign bonus to this box. And the last method is pay will compute and return for an executive, which is the regular employee payment plus the onetime bonus. So we get our method. And this method, let's create a payment, which is super good. So we'll compute the pay date as usual from the employee and plus the bonus and then return. So this is our executive class. Let's go now to our class. And our class we'd have a new variable, hours worked and three methods at ours and to string. So here, first of all, we create our private variable, worked hours. And let's create our constructor as usual. And we have a, B, Jang. And finally, and we'll assign these four variables, five variables to the super AND a, B, S, and R. And give the work hours the value of 0. Here we don't have a method called add hours to add our Avoid method, public hours and hours. And it will assign wild hours. So whatever we have, invert hours, we add these hours to it. And another method is the debate for this employee. So in this method would return. And we have a double payment. And payment is paid. We have to pay rate times how many hours they simply work. So we have our work hours. And then after that, every time we pay, employee will automatically reset to 0. Then we return into payment. So this is our payment. And lastly we have our toString method is public string. And we can just take the result from the tank and then modify it by adding that current hours. How many hours damper currently work. So we add a new line. And then we'll add, let's say current hours and hours, worked hours. Then return the results. We finished with our parent and children classes, staff member, volunteer, executive, and avidly, the next video we'll talk about staff and for classes.
11. Polymorphism Example part 3: Now we still have two classes, firm class and the staff class. Let's work with the staff class. Inside this class will create a list of some staff members. So private staff member, as Adam and his name is, stuff, gets create a constructor to set up a telescope staff members by simply with no parameters and will give this stuff list value. It is the new stuff. So we have eight elements in this list and and have some elements. Stuff list, position 0, executive for example. It, the string name. And the address will be 1-2-3. Mainline phone number, for example, let's say minus 0.51111. And this Social Security number, it is, for example, the 123456789. And lastly, the rate is, for example, let's say 2423.07.07. The element at position one, employee and employee. And as usual, for example, as usual, let's say for example, 0.01. Social Security number 12345451234. And lastly, iterate, say one hundred and two hundred forty six. 0.15. And we do the same with the others just to not to copy them. And so this is the second 17567. And let's change Haiti for example. Let's say, let's keep it as an employee at the second one. And then the one after it gets broken as a teacher. And the other one has enough, so adjust the and make it size six. Now, let's modify this name, this employee. And by 55 to phone number and 99. And lastly iterate for example, 3,246. And the same here. And we have the 999. Same thing heated. Let's change the numbers and the rate as usual. For example, let's set it to 1010. And lastly, we have to vote and t is known. And it was just the name, address, and phone number without these two additional. So let's go ahead and delete them. And this is our first one, and this is our second volunteers. Just change here. P5. And yeah, this 123 main line. And he is. So these are, these are our members and this list. Now we still have two methods. One and executive, a word poisonous and gathered and ours. And let's use them. And our staff members, our staff member. Now, we need to work with executive. So we simply write executive. And to say to the program that we need an executive staff member. We're specifying what the staff list when you start to put it in parenthesis and upward bonus, and that's 500s for example. And the same thing. And we will have staff listed three. And now we have the staff, the payday method to pay it or the members. So after creating the constructor will create a public void payday. And we have an amount to pay, so we'll save it and it doubled the amount. And first of all, let's print every staff list. Every member in the staff list by printing. And then if the amount is equal to 0, then it is surely a volunteer. Then we'll just print tanks. Otherwise, would print the amount that we're going to pay. And the amount is equal to every established. With the method gives the amount is equal to 0. Then just thanks. It is a volunteer just thanking him. Otherwise, when I'm out. Plus the amount. Now we have our method in the staff. Let's go ahead and use it in our firm. So he recreate the staff object. S is the new stuff and use a method. And let's run the code, see what will happen. So here we have first of all, our first. Let's go back and print the line between F3, less every member in the list and this list, just to, to be more clearer. So after printing every, every amount, print a new line. And now inside the photo and run the code one more time, we get the same output, but with a line to divide every member in this list. So first of all, we have some address, phone number and the amount, and then we have the same thing. And lastly, we have to volunteers. And known and Karla, since they are volunteer, will not print the amount because they are not getting paid. So we just print. Thanks. So I think that this example demonstrates the use of polymorphism we have established. And every time staff member, every time it will print different things since every time to work differently. So this is it for polymorphism. See you in the next video.
12. Recursion: We've talked now about recursion. Recursion is a powerful programming technique that provides an elegant solutions to certain problems. We've seen many times in previous examples that one method can call another method to accomplish a goal. What we haven't seen yet, however, is that a method can call itself. Recursion is a programming technique in which a method calls itself in order to fulfill its purpose. But before we get into the details of how we use recursion in a program, we need to explore the general concept of recursion. The ability to think recursively is essential to being able to use recursion as a programming technique. In general, recursion is the process of defining something in terms of itself. For example, let's suppose we wanted to formally define a list of one or more numbers separated by commas. Such a list can be defined recursively as either a number or as a number, followed by a comma, followed by a list. So we can say that we want a number followed by a comma. And then so these are two examples. We have a number and then a comma, and then a list. No matter how long the list is, the recursive definition describes it. A list of one element, such as this example, is defined completely by the first non-recursive part of the definition for any list longer than one element that it goes if part of the definition is used as many times as necessary until the last element is reached. What we're saying here is that we have a number and then followed by a comma, and then we have a list. And then the same thing goes for 88 is a number, followed by a comma, then followed by that list. And 40 is the number comma, and then a list of one element. And finally, we have a number. Now, the definition of list contains one option that is a cursive and one option that is not. The part of the definition that is not recursive is called the base case. If all options had the recursive component, that recursion would never end. For example, if the definition of lists were simply a numbered followed by a comma, followed by list. No list could ever end. This problem is called infinite recursion, dissimilar to Glenn infinite loop, except that the loop occurs in the definition itself. So now let's go ahead and talk about recursion in mathematics. For example, let's suppose the n factorial. So let's say and factorial. So the value referred to as n factorial is defined for any positive integer n as the product of all integers between one and n inclusive. So if we say n factorial is equal to three times two times. One is six. Now, the same thing if we say five factorial is five times four times three times two, all the way to one. Mathematical formulas are often expressed recursively. And definition of N factorial can be extra expressed as. And factorial is equal to n times n minus one. Here we have factorial four and bigger. So as long as n is greater than one, n factorial is equal to n times n minus one factorial. And the same thing goes for this. And so on. Now, the base case of this definition is one factorial. One factorial is equal to one. All other values of n factorial defined recursively as N times the value n minus one factorial. So using this definition, when we saying 50 factorial, it is equal to 50 times 49 factorial. And 49 factorial is equal to 49 times 48 factorial and so on. And this process continues until we get to the base case of one. Because n factorial is defined on the positive integers, this definition is complete and will always conclude with the base case. Now, let's work with bacteria and programming. First of all, we should create a matter method to return an integer. Let's name it factorial and the twill take an integer as payment. And now, as we said, the base case is when n is equal to one. So we'll say if m is equal to one, we'll just return one. Otherwise, if n is not equal to one, we just returned and multiplied by the factorial of n minus one. Now, to perform this operation, we just call the method one more time with parameter of n minus1. Now let's go ahead and use it. For example, let's say that n is equal to four. And this method and, and run the code, we get 24. So what happened here is we, we performed factorial with a parameter of four. So it goes to this method. We have for it is not equal to one. So we have four times the factorial n minus one, which is three. So four times factorial three. So we have four. Strike here, four times something. Now factorial of three, it goes to the method one more time. We have three times factorial two. So we have three times something. And the same thing, one more time, two times factorial 12 times factorial one. So the last time we entered the method, we have n is equal to one, so just return one. And this is it, it is four times three times two times one. So we'll print this four times 312 times 224, and we'll get 24. Now, we might face something. For example, if we enter a negative value, let's say minus seven, we'll get an error. Because we didn't deal with this. We just have the positive number and multiply it by the number below it. And we have the base case, which is when n is equal to one can fix it by saying while n is less than or equal to one, return one, so we get one. And if we don't want to get one, for example, if we want to get minus1, we can say that if n is less than equal to one, return minus1. And, and then we move this from here and run the code, we'll get minus one. So this is a small example and recursion. And in the next videos, we'll explore it more.
13. Example: Sum using Recursion: Let's now use another simple mathematical operation to demonstrate the concept of recursive programming. Consider the process of summing the values between one and n inclusive, where n is any positive integer. The sum of the values from one to n can be expressed as and plus the sum of the values from one to n minus one. So we can say that sum of n is equal to n plus and minus one. So let us keep this here as comment. And let's start with our method. Let's name it. Some public static returns an integer with the value and, and our base case being deaf and is equal to one. Return one otherwise would be turned the number and plus sum of n minus1. So as we said here, we should return some of n is equal to n. This is n plus the sum of n minus one. And this is our method and let's use it here. Print out some of averages. In this case four. We get four plus three plus two plus one equal to ten. Now, the base case in the summation example is when n is equal to one, at which point no further recursive calls are made. The recursion begins to fall back into the earlier versions of the sum method, returning the appropriate value each time. Each return value contributes to the computation of the Sun at the higher level. Without a base case, infinite recursion would result. The sum function different initial values of non end and until the processing becomes familiar. So in this figure illustrates the recursive calls when the main method invokes some to determine the sum of the integers from one to four. Each box represents a copy of the method as it is in. Invocations are shown as solid lines here and returns as dotted lines. The return value result in is shown at each step. The recursive path is followed completely until the base case is when sum is equal to number here, values equal to one. And after that, the base is now reached. So the cause then began to return the result up through the chain. So when n is equal to one, we begin to return their results. First of all, we return one. Then we have two plus 133 plus three is equal to six, will return 66 plus 410 would return ten. Now, of course, there's a non-recursive solution to the summation problem would just explored. One way to compute the sum of the numbers between one and a number and inclusive in iterative manner is, for example, we'll use the for loop for one to n inclusive, so equal to n and sum plus equal to. And first of all, we have an integer, sum equal to 0. And then we print out some plus sum, and here we need to add. So sum is equal to 0 plus one plus two plus three, plus five plus four. And when i is equal to four, the exit, the for loop and print sum. And here I added a print line here. Now, if we run the code, we'll get some is ten. Now, of course here we can say that i is equal to one. And we get the same thing. Or can set r is equal to one and start with i equal to two. And of course we get the same result. Of course, the solution is certainly more straightforward than the recursive version. We use the summation problem to demonstrate recursion because it is simple, not because you would use recursion to solve it under normal conditions. Recursion has the overhead of multiple method invocations and in this case presents a more complicated solution. Then it's iterative counterpart. The programmer must learn when to use recursion and when not to use it. Determining which approach is best depends on the problem being solved. All problems can be solved in an iterative manner. But in some cases, the iterative version is much more complicated for some problems and allows us to create relatively short, elegant programs. Finally, we'll talk about direct and indirect recursion. Dialectic corrosion occurs when a method invokes itself, such as when some goals, some indirect recursion occurs when a method invokes another method, eventually resulting in the original method being invoked again. For example, the method m1 invokes a method M2 and M2 invokes method m1. We can say that m1 is indirectly recursive. The amount of indirection could be several levels deep. As when m1 in books, m2, which invokes M3, which invokes M4. And finally, this method and for invokes m1. And direct recursion requires all of the same attention to have cases that direct recursion requires. Furthermore, in direct recursion can be more difficult to taste because as the intervening method calls, therefore, extract is one ended when designing or evaluating in directly recursive methods. And showed that the indirection is truly necessary and clearly explained as you want.
14. Recursion: Maze part 1: After using recursion for some simple programs, now use it with more complex ones. Let's go ahead and create a new package. Name it programs. And we create two classes. Two fabulous. That means we have the first one is named maze search. Here we have our main method. And the second one, we'll name it maze. Now it's toggling amaze involves a great deal of trial and error, following a path, backtracking when you cannot go further and trying other untried options. Such activities often are handled nicely using recursion. We have our two classes. This is our driver class, may search. We have a main method here and our maze where we'll create our recursive method. So here, first of all, let's write MAs and we'll use the two-dimensional added. Will never used it before, like an array, but a two-dimensional one. So we'll use a two-dimensional array of integers to represent this maze. And the goal is to move from the top left corner to the bottom right corner and write it down and then we'll get back to you. So this is our maze. Initially, a one indicates a clear path and a 0 indicates a black path. As the maze is solved, these array elements are changed to other values to indicate attempted paths and ultimately successful path throughout the maze. So we'd have two values. One will give them a reference final, and one is, let's limit. So if we try a path, then the value will be 31 over the past Less naming path. And we'll give it a value of seven. Now, the first method we're going to create is the toString method to print this grid, this maze. And to go ahead and we'll use the public. Here we have strain. Strain and he would return. A maze domains will create as a string. So first of all, we have our strength and stamina. And this result. First of all, let's print a line and print a line here. And we just print this. So we'll create two for loops nested for loops. One for the rows and the second for the columns. So here we have the Great dot length. And the other one insight is that length. So if we say great I that length. So we'll take every row and, and we'll see the length of the stroke. So he will have 131313. So the length of the outer for loop as eight and the inner for loop is 13. And now we'll go ahead and store them in the result. We store the grid at i and j and add double quotations here. And we've done, after that, we'll just print aligned. So with that here and you line. And it's going to add these up. And then we should pretend the results. So let's go and try it out. An object means let's use the toString method and printed out the code. Look at our maze. So this is our mains. Now, as we said, one indicates a path and 0 indicates a block. But now, to know if this position is valid or not, I will create a method, let's call it pilot. Before creating our because if method. So we'll go ahead and create a new method. Let's name it. And it will return true if this position is valid and false. If not. So, take two elements. And finally, we have Boolean result. First of all, it is false. And now we check if the cell is in the bounds of the matrix. So check if rho is greater than or equal to 0. And if rho is less than or equal to that length. And of course, the same thing for column. If current is greater than or equal to 0 and column is less than or equal to rho dot length. So this is the case. Then we check now if the cell is not blocked and not previously tied. So if that grid row equal grid row and column is equal to one, then this is a pilot move, would never tried it before and it is not blocked. So if it's not equal to 0 or it's not equal to three, then we go ahead and we'll get the result. We change the results from false to true. And then after that, we returned the result, whatever that result is, true or false, would return it. Now. So this is now a method to check if this is a valid move. So what we're saying here is, for example, let's check this position. So this is at position 012 and approach 0. So first of all, this, if you want to access this position, we can write cred, row and column. It is at column 3012. I'm sorry to hear. So at position 02, we have this 012, we have this position, that 22 here, 03, 0s and so on. So this method valid, first of all, we'll take the two parameters, row and column. And first of all, it will check that the cell, it is the bounds of the matrix. So if rho is greater than 0 and lower than the length, so if it is between 08 and same here, it will check if the current is between 0 and the length 13. After that, if this is the case, then we go ahead and check the number and discrete. So we'll access, read joe Cannon in this case 12. And we'll see here we have 12012012 here. So this is 12. If it is equal to one, then we'll change the result to true. In this case, we have one, so we'll change it to true and it will return result as true. Now we have all the tools and we tend to start with our recursive method. So we'll start with it in the next video.
15. Recursion: Maze part 2: We still have our last method, which is our recursive method. And the only valid moves through the maze are in the full priority direct directions down, dried up and left. Not diagonal moves are allowed. So in this example, the maze is eight rows by three columns. Although the code is designed to handle amazed of emphasize. But for now, let's work with 813. So let's think this through recursively. The ms can be traversed successfully if we can traverse it position 00 to the position 712. So in this case at position 00, we need to work with it, so we'll check if it is a valid position. If it is valid, it is equal to one. Then we have four directions. We have 01100 minus one and minus 10, minus 10100 minus one and not valid. So we still have two valid moves, which is 0110. And we'll go with 01 for example. And we'll check if it is valid. It is valid. And, and now we'll find ourselves in the same position as we were in the first one. So we also have four directions, up, down, right, and left. And we need to check between them. So the same thing occurs every time we move in this maze. Now, let's create our method. Let's name it Avars. And this method is Boolean. Return true, pretend travels the maze and false otherwise. Public boolean. And to start with 0-0 scholar 22 parameters, intro and incarnate and would work with the body here. First of all, we need our boolean. Let's name it done. First of all, it will be equal to false. And at the end of the method, we should return a Boolean. So we'll return done. Now. We need to check the position we are in is valid. So we'll use the valid method. We created a leverage. So if valid, we'll give it two parameters, row and column. And if this is the case, we'll work here. After checking that this is a valid position. Now will change it from one to three since we tried it. So we'll change the grid row and column from one to three since we find it here. So we can say that This has been tried. Now, there's only one case where the mains will be solved and we return true. So it is when rho is equal to the length of the grid minus1. So rho equal to that length minus one, and m is equal to red row minus one. And then we'll change done from false to true. Otherwise, we need to check. So here we are saying that if we are in the position 712 in this case, since dot length minus one is eight minus 17. And quid pro dot length when S1 is 13 minus 1 12th. So if we are at position 712, then the means is solved. W1 equal to, and then we'll return done and we're done. Otherwise we need to check with not in this position yet. We need to check the down by using w1 equal to traverse down. We'll add row one. So if we are at pro 66 plus one, we know across seven row one with the same column. And the same thing is not done. Or we can say if w1 is not equal to, is equal to false. If we still not done. Same thing. We try write row, column plus one equal to rho minus one. The same thing. Try ro minus1, row and column minus one. So this is it. And now we'll explain it. But before dun, dun and dislocation is part of the finite, but then we need to change it from three or one or whatever to seven, which is equal to. So this is what we did here is we created a method called the traverse, which is a Boolean method. It returns a boolean value that indicates whether a solution was found. First, the method determines whether a move to the specified row and column is valid. So a move is considered valid, as we said before, if it stays within the boundaries and if decade contains a one in that location indicating that a move in that direction is not blocked. So the initial call to traverse passes in the upper left location, 0-0 will start with 00. And if the move is valid, that Vint entry is changed from one to three. If it is valid, then will change the grid entry from one to three. And then so these marks that delegation as visited so that later we don't retrace our steps. And this method then determines whether the maze has been completed by having reached the bottom right location. So if we have reached the bottom-right occasion, then would change done from false to true. And our maze has ended then. And otherwise we have some steps to follow. So in this method, we try out different paths. So for example, we can start by U1 and then go down one. And he were blocked by three zeros. And actually there is three, there are three possibilities of the base case for this problem that will terminate any particular because of the first one if an invalid move, because the movie is out of bounds. So for example, here, if we get to here, we have one and the left position is out of bound. So it will terminate the program. And other one is an invalid move because the moon has been tried before. So for example, if we go here 21 and then go back, then I don't know, maybe go try left and then go back to the two down. We tried it before, so it will not be valid. Lastly, a move that arrives at the final location. So after going through the maze and reaching the bottom right here, one, then we have sought the maze and it will terminate our path. Now, currentLocation is at the bottom right corner. We searched for a solution in each of the primary directions if necessary. First, we looked at me, looked down by recursively calling the traverse method and passing and the new location. So the logic of the terrorist method starts all over again. Using the new position. A solution is either ultimately found by first attempting to move down from the current location or it's not found. So for example, if we start with 00 and we have here 01, research down first, first, we have 010, excuse me. So here we are at position 1-0 would try all the logic again. And we'll check first of all down, we have nothing, we have 0. Then it is not valid. Then we'll try, right? 0, we cannot try right? Since it's not valid, then we'll try up. Now is equal to three, then it's not valid also. Then finally would try left, which is equal, which is out of bound. So this is not valid. Then we'll return false and go back to here. After that, what we'll do is to try derived. We have here in the right position. It is 01. So here we are at location 01. First of all, we'll start by looking down. It is 0 invited. So we'll go back here and look, right, we have one, it is valid. So we go to this position x. So now we are at this position, will do the same logic all over again. We start by down, we have one, we find the path. The same thing with one. We go and search down. We have 0 invalid, go with right. The same thing here. Until we reach either a blocked move. If I added one and continue until we reach the bottom right corner, step-by-step until reaching the bottom right corner. But for now, we'll go to the search and we have, this method is booleans. So we create a Boolean variable, name and maize. Two equal to M. Traverse would start with 00. So if this is equal to true, if maze, we can say equally good, leave it empty. Data at the same. And if this is a case, just print was successfully. Otherwise, we'll print there is no possible path. And finally, we'll print out the maze. Run more time. Go ahead and run that code, will get the maze was successfully traversed. And here we have our path 777 down Seventh, down until we reach here than up seven, all the way down, and then up until reaching the last dime and the bottom right corner. So this is it for the maze problem, problem. And in the next video we'll talk about Tower of Hanoi.
16. Recursion: Towers Of Hanoi: And this example will serve the Towers of Hanoi puzzle. The Towers of Hanoi puzzle was invented in the 18 eighties by French mathematician, has become a favorite among computer scientists because it's an illusion is an excellent demonstration of recursive elegance. The peasant consists of three upright bags and a set of disks with holes in the middle so that the slide onto the backs. Each disk has a different diameter. Initially, all the disks are stacked on one peg in order of size, such that the large, the largest disk is on the bottom, as shown in this figure. And the goal of this puzzle is to move all the disks from the original peg to the destination PEC. But this is the original bank. The destination pack is this one. So we can use the extra Peg as a temporary place to put disks. But you must obey the following three rules. First, we cannot place a larger disk on top of a smaller disk. For example, we cannot take this desk, place it here, and then take the other one and place it on top. Second, We can move only one disk at a time. And lastly, old desk must be on some peg except for the desk in transit between packs. So we cannot take today from the towers. These rules implies that you must move smaller disk out of the way in order to move the largest disk from 1 to another. So here we have an example step-by-step solution for the towers of Hanoi puzzle using three desk. So in order to ultimately move all three disks from the first peg to the third peg, you first have to get to the point where the smaller to this out of the way and the second bank so that the largest disk can move from the first peg to the third peg. Here we have the original configuration. So first of all, we move the first, this the smallest disk to the last Peck. And then after that we move the second one to the, to here, to the second peg. And then we'll take back this smoke that the smallest disk and put it on top of the second disc. And now we can move the last disk from here to the destination. And then we move the first disk to the first bag. Move the second disk, did the last bag, and then move the first disk to the last page. So we have seven moves. And this example, while using three. Let's use this idea to form a general strategy. So to move a stack of n disks from the original peg to the destination peg. First of all, we have here n disks. What we did is that we moved and minus1 to disk from this peg to the second peg. So what you should do is to move the top most n minus one disks from the original peg to the extra peg here. Then move the largest disk from the original peg to the destination Peg, as we did here. And finally, move the n minus one disks from the extra peg to the destination pack and use recursion early. So the step to move n minus one disks after the way is the same problem all over again. So when we have here and minus1 desks here, so we need to move them back here. We can perform the same steps as usual. And after getting to this point, we can then perform the same step. All other account. So now let's go to this program and create a new package. Our gathering. Here we have our main method. And the second class, we name it Tower of annoyed. And now, first of all, we set up the puzzle with a specified number of disc. So we create our constructor towers. And then it will take an integer, how many disks? So name it. And we have, of course, I would local variable total desks. And what we'll do is to equal to n. And now we need to solve this program, this button. So we'll use two methods here. The first method is to move the specified number of disks from one tower to another by moving a subculture of n minus one disk to the way. So as we said, what you do is make it private. We'll name it move tower. And now today the number of disk as parameter and the starting and the ending, and the extra one. Now, as we said, if we only have one desk left, we just move it from here to the last Peck. And so this is our base case. If number of this equal to one, then we just move it. So let's create the method that will move the disks will instead of writing it every time here. So we have private void. Let's name it, move one disk. Today, two integers is starting from where we are going to move it to two. And until it will simply print that move one disk from start to the end. Now, so if the number of disk is equal to one, then move one disk from the start to act. Otherwise. What will do is what we said here. So we need to move n minus one disks from the first peg to the extra peg and then move n minus one. Move that last from the first day starting peg to the ending peg here, as we can see here. And then move these back to the first peg. So as we said, we need to move. The first step is to move n minus1 from start to extra. So we'll perform this move tower. We have n minus one here, so a number of minus one. And we start with start. And we moved them to extra. And the excerpt bag would be the ending Peck. After that, we need to move one disk. Now we're here. So what we should do is to move this disk from the first bag to the last peck. So we perform this operation by simply calling the method that you created here. Move one death from start to end. And lastly, we should move these disks to the ending pet. So we'll create, moved our number of death from the extra, the extra here to the end. So here we have and, and start. And now this method is said. Now, we can create a public method just to use this method easily without entering the start and end extra, rename it to sold. And it will take total disks as parameter, an integer. And two simply called moved our method with a number of this, which is the total. This bag is the peg number one, the end is three, and the extra one is two. And now let's go ahead and run this code and our main method. So we'll create an object Tower of Hanoi and T, the new towers of Hanoi. And let's use it with 34 desk. And here we have soil. And this code will get following lines. And the same thing. For example, let's say ten. This will get so many lines to move all the disks from the first peg to the last one. Now, think of the iterative version. How would look like? And if it is as simple as this recursive version. So this is it for the tower of Hanoi problem. And see you in the next video.
17. Insertion Sort: Consider you have a list of integers such as this list. And you want them to be sorted from lowest to highest. Hey, you can use salting. And there are actually multiple sorting algorithms and we'll talk about some of them. So inside by insertion sorting. Insertion sort is a simple sorting algorithm that works similar to the way you saw playing cards in your hands. The array is virtually split into a sorted and unsorted part. Values from the unsorted part are picked and placed at the current position in the sorted part. Two here we can start with this example. Let's suppose we have this list, and this list will be divided into two parts, a sorted and unsorted part. So first of all, I will solve it by two, will be the first element only. So this is our first list and this is the second part. Now, four is already sorted since it is only one element, there is only one element in this list. And you don't have to do anything. There is no element to the left of that is greater than four, then we need to add three. So we have 43. We compare three with four. So four is greater than three. So we should swap them and we'll get 34. Now, the sorted part of the list is 34 and the unsorted part is whatever there is here. And we'll move on to the next element. We have to compare two to 44 is greater than two, then we swap them. And the same thing we compare two with 33 is greater than two also. So swap them one more time, we'll get 234. And now this is the sorted part, and this is the unsorted part, and so on until reaching the last element of the list. And then we'll be done. So the general idea is to compare every element with all the elements to the left. Swap. Every time we find an element to the left greater than the element we are using. So let's go ahead and write the code. You go and create a class. And first of all, let's create our integer array, our list of integers. And for example, we have five elements in this array. Let me store them directly to 5110. So this is our array and let's create our Method. But let's name it insertion. And to take parameter an array, let's name it at work here. So first of all, we have the for loop to pass through all the elements from 0 to listed length minus one. Zeros are already sorted, so we don't have to start with 0. So we start with one. So our for loop result with one and ends a dot length minus one. Now we'll create an integer. Let's name ID key, and it will be our element in this list. So we'll be comparing a of i. So here it is three to 1012 and so on. And we sold it and an integer called game. And we'll have another integer will be j, i minus one to start by minus1 and go back until reaching 0. And what we're doing here is that we're starting this number, for example, that the state does case. The third line, third key in an integer. And we thought this number to an integer called key. And then we stored the position we're recovering to start, which is the position i minus one, j i minus one. So we're going to side with this position and going back until reaching 0. So we'll create a while loop. While j is greater than 0 and the key is less than a of J, we need to swap. So to saying here is that y j is less, is greater than 0. So here in this case j is equal to one. So good. And the second condition, while key, which is two, is less than a of J, in this case four. So we need to swap them. We swap. And then one more time, we check the conditions. We have j greater than or equal to 0. In this case, j is equal to 0. So that condition is valid. And two in this case, we have here too and here four, so 23, so three is greater than two, then this also valid. We need to swap one more time. And then we finish with this for loop since j will be greater than 0. And in this case, so every time we execute this for loop, j will be decremented by one. And here we need to swap this, create an integer called tamp. And as usual, that swap them will take a of j and storage here, and ten and a of j. A of j plus one in this case. And finally, we'll take a j plus one and give it the value of w. So here we swap them. And now we said, let's go back and print out. First of all, let's print the array as it is before sorting. So print at a and some space. Then perform this method with an a. And then that's printed one more time. For let's print the light from the code and time and will get first of all, the unsalted added and then we get the sorted one, since we used the insertion method we created here. Now we can see how this changed every time. So let's print out the array to create another for loop after each change. After executing the loop. And print out a J2, in this case, some space. And and then, and here we need to print an island. Before executing this loop and run the code will get this. So first of all, we have 32510. We start with i equal to one. So I equal to onRestart, t equal to a of i, j is equal to a of 12, and j is equal to 0 in this case, which is i minus1 0. Then we have a while loop that will run only one time since J is equal to 0 and then read recommended. So the condition here, it will not be valid for another execution. So we need to swap them since the two conditions are satisfied. The same thing with five. We compare five to now. Five with 25 is greater than two, then this condition is not satisfied. Will not enter the for loop with simply though and increment I by one. Now we have number one. The same thing here. We'll compare this one with every element and swap the two numbers. So for example, 15 will swap them. And then 13, we swapped them one more time. And lastly, 12, swap them. And lastly we'll have Dan. Dan is greater than all the other elements. So it will not enter the loop, the while loop, and we'll be done with the two loops, the inner and outer loop. And we can print, print telling you look out and a new array out. So this is it for insertion sorting. We'll explore more sorting algorithms in the next videos.
18. Selection Sort : Let's move on now to another sorting algorithm is the selection. The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning. Now we're considering ascending order. We also have the descending order in which we can find the maximum element and store it at the beginning. And as the insertion sort, we have two parts. The one that was already sorted and the unsorted part. And every iteration of selection sort, the minimum element from the unsorted sub-array is picked up and moved to the sorted subarray. So let's use an example. We'll use the same list here. And let's delete this. We have this method, delete these. And we'll keep this method work here. But before, let's run this code and use this list. Now. But we're going to do in this sorting algorithm is to find the minimum every time and store it at the unsorted the sorted part. So first of all, we will find the minimum and this list here we have one as the minimum, will take this 11 and swap it with this number. Whatever this number is, we'll swap it with one. So here we have one now. And so let me write it here. So we have 1253 and that the next step is to find the minimum and this list. So the minimum is true, and we need to start it at this position. So we're okay since the minimum is two. So the next step would be the same as the first one. Sense, we don't need to change anything. Now, we will look at this list. We have 5310 and we find the minimum here. The minimum is three. We need to store it at the first element. So we need to swap three with five to the next. That is, to swap them. So we'll get 123510 and glass scheme compared these two numbers as usual, Find the minimum between them and store it at the first element in this list. And since ten is greater than five, then we don't need to do anything. And this is our final list. So now let's go ahead and write it as a code. Public static, void, selection parameter of an array, integer. And in this case, for example, first of all, we need to store the length, the length, length to use it in the for loop. So here we have the length of this list. Beside our for loop, we can say array.length or both, the same. And now we need to find the minimum element in the unsorted part. So the unsorted part should be starting with i plus one. So every time we finish with I will compare and find the minimum in the part of i plus one at the length. And here we have n minus one. Since we don't have to end at the last element, we can simply add and here. And the inner for loop would compare the two last element. So in this case, let's store the minimum as i equal to i. And now we should find the minimum and the unsorted part. So we start with i plus one and the angled array, array.length or and the same Maxwell simplicity. And now we'll compare every element to find the minimum. So first of all, we considered that the minimum is at index i. The index and an integer called minimum. Firstly, I is equal to 0. So we considered that the minimum number in this list is at index 0 to go and look at index 0. So we'll find three and it's not the minimum. So we need to compare this number with all the others. And that's what we're going to do to compare a j. In this case, j is the list from i plus one from here to the end. So if i of j is less than array of men, then we need to swap the index and men, it will be actually the next. So what we're saying here is men would be equal to, and let's work with this example to understand it better. So first of all, we'll start with i equal to 0, i equal to 0. We store n minimum 0. Now we are looking at this number and j will be equal to 0 plus one is one who sat with one and, and with 1234. So we'll end with four. We'll compare array of one. F of one is less than array of men, I of men. Remember, many xn equal to 0 and J, in this case it's equal to one, will go and compare T2, which is adding one with three, just array of minimum, array of 0. F. Two is less than three, then minimum now is not this one anymore. It's not at index 0 anymore. It is at index j, in this case at index one. So we'll give minimum and nu value of one. And the same thing as before. Now, J is equal to two. Would compare j, I, a of j and a of two. We have I2 here, five with any of the new minimum, which is one. So you should compare now as five with 25 is greater than two, then nothing will happen. Then we go to here, we compared array of three, which is one with L2. So one is lower than T2. So we need to give the minimum and new value, the value of one. And finally, we have here at which index, the minimum value as after finding the minimum using this for loop, we need to swap this minimum with the element at the sorted list where we should sort them. So what you should do is as usual, we'll take a minimum consulted in an integer called damped than. We change whatever there is minimum with our eye. And lastly, give this i index ID array at index i, the value of n. So here we swap them and let's go back and use this method here. So selection and the arrays, array, and the same thing. We'll print them and we'll get 123510. So I think that selection sort is easier than the insertion. So in terms of understanding, it is basically just finding the minimum in the inner for loop and then swapping it with the first element here. But here. And this is it for selection, so it see you in the next video.
19. Bubble Sort: The third sorting algorithm we are going to talk about is bubblesort. Bubblesort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in groundwater. So consider this list of five elements. First of all, we compare the first two elements and swap them since five is greater than one. And then we do the same thing for number 235 is greater than four, then we should swap. So this is the nest now. And the same thing for element number. 345 is greater than two, she should swap. And lastly we have 58. And since they are in the correct order, eight is greater than five, then we don't swap. Now, we can see that this list is not sorted yet, since we have 1424 is greater than two. So what you should do is repeat the same steps over and over again until we reach the sorted list. The worst-case scenario, if we have the here an element, for example, that say 0. So this 0 should be swapped 12345 times. We have six elements in this list. And the worst case scenario is to swap this 05 times. So if we have a list of n elements, we should swap n minus one times. So we can perform this operation n minus one times, and eventually you will get this sorted list. So let's go ahead and write this code to create another method. Or it bubble with a parameter name ID array as usual and would work here. So first of all, we have a for loop. As we said, from 0 to n minus one, we can say array.length. And inside this for loop we have another for loop to swap every two elements. If the wrong code for we compare every two adjacent elements, a of j is a of j is greater than a of j plus one. Then we'll just swap them. Let's create an integer tamp. Now here, RAM spring, and the same thing here. And if we consider that temp equal to array dot a j and a j, whatever there is at j plus one. And then if j plus1, the value salt, and this is our method and I'm sorry, we will have n minus one and n minus one. Let's use this bubble and use it here, and print the last one more time. And we'll get 325110. This is before eating and after salting 123510. Now, our code can be improved by doing a simple task. So for example, here, we swapped out the elements here. First time. And then the second time, we only needed to swap 42. And this list is sorted now. But in our example, we're obliged to pass through all the list and minus1 times. So one thing we can improve is f. And we got to a point where our inner for loop do not perform any task, then we can equate because we have no elements to swap. So we can do this task using a Boolean. So let's name it swat. First of all, it is, should be and not give it the value here will give it the value inside our outer for loop. Swap two will be first the equal to false in this case. And if, if we only threw up at least one time, then after going out from this inner loop will check swap. If swapped equal to false. Then we did not perform any swapping here. So we can exit the for loop since our list is sorted now. So we can break. Otherwise will continuous swapping. And we run the code, we get the same result as before. But now it is much simpler and it will not take as much time as before. So this is it for bubblesort, the simplest sorting algorithm between all of them. And see you in the next video.
20. Merge Sort: Moving on to another sorting algorithm, merge sort. Merge sort is a divide and conquer algorithm. So let me go ahead and create a new class. Subclass, created insertion name it merged. And he will discuss merge sort. First of all, let's consider a small list of four elements and then discuss a bigger list. For, for example, let's consider a list with four elements, 2431. So at, we're going to do is to divide this list into two list. The first one we'll have 24, will contain two elements, and the second one will have the last two elements, 31. Then we will sort each list alone. So 24 are already sorted, so we don't need to do anything, just type them. And here we have 31, we need to swap them. So this is our second sorted lists. And then after that we need to merge them. Since they are sorted. So the first element should be the smallest. So we'll compare the first element in the two lists. Here we have 21. So one is exploited and would write one. And then we'll compare two with 32 is smaller than two, and then three with four. Same thing, pride v and then still have the last element in the first list, since four. And then we're done. Now, let's use a bigger list. We have in this list seven elements. We divide this lesson to toilets. And the first list will be four elements and the second three elements. Then we do the same thing with this list divided two to 22, the same thing with the other one too. And we still have only one element, so we'll divide it to one and we'll do the same thing. And this list, we have two elements, would divide it to one element and every list. And then we'll have 1234567 list. Each list contains only one element. After that, we need to merge them. We start with the two elements here. We have twenty seven and thirty eight. Twenty seven is smaller than you'd write 2738. Same thing here, 343982. And then after that, we need to merge the two lists here, as we did in the previous example. So first of all, we have three, then we have twenty seven, thirty eight, forty three. The same thing here. And we finally have our finite list final salted. The idea of merge sort is quite simple. It requires to call the method would more than 1s, two until we reach. List of one element, then recreating sorted lists as shown here. Let's go ahead and write it now. So to complete the Merge Sort, need to write two methods. The first method could be thought, the main function that sorts the array using another method. So let's write it. Public void. Let's name it public static, void. And it will accept an integer and no index and high index. They represent where should we start? And then if low is less than the hard, then we can continue. Otherwise, we don't need to do anything. It means that low is greater or equal to high. In this case, we only have one element in the list and we don't need to cite it. So we're working on if low is less than high. So what we should do here is to the middle index equal to low divided by two. And then what we'll do is to sort and divide the list into two lists. And then, so the left part alone and then so the Right but so can do that will enter our At a, we have with low and then sort the right but at a middle plus one. And after that, we need to merge the sorted halves. So we'll call a method limit merge. And it will take as a parameters left, low and high. And let's go ahead and create our merge method. So we have here can make it private, private, static, void, merged and as usual method. And now we need to find the sizes of the two subarrays and to be merged. So the first type is limit n one equal to minus one. And the second one is N2 equal to hi minus. Now we have the two sizes. New lists. So we name it list one. Or we can emit left and right. So we have left the size and right. This second size. After that, you need to copy the data from this original array to our two arrays. Now, we do that. We simply use a for loop with the boundary of un1 and copy all the data from right to left. So left i equal to i. And another for loop to copy the data of the right part of the array to our list called right. In this case, we'll start with an array of middle plus one and plus j. And now we copied the data here. Plus, I am sorry. And this is how we copy our data. Now, we need to merge them together. So what you should do is to create a while loop to copy all the data we stored and left and right copied back to our original update. So as we said in this example, after going to this phase, we need to store them back in the original list. So here we'll compare the two elements and then we'll start them and the original array and the same thing here. We compare these elements together and we'll get our sorted list. So let's go back to our code and write a while loop. And the condition of this while loop that we still have elements in both left and right. So here let's create integers i equal to 0, and the same thing for J, 0. And let's create an integer and name to name it, which is equal to o. Now, while i is less than n, one, which is the size of left and J is less than. And two will be working on the slope. Now first of all, we'll compare left with right of j, of i is less than j, then we store it. This component and the original list. So a will be equal to left. And then we increment i. Since we're done with this, for example, let's go back here. What we have done in this case is we compared left of i here, 27 with three. F, 27 is less than three. We should store it here. Now, in this case, 27 is greater than three, then we should store three in this case. So otherwise, we should store it. And at any k derived component and increment j by one. And in both cases, we should implement k Since it will be filled either way. Now, after finishing this while loop, we might have some elements left in any list. So to fill in the original one, we should complete whatever there is left in our two lists. That would create a while loop. While i is less than N1. The N1 if i is equal to N1. And we broke out of this while loop because of i equal to one, then this while loop will not work since it would be already equal line one. So if this is the case, we should only buy whatever there is in the left part and increment, increment k. And the same thing with n2 if j is less than and to do the same exact thing, to write increment j and k. So now we're done with our merge function. And let's go ahead and use it. And I will main method. So lets go back. But before let's check our boundaries. Here we have left and right. And here we should start with a node. Since we are not sat with zeros, sat with whatever our index here is. And now let's go back and documented here. Our main method. This creates a delay equal to, in this case, four to 718 and use it now, use the sort with a 0 length minus one. And then use a for loop to print out our elements. And discord 12478. So this is it for merge. So it See you next video.
21. Quick Sort: Like merge sort, quicksort is a divide and conquer algorithm. It takes an element as Pivot and partitions the array around the pivot. There are many different versions of quicksort that big pivot and different ways. We can pick the pivot as the first element. First element, random element, or the media. I'd explained what pivot is in a moment. First, let's write a list. So consider we have a list contains 101819. And so this is our list. Now we choose element as a pivot. So let's go ahead and choose, for example, the last element and separate them to understand it. And it's going to have to the same thing here. So here we have this list and this is our pivot. So right down here. And here we have the first element. Now we need two arrows, 2.2 to two positions at this list. The first, we start with the first element from the left and the last element before the pivot. So here we have our first, lets say this is the first element and this is the last. Now, what will do is to compare the first element if it is greater than the pivot, than we need to swap it, we need to end up with a budget that is lower than the pivot and the other part should be greater than the pivot. So to do that, first, ten is greater than the pivot. Now, then will move, will move to 80. Here we have 80. So now we're at 8050. So 80 is ready to be swapped. Now we'll look at 5050. Is 50 greater than the pivot? No, then we can swap it. So now we swap 50 with 80. Here will have 80, and here we have 15. Now we change the positions of these arrows. We have this arrow at 42nd 30. Now, the same thing will do the same thing here. We have 13, is 30 lower than the pivot? Yes. Then we don't need to swap. It will go to another go to 90. And now we'll compare 90 with 40. 90 greater than the pivot? Yes. Then we need to swap it. Is 40 lower than the pivot? Yes. Then we need to swap these two elements, will have 90 here. And the, now the two arrows, let's name them to be able to see what will happen. We have low and high. Now before swapping, these were the possessions, low and high. Low at position 0123 and high position for. Now, after swapping the two elements, we need to increment by one and decrement high by one. So I will be at position, at this position and low will be at this position. And whenever low is equal or higher than high, we can know that we're done here. Since lobe has passed high. Now, the last thing we should do is to swap this element with the pivot. So you will have 17 And at the pivot 90. Now we can see that all the elements smaller than 70 and all the elements here are great and 70. So this is the idea of the QuickSort. We can perform this same exact algorithm to this list. We can choose 40 as the pivot and work accordingly. And the same thing goes here. And we let recursion do the work for us. This is the general idea and we'll use the recursion to be able to implement it more than once has emerged. So we have two methods here. First method will be private, integer. Let's rename it partition. It will take the parameters and emit. And low than this method, where we take the last element as the pivot. The pivot element at its correct position in the sorted array. And cases all smaller, smaller elements than the pivot to the left and greater to the right. So let's go ahead and start with this method. First of all, we have our pivot is created. Now the vector is equal to the last element in this list. And we have the index of smaller element. It is a sname i, which is equal to minus1. And this case, we start with our for loop. We start by low. All the way to. Now, we need to check if the current element is smaller than the pivot. So if j is less in this case, and we need to increment i. One, swap and array j. So let's swap it. And to a. Then equal to, sorry, a equals i, equal to j. And finally, back to G. So now we swapped the two elements. After finishing with this word loop, we need to swap the pivot with at a i plus one. So in this case, create another time and swap the two elements. As we said. Here, we have the pivot is at location a. And then giving the tan two. Now we swapped the two metadata to elements and then we will simply return plus one. So this is our method, the partition method. This method took the last element as Pivot, place the pivot element at its correct position in the sorted at a, and places all smaller to the left and greater to derived. Now, the other method is the main function that implements that quicksort. And let's name it public static, void. So that it would take three parameters as usual, and low and high. First of all, we'll check if flow is not greater than high. We can work otherwise will not work because it will not make sense. And we'll have, we'll create an integer, let us name it by, by is that partitioning and depth. That will, where we'll use this method we created here. So pi would use partition at the low. Now, after getting the index by, now, we should sort the two, abase the left part, Right? But so we'll use the same method one more time with no other way to Pi minus one. And the same thing by plus one other way to write. And then we're done with this method. You can use it. And our main method. So we create an array, for example, steam it, and with some values 426173. And we'll call the sort method 0 and updated length minus1. Then create a for loop and print out the elements of this list. So as usual, with some space here, and let's go ahead and run. The code will get 1234567. So this is the array is sorted array after performing this QuickSort. So this is it for Quicksort. See you in the next video.
22. Linear and Binary Search: Sometimes we want to check, put an element from the list. And here we can use searching algorithms. We have several sessions algorithms and we'll start with linear search. So let's go ahead and create a class name. And then the main method, let's create our array. So this is our array. And let's suppose you want to search for the number to an integer, number equal to two. Now, this linear search is suppose to go through all the list and check if the element in this list is equal to two. Return the position. Otherwise, if no elements matches this number, we should return minus one. So let's go ahead and create our method. And it will take that list and an integer number. So what we're going to do is to compare this number with every element in this list. So use a for loop to go through all the animals in the list. And number two position. Then we should return this specific position. Otherwise. So the method does not work. We should return an integer. And otherwise, if we best through all the list and we didn't return any integer, then we didn't find the number is specified number minus one. And if we use the t at n number and print it out, we'll get then decks of the number two. Now here, 22. Let's change the number, for example, two to six. So here we found the number six at index three in this list. And the same thing if we change it, for example, to nine and print it out, we'll get four and x four. Now, we tried another number that is not in the list, we get minus one. So this is how search works. It's very simple, but it takes. Much time. We'll talk about time complexity later on for every algorithm. Now, let's move on to another searching algorithm is the binary search. Here, we should have a sorted array or list, and you'll know why in a moment. So the idea of binary search is to search a sorted array by repeatedly dividing the search interval in half to begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrowed the interval to the lower half, otherwise, narrow it. The upper half. Repeatedly check until the value is found of the interval or the interval is empty. So let's look at an example. Here we have this list. First of all, we take the middle element. Here. In this case it's 16. And now we want to search for 23. And our array is sorted, as we said. So we check if 23 is greater than 16, then we take this half. Otherwise, who should take this half? Now, since it's greater than 16, then we'll ignore all the elements here because we're absolutely sure that 23 is created then all of them, since they are sorted. And we need to check now for this part. And we take the middle of this part and do the same here. F2 and F3 is greater than 56. No, it's not. Then we need to take the left. But, and he began use the middle as 23. And we found 23 to return the index five, in this case. For now. And our method. Let's create a new method, binary search. And it will take an array as usual. And the low index X. So X is the element to session four in this list. And now we need to find the middle and depth. And to do that, let's go back and see in this example, here we have low and high to what we did is two, subtract nine minus 0 over to 4.5 because its integer, it will take four. And the same thing here, who took 59 minus 54 over two, which is two plus the low index plus five equal to seven, fundamentalist seven. And the same thing we did here. And let's go back and set the condition that if high is less than the load, then less than or equal to the node than we've done. Otherwise, we should work. So here is greater than the load will work. Otherwise, when we turn, we shouldn't return minus1. Now, let's find our middle, as we said, is equal to low plus high minus low of a two. So this is our metal. If metal element is equal to our x is equal to two assertion. And then we'll just return. Otherwise, we should check, as we said, let's go back here. In this case we have 2323 is greater than 16. Then we'll work with this. But we'll do the same exact stamps and this part, otherwise, we should do it steps on this bug. So to do that, we simply compare at a to x. F at a is greater than x, we should return BinarySearch. This is the same, but low, and we need to change how to middle minus1 goes. We're absolutely sure that old middle and all the rest of the elements on the right side greater than S, then the not x otherwise would return. And binary search to search the left side. So we start with the right side, I'm sorry, the metal plus one all the way to high and the same number x. So this is it. Let's go back and implemented here. And our main method, we're going to print out binary search at a 0 and minus one and the number of searching for numbers. Let's go ahead and run the code. We'll get minus 12, for example, six. And we'll get. So sex is at position three. And this is a binary search. Binary search is much faster than linear search. Since every time we are going through the list, we're cutting it in half. However, in linear search, we are obliged to go through all the elements in the list. We still have some searching algorithms and we'll talk about them in the next videos.
23. Jump Search: Like binary search, jumps is a searching algorithm for sorting arrays. The basic idea is to check fewer elements than the linear search by jumping ahead by fixed tabs or skipping some elements instead of searching all the elements in the list. So for example, consider we have this list. We have 16 elements here. Let's suppose that we're searching for number 55. So the jump search will find the value of 50 using some steps. First, let's consider that the block size to be jumped as for since 16, square root of 164. So first of all, it will jump from index 0 to index four. So it will jump to 01234. Jump to this element compared to 5535 is still greater than three. Then we'll jump one more time to any one. Same thing here, 21 is less than 55, then we need to jump, will jump to 144. And then we can see that 144 is greater than 55. So we'll go back to 21 and perform a linear search from 21244 until we find our element to number 55. We usually use the square root of length as the block size to be jumped. Because in the worst case scenario, this is the best step size to take. So let's start with our code. Jump to the main ij's of integer and x that we are going to search in this list. And here, first of all, we need to store the length of the day. We need to choose our stack. And as we said, we'll take the square root of n using the mass. And this mass square root, for example, suppose we have 17 elements, give US 14 certain numbers. So after taking the square root of and we formatted using Math.floor. And then since we're storing it in an integer to converges to ENT. And if the element exists, then we need to find a block where the element is present. So let's go back to our example. And he 55 is between 2144. So we need to find these two elements. And we already have an integers. We create another entity or let's call it, for example, previous, liquid to 0. So at the beginning, previous is equal to 0, so it is at position 0 and step is at position four. And if the element is not found in this interval, then we should give previous the value of four. So previous is now at position four and we need to add four to the step. So step would be at position eight and continue until we find our element in this interval and our interval. So to do that, we need to create a while loop and set the wild loop as at a is less than x. Now, we might get to a point where if we keep adding four, the step, we might have stepped greater than n, then we cannot access at a half-step. So instead of accessing array of step that says a radar minimum between step and, and. So every time we execute this loop, we need to change previous to the new value. And the same for step create to add. Whatever we have here. So it added. And then we'll get previous is greater than or equal to. And then we're finished. We didn't find the animal who simply return minus1. And he we should change to integer. Now. So what we're saying here in this while loop, let's use it at this example. First of all, we have previous equal to 0 and step equal for possession. For. Now. We go through this while loop. First of all, we'll check array of minimum between step and then step is surely less than n. In this case, step is equal to four. So math at a of four, which is three. In this case, we'll check if three is less than x. Yes, then we'll continue executing this while loop will change the values. Now, previous is equal to four and step is equal to eight. And then we'll check if we pass the boundaries. If previous is greater than or equal to n, Then we passed the boundaries and we done, we didn't find any number that matches acts. So now we're at position four. And position eight. The same thing. We compare this 21 with 5521 is less than 55 and we need to execute the while loop one more time previous is now at position eight. So this is position for this position aid. And step is at position 12. In this case, we have 144. So compare one hundred forty four, fifty five and fifty five years less than a 144, then will exit the loop. Having previous the value of eight and step the value of 12, then we have our interval and 55 is in this interval. Now, after exiting the while loop, we need to perform a linear search for x and y and another while loop. So while we sat with the previous, now since the previous is at position eight and step is at position a hundred and forty four and fifty five, which showed that receiver is indistinct third interval, then we'll start with 21 and continue. So wide carry at previous is less than x, then we'll increment by one. And if we got to a point where previous is equal to either step, equal to 12 over n, So equal to minimum between the two integers, either stamp. And then we need to break or return minus1 can simply return minus one. In this case, since we didn't find our number. And then we check if we found the element. So if array previous is equal to x, then we return this position and return minus one. If we die, we didn't find it. So this is here. We have an adder cannot converge from n Boolean, we have a missing equal. So this is it, this is our function. And let's go ahead and choose it here. So we'll print out chunk and we'll search for 55. So let's take this and put them in our array. So this is our array and it will return ten. So 55 is at position ten. So these first two lines were from the past functions now this hour than our position where 55 is at this list. So this is it for jumps. See you in the next video.
24. Interpolation Search: And other searching algorithm as interpolation search. Interpolation search works better than binary search. Because binary search always check on a middle element basis. But interpretation search may go to different locations according to the value of P to be searched. So for example, if we want to search for the number three and this list, if we use binary search, will go and check in the middle. So either 1321034, so this is the middle of the list. However, if we use interpolation search will go to the value that is closer to our number using a specific formula and we'll talk about it later. So he three is closer to 0 than it is closer to 610. So our formula will lead us to a number between these. So the same idea as binary search, but instead of having a middle element, we will having a position that will change according to our elements. So let's go ahead and create our method public. Let's name it interpolation. And as usually to take an array of elements and the size of the element, as well as the t or let say x. Now, we need to set our low and high and low equal to 0 and will be and minus1. Now we'll enter our while loop. Low is less than or equal to i. Otherwise we don't need to work anymore because we didn't find our element. So it's the same as we did in binary search. And we need to add some conditions. While our element x is less than or equal to, our low is greater than or equal, I'm sorry, and is less than or equal to our element. So as long as these conditions are satisfied, we can work here. Now, whenever we get to a point where our low is equal to our high index, then this means that we have done so either we find the element or not. So we'll check if I add the same since they are equal, is equal to our x. And this is the case return low, otherwise, return minus1. And after checking this condition, now we can work, can create our formula that same position that will jump. As we did in our binary search, we created a position called metal element. Every time we go to the middle element now, we create another integer called position. And the formula is as follows. This is how we compute the interpolation. And a of high minus low. Then we multiply it with I would x minus a of load. And now we check if a ray at this position is equal to our element, then we just return our position. Otherwise, we'll check that a at this position is less than our element. Then we need to change our low from low to high position plus one. The same thing as we did and in binary search, but instead of position, we used method otherwise will be position minus one. So otherwise, if the we have at a position is greater than x, then du would be equal to position minus1. And after finishing this condition and everything, the while loop, we can return minus one if we don't find the integer. And now let's go back and use it here. So I print out interpolation. We have the a and B and x will be the number. So for example, let's suppose for a search for b. And let's go ahead and run. Our code. Will get for SO three is at position 401234. This change this number to 89 and we'll get position 11. So 89 is at position 11. And the last thing we're going to check if we enter a number that's not in this lesson, 900, we get minus one. So this is it for interpolation search. See you in the next video.
25. Exponential Search: The last searching algorithm we're going to talk about is exponential search. Exponential search involves two steps. First, we need to find a range where the element is present. And then we'll do binary search in the strange. So let's consider this list. We have 16 elements and we need to find, for example, 89. So what we're going to do is, first of all, consider if our number is equal to the first element in this list. If this is the case, then we return 0, so it is at position 0. Otherwise, we check all the other elements. We start with i equal to one and with doublet I equal to two, then i equal 24816 and so on. And let's go ahead and implemented to better understand this. Go here and you have public static, and let's name it exponential. As usual, take an array of integers and, and, and the value that we're going to search, we name it x here. First of all, as we said, we need to check if at index 0, if the value is at index 0, then we simply return 0. Otherwise, we need to find the range for the binary search by repeated doubling. So we'll define an integer with the value of one. And we enter the loop. While i is less than n, the length of the array. And add a, i is less than our, less than or equal to our number. This loop will be executed. So we'll simply multiply i by two. So every time we enter this loop, we multiply i by two. So let's see here in this example, when we can exit this loop. For example, if we want to search for the number 13, first of all, we check if 0 is equal to 13. No, it's not. Then we define i equal to one and enter this loop. I is equal to one, will check. While I at a, at i is less than or equal to x, one is less than or equal to 13. Yes, then we multiply i by. So now we have I equal to two, and we'll go to our next element. Here we have also one, it's less than 13 and i is less than n. Then we multiply i by 21 more time. Now we have two times 24201234. Now, here we check the is less than 13. So we can multiply one more time to four times 28. So now we're 5678, we're at 21. Now. We'll check 21 is less than 13. No, it's not. Then. We exit the loop with i equal to eight. Now we have I equal to eight. And to get our interval, we have i equal to eight and i equal to four, which is eight divided by two. So after finding our interval here, we simply use binary search. And I work at a. And here we have i divided by two. This is our interval and minimum between i and one, i and n. Since it might be, it might be that i is greater than n and we cannot work outside our boundaries. And here we have our integer x. And since we need to return the type, so we simply turn binary search. And then we're done. Let's go ahead and use it here. So we'll go ahead and print out exponential at array.length and w. We're going to search, for example, 13. And the code will get seven. So 13 is at position seven. So let's make it better, nicer. And exponential. Let's store it as exponential and an integer. As intimate result is equal to this exponential. If the result is greater than 0, then we print out the element is present at index. And we print out the index. Otherwise, we print out that element is not present. And Ray and clustering the code will get element is at index seven. Now we have a shortcut in Java that you can use. So instead of writing all of these, we can simply print out one of the two lines. So we need to set here the condition if result is less than 0, this is the case. We can print out. Element is not present. And the other statement would be element is present, index. And we print out the index. So let's go ahead and see what would have been here. Let's run the code and we get element is present and index seven. So this shortcut, First of all, NDA System.out.print method. We set the condition your result is less than 0. Then automatically this method will print the first statement. Otherwise, it will print whatever there is after the two points here. So we asked them if there is act is less than 0, yes, print this. Otherwise. Print this. This is very helpful if we don't want to complicate things and we need a very simple form of printing. So this is for searching algorithms. See you in the next video.
26. Extra Problem: Inheritance: Now that we're done with our material, let's go ahead and solve some extra problems. And you start with inheritance. Will create the bank account. So I already created a package called it BankAccount. Inside this package, we'll have our parent class, name it, bank account. And we have two types of accounts. We have a saving account and a checking account. So let's go ahead and create two new classes. The first one we name it checking, and the other will be savings account. And of course we need to create our main method. This is our diver method, and we create our main method. Now, the two classes, bank account and just same thing extends bank account. Now let's go back to our bank account and create some methods here. First of all, we have a variable. It is our balance. So let's referred to it as protected w. And let's create a constructor. And then we'll use our methods. So bank account balance. And say that balance to balance. Now, Jaffa allows us to have the same name here. And in this case, we need to do is to refer to this local variable. We need to use that. And now we referring to this one outside and this balance is the one in the parameter. Now, let's create our method. We have the gut balance public. Www2 get balance will simply return. Another method, for example, to withdraw void with a specific number. We would go specific and simply subtract this amount from dependence. And another method if we want to add a specific amount. So we simply added to the balance. Now let's work on our savings account. So in descending account we have an interest. So first of all, let's create our constructor savings account. And we got the support from our parent class with our balance. And to add the interests, we need to have a rate. So let's create a protected vinyl and naming. And we said the rate at 0.04. Now let's create our method to our interests, public void interest, and will simply use the method to create it in our bank account deposit and to add our interest, which is date times our balance. Now, let's move on to our checking account. And our checking account. First of all, let's create our constructor and then talk about the methods. So in our constructed as you live, public checking, account balance. And we'll call the super and penance. Now, every time we withdraw or add an amount to our account, we have a feed that we need to pay. So let's create some integers, some variables outside. To. The first is just to keep count of how many times we used our account either to withdraw, to out at to add a specific amount. So protected and section count. The other one is first of all, we have to free times began withdraw or add an amount for free for two times. So the first two times, we withdraw at its full free. So let's create our finite integer and name it 32. And the last one will be turbulent. And this is the field that you need to pay after passing the 23 times. So let's name it v equal to 0.25. Now, we need to set I will transaction count at 0 equal to 0. So you use go and deposit method. We need to override them. So here we have our deposit and withdraw. So they already called the super dot width row. We don't need to do these steps here. We just need to keep track of our transaction count. So every time we enter this method, we just increment transaction count by one. And the same thing here. Now, these are our method and the last method we're going to create is the method to deduct the fees. So let's name it is. And this method will simply check if transaction count is greater than two. Then we need to add some fees. Otherwise, we just reset the counter. We set the transaction fee, that transaction count to 0. Transaction downtown is greater than antigen outside, we name it three is greater than three. Then we should get the w. Let's name it. Fee. And it would be equal to transaction 23 times. And multiplied by v. We named it outside. So let's suppose here we have FDI. Now, after getting this variable will just withdraw it from L. So these are our method. Now let's create two string method for our bank account class. Here. We have public String toString and we'll simply print with turn balance. Our balance is our balance. In our checking account. We'll call, we'll call super. So let's create a string and call it result, which will store our strength. And then a line and print out our counts. So here we can add our transaction count and just return result now and our saving account. Let's override the toString method. So we'd have to override it. And the string would be equal to super dot toString. And Add to this result, align and return the result. And then we'll go to our main method and create a checking account and savings account. Checking account, let's name it, see it. Violence could be 1000. And saving account S equal to new savings to banish would be 10 thousand. Let's use some of the methods. So c dot with Joe would go 150. And then this word without saving account as dot with TO 2003. After that. Let's use as. Then go ahead and print out checking account with our C. And let's print out the line. Then saving account. And we print out s with a line. And then we'll use our method and see, see, deduct and print it out one more time. And let's go ahead and conduct a checking account balance, saving account balance with count rate. And you can see that the balance here is the same since even though we use data, but count is equal to two. So let's use and the method one more time. For example C, deposit any amounts, for example 20. And we'll see that even though we deposit and we added 20, our Vanessa's now a 169.735, we deducted 0.250 p. So this is it for this example to you in the next one.
27. Fibonacci Sequence: Now we're going to talk about Fibonacci sequence and to solve it using three methods. First of all, the Fibonacci sequence is the series of numbers in which the next number is found by adding the two numbers before it. So let me go ahead and write it here. The first two numbers are 01, then we add 0 plus 111 plus 121232 plus 35, and so on, 8132134 and so on. So this is the idea of this sequence. Now, let's go ahead and solve it recursively, iteratively and using the Big Integer class. We'll talk about the Big Integer class later. So first of all, let's solve it iteratively. So let's create a method, private static that's predetermined along, for example. And let's name it, felt IT. That will take an integer and the position. And what we should return is the number at the specified position. So for example, if we entered five, we should return 01235, we should return three. If we enter seven, we should return eight, and so on. Now, as we said, first of all, let's create an integer and give it a value. And the value at 100. And we need to add the previous element is equal to 0 at first, h equal to one, and the previous previous, previous, previous xi is equal to 0. Now, we create a for loop with, we start with i equal to two and less than or equal to n. And now, every time we enter this loop, we add to the solution previous, previous, previous. Now we need to change our two values here. So previous previous will take the value of previous, previous, previous, previous. Previous will have with the value of the solution. Now, we just return this number after the for loop. So let's go ahead and create our main method. Here. We have our main method and use this. So we print out Fibonacci iteratively duration. And we'll just print out the ICTY with the value. And let's ask the user to enter the value. So scanner scan, scan. Please enter a number, and we'll store that number next n. And we'll give it as a parameter here. Now, if we go ahead and run this code, will get, please enter a number. Suppose we enter five, get the Fibonacci iteration 568, and so on. And for example, we get 55. Now, let's use recursion. So let's go ahead and create another method, method, private Karen to give it a value. And as we said, we need to create our base case. Base case if n is equal to either one or 0, we should end. Otherwise, we should return Fibonacci recursion of n minus one plus Fibonacci recursion of N minus two. So the last two elements. And let's go ahead and run this code. Use it in our main method. So we print out the Nazi. Because plus. And run this code. We get a number, for example, sex, Fibonacci iteration aid, and the same result as we use the recursion method. Now, the last method will use as big integer. So we'll use Big Integer class. So this class is generally used for mathematical operation which involves very big integer calculations that are outside the limit of all available primitive data types. For example, factorial of a 100 contains a 158 digits. So we can store it in any primitive data type available. We can store it and this big integer and use the methods and discrete integer plus. So now let's create our method using MC integer will be a private static with the value of quick integer. Usually we return belonged or integer or string, now returning Big Integer and just name. And the value of n. As usual. Now, the same, I would do the same as we did in our iteration method. So. First of all, we need to store the solution. The value of big integer, let's name it. Solution equal to big integer dot 0. So this is how we store 0. And the solution. We don't say Big Integer solution, solution equal to 0. We say big integers. Now, the same thing for previous, previous, previous. So big integer, previous equal to big integer. But one and Big Integer previous, previous, big integer, 0. Now we start with our for loop and we start with two and end with n equal to n. And solution will be previous, previous, previous, previous, previous, previous. And then previous previous now would be equal to our previous and previous solution. And then we will simply return solution. So this is it. And now let's print out System.out.print integer parameter number. Let's run the code. And we'll get 556, we get eight. Now for example, if we use a large number such as 10 thousand, we can see that because it will take some time. And if we use a 100 thousand concede that it generates an error. However, if we only use this Big Integer class, and let's enter this number. You can see that 20 dead this sequence. And it is a very large, Not really, not be able to store it in any primitive datatype. So this is why we use the Big Integer class. Now, this is it for Fibonacci Sequence. We used three methods and we learned a new class about a new class, the Big Integer class.
28. Big Integer Class: Now let's talk about Big Integer class. We already talked about it and Fibonacci, but he will explode it more. So this class is available for us in Java to math class. And first of all, let's create our big integer, captured this favorite Big Integer one equal to one. So now we are giving this object a value of 1. First of all, let's compute the factorial of code for example. So let's name it. And we create our for loop two, the start from 12 all the way to. And every time we pass through this for loop, we multiply two big integer. We have a method, big integer dot multiply and multiply it by big integer value of i. And then let's go ahead and print out the area of plus big integer. Run the code. You get factorial of 24. Now let's use other methods. We have. For example, let's create another object, Big Integer, big integer, two. New big integer with the value of a 197. Now, let's use it confirmed method and get the minimum between the two objects. So let's print out I think the big T2. And now we get the minimum between the two values. We get 24. And if we use the Macs big integer, integer to get a 197. Now, for example, if we want to get the next prime number greater than 197. So we may use this method. So let's print out the next prime number. Next to a 197 is, and use big Institute to next probably prime. And we get the next prime and it is a 199. Now, we still have lots of methods and we use some of them. For example, we have the ad. So if we say big integers, the integer two, and let's start it in big integer name. Call it edition equal to this, and then print out edition will get to a 121. So the rest method we're going to use the toString. So this method will return the decimal string representation of the big integer. So we can store it in a string. Let's call it equal to integer, one to string. And so we already have n here, so we need to choose a number cruncher name, template name. Now, if we print out name, will get 24 and name dot charAt 0, for example, will get too. So we converted this big integer to a string and now we can manipulate its characters. So this is it for Big Integer class. We don't use it that much when dealing with small integers. And we still have lots of methods. They are so useful and we can use them in our code. So you can explore them on your own. And now see you in the next video.
29. Extra problems: Recursion: Now let's go ahead and solve some problems using recursion. So the first problem we're going to solve is to change old x's and a string, too wise to consider. We have an example code X. Then we need to change it to owed by the same thing. For example, x x, x x. We need to change it to y, y i by light. And wouldn't do it that without using loops. So let's create our method, public static. And it should they turn staying this name, change x, y, and it will take a stand. That's now we need to pass through the animals, the characters in the string. And first of all, we need to check if this thing, our base case is if the string is of length 0, then we're done. We don't have any character. So we check SDR that length. If SDR that time equals 0, then we simply return an empty string. Otherwise, we need to work. Now, the first thing we need to do is to check if the first character in our string is x. If this is the case. If SDR is at z is equal to x, then we need to do something. And we need to return X and converted to y. So we should return y plus. Now, after finishing without first character, we need to do the same thing for the rest of the characters. Now, in this example, let's say, let's say we have x, x, x x. So what we should do here is to compare this to x. If this is the case, then we need to convert it to i. Now we have Y and something. Now, after finishing with the first character, we need to do the same thing with the rest of the characters. So we need to enter this method one more time and check if this character is X. Now we need to convert it to, so we'll let the recursion to do it. We simply call it the method itself with a new string, which is substring from one till the end of the string. Now, when we get to the point where we have only one element in the string, then this will generate an error. Because when the string has only one element, one character, and we're saying that we need all the elements after the first character. So to deal with that, we need to set the condition STR, that length is equal to one. Then we should simply return. Why? Otherwise, we should return y plus quota method one more time. Now, this is for standard chart at 0 equal to x. Otherwise, we need to do another task. So if SDR dot length equal to one, we simply return STR at 0. Otherwise, we return stdio.h I that quote the method one more time. And yeah, that substring, substring from one end of the string. And now we need to convert it to a string. So we simply add string here. And now we're done with this method. Let's go ahead and use it in our main method. This is our main method. And let's ask the user to provide us with the string, please and stored it. A string called name. Then use this method and print out the result. So change x, y with our name. Let's run the code this into a string. For example, x x x x, y, y, y, y. And if we don't have any x, here, for example, we get high. Now let's move on to another simple example. The precomputed, the power of n. For example, if we have 32, then this is, as we are saying, that we need, that we want t to the power of two over three to the power of 45 and so on. So it is very straightforward. Let's create our method. And it will return a teacher to take two integers, and, and, and. And. And I would base case, if n is equal to and 0, then simply return one. Otherwise, we should return our base times our base with an minus1, since we multiply base. And let's go ahead and use it here. Let's, for example, consider n equal to five and n equal to three. And print out with base. And then let's run the code. And we'll get, you get a 125. Now, let's move on to another example. And this example, we'll use integers or an array of integers. So suppose we have this list, one to 20. So here we have two and then followed by 20, which is two times ten. And let's take another example, 14315 and eat the same thing. We have three multiplied by ten, we get. So three is followed by 13. Now, our code should return true if we have two elements and if we multiply the first by ten, then we get the second. So here we return true here. And for example, 12345 should return. Let's go ahead and write our code. Public static should return a Boolean. And let's name it. For example, multiple. And it will take a value. Integers has a limit at a and the number. And this number is the index that we're going to use the pass through our array. And now let's start. So first of all, if then dx is equal to the array.length minus1, then we passed all the array and we didn't find any two elements that matches our condition. And in this case, we should return false. So this is our base case. Otherwise, we should work. Now, if index is less than a day, length minus one, then we can work. In this case, we'll check that if array at index timestamp is equal to array at index plus one, then we should, we should return true. Otherwise, we need to call the same method again with and increment the index. So multiple had a and index plus one. Now, this is not the case, then we just simply return. So let's see what we did here in this case. First of all, we get, for example, let's use this array. And at first it will be 0. So n dx is not equal to that length minus one. So we enter this block and here we'll check if index is less than array.length one is one. This is the case. Then we should check if array index times ten. So if one times ten equal to ten is equal to four, no, then we should call the method one more time. And now our index is incremented by one. So here our index would be four and then which also is four times ten equal to three. Now, than our index will be at position, at this position. And we do the same thing. Three times ten is equal to 30. Now our condition is satisfied. Then we don't need to do this method again. So we'll just return true. Now in this case, for example, if we use this list, then we not find any, then any element that matches our condition here. So we'll just continue to enter the same method until index will be, eventually will be at array.length minus1 and we'll return false. So this is our method and let's go ahead and use it in our main method. So let me just comment these. And let's print multiple and create an equal to, for example, 12355310. And in this case, that is used this method with this at a and 0. Let's see what will happen. Will get true. Now if we delete 15 will get flows. So this is it. Some simple examples on recursion. See you in the next video.
30. Sorting Array of Strings: Now we go back to our sorting algorithms. The oddity tried them with arrays of integers. Now, we will use arrays of strings. So here, a main method. Let's create an array of strings. Scale it names, and it would be equal to some names. For example, Alix and press. So this is I would list. Now let's go ahead and use the insertion. So let's name it public static, void, insertion of arrays, arrays of strings, called them names. So it is the same as we did for integers with some variation. So we start with our for loop at i equal to one. And we need to define our strength is equal to names at i and j would be equal to i minus one. Now will enter our while loop. While j is greater or equal to 0. And we'll use a method available for us. And it's String class in Java. This decomposed to, we'll compare the key to another string. In this case, it was named at j. If it is less than 0, then we need to swap them. We need to create a string termed as usual, give it the value of names, names of j plus one, and names of j plus one. We take the value of damping. Now. So this is our method and let's go ahead and use it in our main method. And search and with names. And then the for loop to print our elements. We print aimed plus space. We'll get Alex, Chris, and James so they're sorted now. So we used, compared to this method is available in the String class. And we use that. We have the same method here. But instead of comparing with this sign, we used the compare method in the String class and Java. Now let's use selection sort. So let's go ahead and copy it without writing it one more time. Selection sort, and we'll modify it here. So let's go ahead and modify it. Now. You take a strength. And here we set minimum is equal to I will. Okay? And if we need to use the compareTo method, the two strings. And then finally, we have a string array that compared to gay and minimum, it should be less than 0. And then we're done. Let's go back here and use it. So instead of using insertion, let's print insertion sort. And could perform selection are names and print them out. Now we already sorted names, so let's create another at a. Let's call it name. Two will be equal to names and use it here. Selection so that here. Let's go ahead and print them out. We'll get, we just need to print a line here. And the code one more time to get insertion. So it, this is our output and selection, so it would get the same output. So this is, this, this video is just to show you that you can use these sorting algorithms not only for integers, but for strength. And you can use them for characters as well. So you can go ahead and tighten out using characters instead of strings or integers. And not only the sorting technique, but you can also use the searching algorithms with strings and characters to this is it for sorting and searching algorithms? See you in the next video.
31. Project: So our project is to create an account for either student or instructor. This is our main method and let you see it and you need to create the account class student and instructor as children of this parent class account. Now, let's go ahead and see what this class do. So if we go ahead and run the code and we get student or instructor. So of course we are students. And to ask us to enter our first and last name as the major computer. And G. And I should enter my courses. For example, say I'm taking CoA to one, English 101 and physics. To go to. Now, my account is created, had unions student, my ID is one major computer engineering courses. And to ask us to try again. Try again. Type yes. Let's suppose we are instructed Now. First and last name. So Alex, the department, let's see. So the courses I'm teaching, let's say two. And so this account is also created Alexei instructor, department finance courses teaching these and without an idea because the instructor doesn't have 90. Now, if I press enter by mistake, I'll get invalid input. If I want to try again, for example, try again. Lowercases. Suppose a student first and last. For example, a major. Suppose electrical engineering and courses to a one ELE D03. And this account is also created and the idea is now to, since we are to students now, deontology. And lastly, if for example we type by mistake, will get invalid input to try again one more time. So if we don't want to try again, simply type no. And this is the end of the program. Now, your student and instructor. First of all, we started with student. We have a class and we have some methods here. First of all, you need to create a constructor using an object Student. And then we need to set the major and set courses and instructor class. We have the constructor to take just two parameters. Here, we have three parameters, we have the ID and we have two methods, set courses and set department. And we also have else if this is an invalid input and while we enter something different than yes or no, we keep asking the program and we keep asking the user to try again. So this is it for the project. And I hope you enjoy it and see you in the next video.
32. Recap : So this is the end of the class. First of all, we talked about inheritance and polymorphism. Then we moved on to recursion and some, solved some problems in this topic. Then we talked about sorting and searching algorithms. And of course, at the end we solved some problems on every topic. And we have our project. So this is it for this class. The next class, we'll talk about XML and JSON parsing. We learned how to parse JSON and XML using Java. And then we talk about stacks and queues and use them in our St. Louis and doubly-linked list. And finally, we'll talk about collections class and how to use, do use it in Java. I hope this class was beneficial. And see you in the next one.