Sorting Algorithms and Efficiency

Sorting is the process of putting the elements in an array or a list in order using an algorithm. A sorting algorithm may be more efficient than the other depending on its performance. This is very useful when encountering different real life problems. For example, if we want to calculate the median of a list of numbers, the list will have to be sorted and the median will be found in the middle of it. If we want to solve this problem faster, we will have to choose between many sorting algorithms (which behave differently depending on their input).

In computer science we use the Big-Oh notation to represent the efficiency of an algorithm over a  large input of size n. This notation analyzes the performance of the algorithms as n changes. Depending on the function, it can be constant, logarithmic, linear, quadratic, exponential or a combination of any of these. The time it takes will depend on the efficiency of the algorithm. Some commonly seen functions and their relative performances are:

O(1) <= O(lgn) <= O(n) <= O(n^2) <= O(n^3) <= O(2^n) <= O(n^n)

There are several sorting algorithms that are O(nlogn) like quicksort, merge sort, timsort, etc and the worst ones, which are approximately O(n^2) are insertion sort, selection sort and bubble sort.

Two of these algorithms are described below:

– Quicksort:

Here, if the length of the list is greater than 1, the first element of the list is taken as the pivot. Using this pivot, the function breaks the list into two lists. The first list contains the elements that are less than the pivot (let’s call this list “less_than_pivot”) and the other list contains the elements that are greater than the pivot (called “more_than_pivot”). After that, recursion is used in those two lists. Smaller lists will be broken in two and so on until their lengths reach 0 (this approach of breaking down the problem into two recursively is also called divide and conquer). Finally, less_than_pivot, the pivot itself and more_than_pivot will be merged and  this final sorted list is returned.

The problem with this approach is that in Python, there is a recursion limit. So, if a really long list is used (e.g.: a list with 5000000 elements), this function will not work as the recursion limit is exceeded.

To prevent this, an iterative approach (using a while loop) can be used. This is called memoization. Memoization, apart of avoiding the recursion limit problem, optimizes the function because it avoids repeating calculations done previously. 

The worst case of this sorting algorithm is when the list is already sorted. In this case, its efficiency is of O(n^2). On the other hand, for the rest of the cases, its efficiency is of O(nlogn) as the main list and each sub list are divided in two and the pivots are compared with every element in them.

– Merge Sort:

Unlike quicksort, merge sort splits the input in half continuously until each sublist’s size is 1. Then, the sublists have to be merged (comparing the elements and creating ordered merged lists)  until there is only 1 sublist remaining. This remaining list will be the sorted list and is the one that will be returned by the function. This algorithm’s performance is O(nlogn) in all of the cases because in every case, the input will have to be split into two. The sorting and merging process is done after splitting the list.

Here you can see a visualization of 15 different sorting algorithms:

 

 

 

Recursion

Let’s say that we have a poll which gathered the amount of students within different ethnic groups in a certain university. We would have a number for each type of ethnic group. If we wanted to know the nationalities of these and their native language,  we would have even smaller subgroups within each ethnic group and even smaller subgroups within the nationality groups. Let’s assume that there is no overlap within each subgroup. So, if we wanted to know the total amount of students in that university, we would have to sum each element in each subgroup. Let’s take the following as an example:

There are 3 ethnic groups:
– The first group has 3 Peruvian students, 4 Colombian students and 3 Brazilian students.
– The second group has 37 Canadian students and 17 students from the US.
– The third group has 30 Chinese students.
– 1 Peruvian student’s native language is Quechua, the other Peruvian and Colombian students’ is Spanish; and the Brazilian students’ is Brazilian Portuguese.
– Both Canadian and US students’ native language is English.
– Half of the Chinese students’ native language is Mandarin Chinese and the other half’s is Cantonese.

The nested list representation of the total number of students in that university would be:

students = [ [ [1, 2], [4], [3] ], [ [37], [17] ],[ [15, 15] ] ]

The definition for solving this problem would be:

To calculate the total number of students, we can’t just use the built-in function ‘sum’ because every item within the list is another list. We would need to use recursion. So, before solving the problem, we’ll define recursion as the method of calling a function itself within its definition. In other words, what recursion does is dividing the main problem (the function and its input) into smaller sub problems in order to solve the bigger one. In the case of the number of students, a for loop can be used to check each element in the big list. Then, what recursion does is look if each element is a list or a number. If it is a list, then it will call itself again until it finds a number.  The base case is the simplest sub problem that the function reaches. In this specific example, the base case would be when the function finds a number. The function will stop calling itself once it reaches the base case and will go onto the next element of the list. Here, the function will return the sum of all the numbers found after all elements in the big list are examined. In any recursive function, if there is no base case, then the function will keep calling itself infinitely and nobody wants that. Then, when having a problem that can be divided into sub problems of the same type, recursion can be used to solve it efficiently. Of course, you will encounter more difficult problems, but the basic idea of recursion is this one.

 

