Diary

Venditore: Almanacchi, almanacchi nuovi; lunari nuovi. Bisognano, signore, almanacchi?
Passeggere: Almanacchi per l’anno nuovo?

Detto altrimenti: non è che perché ci sta la munnezza, non ci sta il Cristo velato. No. Ci sta la munnezza e poi ci sta pure il Cristo velato. Siente a me: esistono altri posti pieni di munnezza, certo, ma un altro Cristo velato, però, no, mi dispiace, non ce lo trovi. E chest’è!

SELECTION SORT is a comparison sorting algorithm that is used to sort a random list of items in ascending order. The comparison does not require a lot of extra space. It only requires one extra memory space for the temporal variable.

By default, the sorted list is empty, and the unsorted list contains all the elements. The unsorted list is then scanned for the minimum value, which is then placed in the sorted list. This process is repeated until all the values have been compared and sorted.

How does selection sort work?

The first item in the unsorted partition is compared with all the values to the right-hand side to check if it is the minimum value. If it is not the minimum value, then its position is swapped with the minimum value.

Example:

• For example, if the index of the minimum value is 3, then the value of the element with index 3 is placed at index 0 while the value that was at index 0 is placed at index 3. If the first element in the unsorted partition is the minimum value, then it returns its positions.
• The element that has been determined as the minimum value is then moved to the partition on the left-hand side, which is the sorted list. 
• The partitioned side now has one element, while the unpartitioned side has (n – 1) elements where n is the total number of elements in the list. This process is repeated over and over until all items have been compared and sorted based on their values.

Problem Definition

A list of elements that are in random order needs to be sorted in ascending order. Consider the following list as an example.

5, 7, 2, 3, 8

The above list should be sorted to produce the following results

2, 3, 5, 7, 8.

Solution (Algorithm)

Step 1) Get the value of n which is the total size of the array

Step 2) Partition the list into sorted and unsorted sections. The sorted section is initially empty while the unsorted section contains the entire list

Step 3) Pick the minimum value from the unpartitioned section and placed it into the sorted section. 

Step 4) Repeat the process (n – 1) times until all of the elements in the list have been sorted.

Visual Representation

Given a list of five elements, the following images illustrate how the selection sort algorithm iterates through the values when sorting them.

The following image shows the unsorted list

Step 1)

The first value 5 is compared with the rest of the values to check if it is the minimum value.

2 is the minimum value, so the positions of 5 and 2 are swapped. The green values represent the sorted partition of the list.

Step 2)

The value 7 which is the first element in the unsorted partition is compared with the rest of the values to find out if a lower value exists:

3 is the minimum value, so the positions of 7 and 3 are swapped:

Step 3)

The first element of the unsorted list with the value of 5 is compared with the rest of the values to check if it is the minimum value.

Step 4)

The value 7 is compared with the rest of the values. The value 7 is the minimum value, so it maintains its position in the sorted partition.

Step 5)

We only have one value left in the unpartitioned list. Therefore, it is already sorted.

The final list is like the one shown in the above image.

Selection Sort Program using Python

The following code shows the selection sort implementation using Python

Run the above code produces the following results

Here is Code explanation:

1. Defines a function named selectionSort
2. Gets the total number of elements in the list. We need this to determine the number of passes to be made when comparing values.
3. Outer loop. Uses the loop to iterate through the values of the list. The number of iterations is (n – 1). The value of n is 5, so (5 – 1) gives us 4. This means the outer iterations will be performed 4 times. In each iteration, the value of the variable i is assigned to the variable minValueIndex
4. Inner loop. Uses the loop to compare the leftmost value to the other values on the right-hand side. However, the value for j does not start at index 0. It starts at (i + 1). This excludes the values that have already been sorted so that we focus on items that have not yet been sorted.
5. Finds the minimum value in the unsorted list and places it in its proper position
6. Updates the value of minValueIndex when the swapping condition is true
7. Compares the values of index numbers minValueIndex and i to see if they are not equal
8. The leftmost value is stored in a temporal variable
9. The lower value from the right-hand side takes the position first position
10. The value that was stored in the temporal value is stored in the position that was previously held by the minimum value
11. Returns the sorted list as the function result
12. Creates a list el that has random numbers
13. Print the sorted list after calling the selection Sort function passing in el as the parameter.

The largest-so-far value, again initially the first number, must be compared to all the other numbers in the unsorted
part of the list, which will require \(n-2\) comparisons. The number of comparisons keeps decreasing as the length of the unsorted section of the list gets smaller, until finally only one comparison is needed. The total number
of comparisons is

\((n-1)+(n-2)+(n-3)+ \ldots + 3+2+1= \frac{(n-1) n}{2}=\frac{n^2-n}{2} \)

