# 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__:

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


### Sample implementation 1

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

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

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

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?


What would be the error in this solution?

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)

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.

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

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:

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

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

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:

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. )

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()