Week 5

This week , we continued working on recursion exercises (I’ll talk more about this in 2 weeks) and we began working on our assignments. This first assignment consists of making a program which plays a slightly different version of the Towers of Hanoi. The difference is that this game uses four stools. The first half of the assignment was pretty straightforward, but, when we reached the part in which we had to use recursion, me and my partner almost lost our minds. The difficult part of this assignment was to find out (recursively) the minimum steps required for a four stool configuration. Although this may sound exaggerated, it took days for us to figure out what was going on.

For this week’s lab, we traced recursive functions and attempted to write our own as well. This lab was really useful because by practicing more, the concept of recursion became clearer. We even wrote one of the extra problems so we could practice more. Now I feel more comfortable with recursion, although I know it will get harder as the time passes.

Inheritance

Imagine you’ve written code containing more than a hundred lines. After running the program you’ve made, you may want to create a new program that has similar functions than the one you’ve made previously. It would be horrible if you had to rewrite your long code just for modifying little things. You could copy and paste the original code into a new file, but, if a mistake is made when attempting to change the code, the whole program may be ruined. Luckily, inheritance makes your life easier as a programmer. When we talk about inheritance, let’s imagine that the original code is the parent of all the smaller codes you write to modify it. The daughter/son (as you may want to put it) codes are known as sub classes and the father/mother is known as the super class. As you may have guessed, these sub classes are created to modify certain methods or attributes from the super class or to add new ones. When a sub class is created (which refers to its super class) it inherits all the functions from its parent and you can modify certain methods from it or add new ones to make the new class behave differently. 

In this week’s lab, we created a Motorized class, which created a certain vehicle, measured its fuel level, filled the vehicle’s tank and moved the vehicle to a different point (depending on its fuel level). After that, we wanted to create new classes that behaved similarly, but had different attributes and methods. For example, we created the Car and Motorcycle sub classes which created new vehicles, but with different attributes. Then, we created a new HumanPowered class (which didn’t inherit anything from Motorized) and realized that we had repeated code. To fix this, we created a re-factoring code, which included both HumanPowered and Motorized in order to prevent repeated code. 

OOP and ADTs

So far, we’ve been talking mostly about Object Oriented Programming (OOP) and Abstract Data Types (ADTs). OOP refers to the creation of a program or software by creating any types of objects that contain both data and functionality together. An object can be anything that you can imagine: a boat, a galaxy, an alien, Dumbo, etc. These objects can just exist by themselves (if no attributes are given to them) or can contain any data that can differentiate them from other objects and can be implemented. For example, let’s say that a boat has a colour and that a galaxy has a composition and an age. These characteristics are parameters attributed to the object in the initializer, which is the first function (inside the class) that creates the object. When creating an object, methods can be added to the class. These methods are functions defined in the class that give some type of functionality to the object. Let’s take Dumbo as an example for an object. If a method “fly” is added to its class, then we can make Dumbo fly! So, with the ability of creating objects with different functions, Computer Scientists can make (and probably they do) the programming experience much easier and faster. Instead of using procedural programming, they can use OOP to put any real world object or concept into code, which will eventually beneficiate the users of the created program by enhancing tasks, or just giving them fun times (in the case of videogames or any other program that you may find fun).

OOP is also used to create ADTs, which as explained by their name, they are not concrete types such as the examples provided earlier. In other words, we don’t know where they’ll be implemented. Using OOP for these is useful because if the ADT has to be implemented in various scenarios, then the code would not have to be rewritten, but it can be reused as many times as long as it works in each case. In the second lab, we worked with the Stack and Queue ADTs. After writing code for each of them, we analysed the runtime of each one. We noticed that the Queue functions were slower than the Stack ones. At first, we thought that, as the dequeue method had one if statement, then as it had one more line than the pop method in the Stack class, the program would have to make one more comparison and therefore the slower runtime. But, afterwards we found out that the reason that it was slower was that as it popped the first item in the list (the one at index 0), then the other items had to be shifted one index to the left in order to create a new list. I am still wondering how can this problem be fixed.

Welcome to my blog!

Welcome to my blog for CSC148 (Introduction to Computer Science) at the University of Toronto. I’ll be posting one entry each week. Here, I’ll keep a record of the themes learned in class and other things that I may find interesting during this course. I’ll share my thoughts about these and any problems encountered. Feel free to comment on each entry. Enjoy!