The selection sort algorithm not only does comparisons, it does exchanges. Even if the largest number in the unsorted section of the list is already at the end of the unsorted section, the algorithm exchanges this number with itself.
Therefore, the algorithm does \(n\) exchanges, one for each position in the list to put the correct value in that position. However, the work contributed by exchanges and marker moving is so much less than the amount contributed by comparisons that it can be ignored.

Therefore, the number of executions is \(n^2\), which can also be expressed as \(O\left(n^2\right)\).

The selection sort has three categories of complexity namely:

• Worst case – this is where the list provided is in descending order. The algorithm performs the maximum number of executions which is expressed as \(O\left(n^2\right)\)
• Best case – this occurs when the provided list is already sorted. The algorithm performs the minimum number of executions which is expressed as \(\Omega\left(n^2\right)\)
• Average case – this occurs when the list is in random order. The average complexity is expressed as \(\Theta\left(n^2\right)\)

Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes.

Unlike traditional sorting algorithms, which attempt to sort with the fewest comparisons, pancake sort tries to sort the sequence in as few reversals as possible.

The idea behind pancake sort is similar to Selection Sort. In every iteration, we find the maximum element in the sequence and place it at the end, and reduce the size of the sequence by one.

Given an array of integers Arr:

• Write a function flip(Arr, i) that reverses the order of the first i elements in the array arr.
• Write a function pancakeSort(Arr) that sorts and returns the input array. You are allowed to use only the function flip in order to make changes in the array.

Algorithm :

Let the given array be Arr[] and size of the array be n

• Start from the current size n and reduce the current size by one while it is greater than one. Let the current size be c. Do the following for every c.
  1. Find the index i of the maximum element in Arr[0....c-1].
  2. Call flip(Arr,i)
  3. Call flip(Arr,c-1)

Array representation of the above diagram :

initial pancake order : [3, 5, 2, 1, 7, 6, 4]

First flip : [3, 5, 2, 1, 7, 6, 4]
after first flip : [7, 1, 2, 5, 3, 6, 4]

Second flip : [7, 1, 2, 5, 3, 6, 4]
after second flip : [4, 6, 3, 5, 2, 1, 7]

Third flip : [4, 6, 3, 5, 2, 1, 7]
after third flip : [6, 4, 3, 5, 2, 1, 7]

Fourth flip : [6, 4, 3, 5, 2, 1, 7]
after fourth flip : [1, 2, 5, 3, 4, 6, 7]

Fifth flip : [1, 2, 5, 3, 4, 6, 7]
after fifth flip : [5, 2, 1, 3, 4, 6, 7]

Sixth flip : [5, 2, 1, 3, 4, 6, 7]
after sixth flip : [4, 3, 1, 2, 5, 6, 7]

Seventh flip : [4, 3, 1, 2, 5, 6, 7]
after seventh flip : [2, 1, 3, 4, 5, 6, 7]

Eight flip : [2, 1, 3, 4, 5, 6, 7]
after eighth flip : [1, 2, 3, 4, 5, 6, 7]

Below, the Python code that implements the algorithm explained:

…and the output:

Each pancake therefore requires two flips, which would give a total of \(2n\) flips required. But the last two pancakes require at most one flip; if they are already in order, no flips are needed, and if they are out of order, only one flip is needed. So this algorithm requires at most \(2(n – 2) + 1 = 2n – 3\) flips in the worst case, which means that \(P_n \leq 2n – 3\).

Mi sono chiesto come mai mi piacciano i libri che mi fanno star male, “Non sarò un po’ masochista?”, mi son chiesto, e mi sono risposto con una cosa che mi è successa mentre scrivevo questo romanzo, nel gennaio del 2020. Ho partecipato alla riunione di una rivista che si chiama “Qualcosa”. L’argomento del numero di “Qualcosa” che stavamo preparando era: le storie sentimentali finite male; i disastri sentimentali, praticamente. Noi, quella sera lì, le venti persone che erano lì, di quei momenti che abbiamo passato tutti, che siam stati male per amore, se così si può dire, di quei giorni così dolorosi che eravamo messi così male che ci sembrava di non esser mai stati tanto male nella nostra vita, e non ci sembrava possibile stare peggio, a ripensarci dopo degli anni, ci veniva da pensare “Ma come son stato male bene, quel giorno lì. Ma che bello, essere così vivi”. Ecco. L’effetto che mi fa leggere (e rileggere) Delitto e castigo, Memorie del sottosuolo, L’idiota, I demoni, Il giocatore, I fratelli Karamazov è quello: mi accorgo di essere vivo, di avere un corpo, di avere il sangue che mi scorre nelle vene. Questo.

— Paolo Nori, Come mai mi piacciono. Novembre 2021

Here the LaTeX code:

and this is the output: