Diary

• 

• 

• 

• 

Qui
non si sente
altro
che il caldo buono

Sono arrivata sul set digiuna da un giorno.
Volevo essere affamata, volevo che la scena fosse assolutamente realistica.
Simboleggia la voglia di divorare la vita.

– Dora Romano

Il preside quasi sempre appariva in cima alla scala nel momento in cui la nostra vociante orda si avventava a salirla: e la sua apparizione bastava a spegnere le voci e la corsa. Si chiamava Luigi Monaco. Ne ho un ricordo talmente vivo e profondo che sempre mi capita di confrontare a lui ogni persona severa e serena, veramente colta, veramente giusta, veramente ragionevole che (raramente) incontro. Ci conosceva uno per uno, con inflessibile ma al tempo stesso indulgente giudizio. I suoi rimproveri, le sue arrabbiature, suscitavano in noi contrizioni e rimorsi. Non riuscivamo nemmeno fra noi a fingere spavalderia, dopo un suo rimprovero. (L’ho ritrovato – amico ma sempre, per me, ‘il preside’ – dopo gli anni di scuola, quando cominciai a scrivere e poi a pubblicare: e il nostro incontro di ogni sera, nell’angolo di una libreria, quando lui è morto mi sono accorto che era la ragione per cui ero rimasto a Caltanissetta.)

– da Il maestro di Regalpetra di Matteo Collura

Altroché chemin-de-fer, prese di cocaina, partouzes… Leggere le millesedici pagine de I fratelli Karamazov vuole ben altra vocazione a sperperare il proprio tempo e, dunque, il propio denaro (o quello di chi ci vuole bene) sottraendoci ai rigori della realtà! ben altra ostinazione nell’errore! E si narra di un tredicenne che in tempo di scuola, per leggersi in pace I fratelli Karamazov tutto di fila, si sarebbe applicato con il massimo zelo, nei sospetti tepori del suo letto, a strofinare la punta del termometro, e avrebbe saltato sedici giorni di scuola di fila (si narra nel senso che lo narro io, perché so di certo, perché ero io, il tredicenne). Da allora, mettendo nel conto anche il rischio di imbattersi in parecchie schifezze, quell’io pratica la lettura con perseveranza, con l’abnegazione, con l’inconfessabile voluttà con cui coltiva tutti i suoi vizi. E finché il fatto non sarà perseguibile a termini di legge, egli si passerà lo spregevole lusso di sobillare alla lettura de I fratelli Karamazon a chiunque. E certo meglio di come l’ha letta lui quella prima volta. La traduzione, evidentemente condotta su una traduzione francese, era piuttosto oscena, a tratti incasinata; anche se a quel tempo non ci si attarda su dettagli del genere, ché si era di bocca molto più buona, allora. Ora che ho sottomano una copia de I fratelli Karamazov uscita per i tipi dell’Einaudi a traduzione di Agostino Villa, la voglia di rileggere quel capolavoro è tanta – tant’è che è tra i propositi (quelli buoni) per il prossimo anno. E a chi non l’avesse fatto ancora, non posso che consigliare l’avventura di una lettura così mostruosamente bella. Fidatevi!

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