--- # System prepended metadata title: B2.4.3 Bubble and selection sort --- # B2.4.3 Sorting algorithms :::info This is a note part of the coding course for IB Computer Science program. If you want to check out other parts of the same course you can see them in [This link of teaching material](/68GDv_RgT-yh9oERMvdnFw) ::: :::warning :warning: Note still under construction :warning: ::: ## Sorting algorithms In the previous syllabus you need to know bubble sort and selection sort. We're going to discuss a bit more, but those are the ones that you need to be able to construct ## Pre-requisites ### Swapping in python It's important to know how to swap values. 2 ways of swapping in python: If we have a = 5 and b = 3 and we want a = 3 and b = 5 __the python way__: ``` a, b = b, a ``` __the regular way__: ```python temp = a a = b b = temp ``` :::danger the wrong way ``` a = b b = a ``` b is going to overwrite a so b is going to have the same value as A ::: ## Bubble sort ![](https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif) ### Sample implementation 1 ```python= mylist = [64, 34, 25, 12, 22, 11, 90, 5] n = len(mylist) for i in range(n-1): for j in range(n-i-1): if mylist[j] > mylist[j+1]: mylist[j], mylist[j+1] = mylist[j+1], mylist[j] print(mylist) ``` _(source: https://www.w3schools.com/python/python_dsa_bubblesort.asp)_ ### Sample implementation 2 ```python= def bubble_sort(arr): n = len(arr) for i in range(n): swapped = False for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if not swapped: break ``` _(source: https://ellibrodepython.com/bubble-sort)_ ### Pros and cos //TO-DO by the students! ### Reference https://ellibrodepython.com/bubble-sort (in Spanish) https://en.wikipedia.org/wiki/Bubble_sort ## Selection sort ### Sample implementation 1 ```python= mylist = [64, 34, 25, 5, 22, 11, 90, 12] n = len(mylist) for i in range(n-1): min_index = i for j in range(i+1, n): if mylist[j] < mylist[min_index]: min_index = j min_value = mylist.pop(min_index) mylist.insert(i, min_value) print(mylist) ``` _(source: https://www.w3schools.com/python/python_dsa_selectionsort.asp)_ ### Sample implementation 2 ```python= def selectionSort(array, size): for ind in range(size - 1): min_index = ind for j in range(ind + 1, size): if array[j] < array[min_index]: min_index = j array[ind], array[min_index] = array[min_index], array[ind] arr = [-2, 45, 0, 11, -9, 88, -97, -202, 747] size = len(arr) selectionSort(arr, size) print(arr) ``` _(source: https://www.geeksforgeeks.org/python/python-program-for-selection-sort/)_ ### Pros and cons //TO-DO by the students! ### Reference https://www.w3schools.com/python/python_dsa_selectionsort.asp :::info This is an algorith that _seems_ to work, but it doesn't. Find out why! _before seeing it in the comments, or when you see the comments_ https://discuss.python.org/t/selection-sort-algorithm/60861 ::: https://www.geeksforgeeks.org/python/python-program-for-selection-sort/ ## HL only theory Quicksort: I don't think it's going to happen in the exam, but I prefer to go as if it were going to happen. Heapsort. We're going to check it out just if we have seen heaps. It's not going to happen in the exam. ### Quicksort References: https://www.youtube.com/watch?v=UrPJLhKF1jY https://www.youtube.com/watch?v=7h1s2SojIRw ### Heapsort Reference: https://www.youtube.com/watch?v=HqPJF2L5h9U+ ## Exercises The question is usually how can they ask this in an exam? The two main ways are theoretical or practical Theoretical can be questions like: Compare the effectiveness of Selection sort and bubble sort. Practical questions can be + Identify a sorting algorithm of bubble or selection sort (with other implementation) + Implement bubble or seletcion sort (usually through parallel arrays or objects) ### Sort parallel arrays Parallel arrays are common in the exercises from previous syllabus. The idea is that you need to sort not only 1 list (or array) but 2 of them. We have 2 parallel arrays in a program for a school: `names` and `grades`. We want to sort both of them so names are sorted and they keep the parallel relationship. You can use any sorting algorithm that you may have but I splitted the class between selection sort and bubble sort. (In the exams they may specify which algorithm to use) ### Find the error What would be the error in this solution for the previous exercise? ![image](https://hackmd.io/_uploads/S15E2QITbe.png) What would be the error in this solution? ```python! names = ["Pepa", "Pipo", "Pepe", "TJ"] grades = [6, 6, 5, 7] def bubblesort(names, grades): swapped = False for n in range(len(grades) - 1, 0, -1): for i in range(n): if grades[i] > grades[i + 1]: swapped = True names[i], names[i + 1] = names[i + 1], names[i] grades[i], grades[i + 1] = grades[i + 1], grades[i] if not swapped: return bubblesort(names, grades) print(names) print(grades) ``` ```python! names=["Pipo", "Pepa", "Pepe", "Thomas Jefferson"] grades=[6, 5, 7, 2] calif = dict(zip(names, grades)) items = list(calif.items()) n = len(items) for i in range (n): for j in range(0, n-i-1): if items[j][0]>items[j+1][0]: items[j], items[j+1]=items[j+1], items[j] print(dict(items)) ``` Credit E.C. ### OOP connection It's common for these topics to intertwine. So instead of sorting some numbers or some strings, we're going to sort objects. (By their propierties) Now, keeping the same example of students and grades, we could have a class Student defined by names and grades We're going to do with the encapsulated version. ```python! class Student(): def __init__(self, name, grade): self.name = name self.grade = grade def getName(self): return self.name def setName(self, name): self.name= name def getGrade(self): return self.grade def setGrade(self, grade): self.grade = grade ``` Let's think of 20 instantiations of students that are in the list `students` Order them by name. #### Bubblesort solution ```python! students #list of the Students objects that we want to sort for startingIndex in range(len(students)-2): # This has a -2 because the last comparasion will be between len(students)-2 and len(students)-1 indexes for index in range(startingIndex, len(students)-1): #compare all elements so one with the next. We stop one before the end. if students[index].getName() > students[index+1].getName(): #Swapping the python way students[index], student[index+1] = student[index+1], students[index] ``` ### Selection Sort solution: ```python! students #list of the Students objects that we want to sort for i in range(len(students)): maxindex=0 for j in range(len(students)-i): if students[j].getName()>students[maxindex].getName(): maxindex=j students[maxindex], students[len(students)-i-1]=students[len(students)-i-1], students[maxindex] ``` ### OOP exercise squid game ![image](https://hackmd.io/_uploads/SkObban6bg.png) Squid game https://en.wikipedia.org/wiki/Torment_Nexus In the squid games there is an (unordered) list (`all_players`) Here you have a possible implementation of the class Player ```python! class Player (): def __init__(self, name, number): self._name, self._number= name, number self._in_game=True def get_name(self): return self._name def get_number(self): return self._number def is_in_game(self): return self._in_game def lose(self): self._in_game=False ``` Credit: E.C. Every time that a game happens, there are some players that are eliminated from the game, so the method `lose()` is called. For example, this can be in the driver: ```python! all_players=[Player ("Alba", 1), Player ("Edwin", 5), Player ("Fiona", 6), Player ("Corine", 3), Player ("Diana", 4), Player ("Bob", 2)] all_players[1].lose() all_players[5].lose() ``` Revision question. Write a list of the remaining players. _(this would be a 1 mark question in an exam)_ Solution on the spoiler: :::spoiler The list would have Alba, Fiona, Corine and Diana in that order. Remember that `all_players[x]` access to the `x` **index** ::: Actual question: Construct in python an algorithm that creates an **updated** list in the variable `remaining_players` with only the players that are still left **in order by number**. For example if we had the code that was before, the final list would be: Alba, Corine, Diana, Fiona. #### Solution with bubblesort #### Solution with selection sort. #### Solution with quicksort This would be the final implementation using quicksort (including an implementation of the class Player. ) ```python= class Player (): def __init__(self, name, number): self._name, self._number= name, number self._in_game=True def get_name(self): return self._name def get_number(self): return self._number def is_in_game(self): return self._in_game def lose(self): self._in_game=False def update_remaining_quicksort(all_players, done): list=[x for x in all_players if x.is_in_game() and done] if len(list)<=1: return list pivot=list[len(list)//2] left=[x for x in list if x.get_number() < pivot.get_number()] middle=[x for x in list if x.get_number() == pivot.get_number()] right=[x for x in list if x.get_number() > pivot.get_number()] return update_remaining_quicksort(left, True) + middle + update_remaining_quicksort(right, True) def update_remaining_bubble(all_players): list=[x for x in all_players if x.is_in_game()] for i in range(len(list)-1): if list[i].get_number()>list[i+1].get_number(): list[i], list[i+1]=list[i+1], list[i] return list all_players=[Player ("Alba", 1), Player ("Edwin", 5), Player ("Bob", 2), Player ("Corine", 3), Player ("Diana", 4), Player ("Fiona", 6)] all_players[0].lose() all_players[5].lose() print([x.get_name() for x in update_remaining_quicksort(all_players, True)]) print([x.get_name() for x in update_remaining_bubble(all_players)]) ``` Credit: E.C. #### Extra binary search Now that we have the list sorted, we need to find if a specific player with a specific number is on the list. If it's found a) Implement this with a linear search (two different implementations) b) Implement this with a binary search (only one implementation) #### Extra HL question Open question: How could be this optimized if we have a game where we're only going to have less and less players over time? Could we use... **heaps**? ### Exercises with books (concatenation of sorting) Now let's say that we have a OOP implementation on books. Each book has a title, an author name (Starting with the surname) and a date of publication (year). All of them are the list `books` One book could be represented like this: :::info title: "Don Quixote" author: "Cervantes Saavedra, Miguel de" date: 1605 ::: In this case we're going to supose that they are not encapsulated, so we can access to a specific information of the book just with the dot operator. (To be specific: `book.author`, `book.title` and `book.date`) Now we want them sorted by author, but if they have the same name of author, we want to have them ordered by date (So if 2 books are from Cervantes, we want the first one first and the later one after) ## Why not just use sort()??????? Try the following: Create an empty list called `students` Copy the definition of Student from before. Append 5 different students with names that are not in alphabetical order and different grades. Use students.sort() Print the new list with their names. (it shouldn't work, why?) Solution: The error is related that we cannot compare references between them is the refernce to 1 student 09AF-3DF2 bigger or lower than the reference 88B2-FE42? Since Python can't tell the difference is going to raise an error. For solving that we could either use the methods that we have discussed here or implement methods `__gt__` (greater than), `__lt__` (less than). These are standarized names for methods like `__init__` or `__str__` For more info on this _nerd_ stuff you can see here: https://docs.python.org/3/library/operator.html ## HL Exercises ### Parallel arrays. Now with quicksort! ### OOP. Now with quicksort! ## Questions to the IB They are not saying sort() but they are saying sort() ![image](https://hackmd.io/_uploads/HymVcHUaWg.png)