Pseudocodifica selection sort C++

[MPG]

Il prof ha spiegato cosi' i passaggi della pseudocodifica del selection sort:

4 2 1 3
2 4 1 3
1 4 2 3

(1) 4 2 3
(1) 2 4 3
(1 2) 4 3

1 2 3 4

Andando qui
https://books.google.it/books?id=oA77AwAAQBAJ&pg=PA236&lpg=PA236&dq=pseudocodifica+selection+sort&source=bl&ots=urlw-HaJpR&sig=WLdQflfCxguQirvkklhbDY3i0n8&hl=it&sa=X&ved=2ahUKEwji7s_-uvPaAhVHyRQKHfKACjMQ6AEwCHoFCAAQhQE#v=onepage&q=pseudocodifica selection sort&f=false
la vedo un po' diversa...
Inoltre perche' nella spiegazione viene messo
Per i=1,2....n RIPETI quando nella codifica viene scritto:
for(i=0; i<dim-1; i++)
come nel code sotto che ho fatto? (quindi il controllo di i parte da 0 non da 1)
Qualcuno puo' aiutarmi per non confondere le idee e spiegarmi meglio il tutto?
Grazie infinite.

#include<iostream>

using namespace std;
int main()
{
int i,j,dim, min;

cout<<"Dimensioni array: ";
cin>>dim;

int arr[dim];

cout<<"Valori dell' array: "<<endl;
for(i=0; i<dim; i++)
cin>>arr[i];

for(i=0; i<dim-1; i++)
{
min = i;
for(j=i+1; j<dim; j++)
{
if(arr[j] < arr[min])
// if(arr[j] > arr[min])  Se si vuole un ordinamento decrescente
min = j;
}
int tmp = arr[min];
arr[min] = arr[i];
arr[i] = tmp;
}

cout<<"Ordinamento con selection sort: ";
for(i=0; i<dim; i++)
cout<<arr[i]<<",";

 

[Skills07]

ciao ti riporto il selection sort da me studiato in università con pseudo code in Java

public class Selection{
public static void sort(Comparable[] a)
{int N = a.lenght;
for(int i=0; i<N; i++)
{int min = i;
for(int j=i+1; j<N; j++)
if (less(a[j],a[min])) min=j;
exch(a,i,min);}
}
\\...}

spero possa esserti utile

 

[MPG]

Grazie purtroppo mi serve in C++.
A dir la verità piu' che il codice era capire come si arriva ad ottenere il tutto , insomma la spiegazione dell'ordinamento dei vari passaggi (prima ancora della codifica).

 

[rodhellas]

Inoltre perche' nella spiegazione viene messo
Per i=1,2....n RIPETI quando nella codifica viene scritto:
for(i=0; i<dim-1; i++)
come nel code sotto che ho fatto? (quindi il controllo di i parte da 0 non da 1)

E' pseudo-codice, nessuno ha specificato che si tratti di un array. Ciclare da 0 a n-1 o da 1 a n non cambia nulla a livello logico.
https://it.wikipedia.org/wiki/Selection_sort
Più chiaro di cosi non si trova.

 

[rctimelines]

l'algoritmo deve ricostruire la lista mettendo in sequenza dalla cima il valore più piccolo "selezionato" (da cui il nome) nella parte rimanente.
La velocità aumenta man mano che si procede, i confronti sono molti, determinati dalla lunghezza della lista, ma il numero di spostamenti è minimizzato perché se la lista è ordinata, dopo i confronti ogni valore rimane al suo posto.

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[MPG]

Scusate se insisto ma ho compito domani.
Riporto questi passaggi del prof :

4 2 1 3
2 4 1 3
1 4 2 3
(quindi ho scambiato 1 e secondo poi primo e terzo)

(1) 4 2 3
(1) 2 4 3 (il primo numero non è piu' considerato, scambiato secondo e terzo numero)
(1 2) 4 3

1 2 3 4 (i primi due numero non sono piu' considerati, scambiato 3 e quarto numero)

In pratica arrivati a (1) 4 2 3 c'è uno scambio tra il secondo e il terzo e poi tra il terzo e il quarto numero.
Ho trovato anche questo che vi allego, in cui nel pass 2 c'è invece lo scambio tra il secondo e il terzo poi tra il secondo è il quarto e cosi' via.. Inoltre nel pass1 c'è il controllo anche tra il primo e ultimo numero.Insomma trovo sempre cose diverse.
Se dovessi seguire il prof se avessi che so 5 o 6 numeri (anzichè 4 come esempio) ad esempio

7 5 3 2 6

che passaggi avverrebbero ? E' una domanda che ci sarà (al di la' del programma codificato) e vorrei capire bene, solo che trovo diverso online....

Sarebbe cosi?
75326
57326
37526
27536

(2) 7536
(2) 5736
(2) 3756

(2 3) 576
(2 3 5) 67

 

[rctimelines]

Il primo passaggio è sbagliato, l'algoritmo nel primo giro di confronti trova 1 e lo mette in prima posizione scambiandolo col 4. Poi cerca negli altri tre numeri e trova il 2 ...

4 2 1 3
(1) 2 4 3
(1 2) 4 3
(1 2 3 4)

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[MPG]

Il primo passaggio è sbagliato, l'algoritmo nel primo giro di confronti trova 1 e lo mette in prima posizione scambiandolo col 4. Poi cerca negli altri tre numeri e trova il 2 ...

4 2 1 3
(1) 2 4 3
(1 2) 4 3
(1 2 3 4)

Inviato dal mio Nexus 5 utilizzando Tapatalk

Non so che dire il prof (ne sono sicuro al 100%) alla lavagna ha scritto cosi':
4 2 1 3
2 4 1 3
1 4 2 3
(1) 4 2 3
(1) 2 4 3
(1 2) 4 3
1234

In effetti guardando il file che ho allegato il controllo avviene allo step 1 tr ail primo numero e gli altri successivi allos tep 2 tra il secondo e gli altri successivi e cosi' via...

 

[rodhellas]

Ad occhio sembra un misto tra bubble sort e selection sort. Appena trova un numero da scambiare lo scambia.
Probabilmente il tuo prof è abituato a scriverlo come codice cosi (in modo ricorsivo).

 

[rctimelines]

Ad occhio sembra un selectionsort, ma senza l'ausilio di una variabile di supporto (per il minimo). Appena trova un numero da scambiare lo scambia.
Probabilmente il tuo prof è abituato a scriverlo come codice cosi (in modo ricorsivo).

In tal caso non sarebbe un selection sort

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[rodhellas]

In tal caso non sarebbe un selection sort

Inviato dal mio Nexus 5 utilizzando Tapatalk

Non sono stato abbastanza veloce a modificare il mio commento:cav:

 

[_Achille]

Ad occhio sembra un misto tra bubble sort e selection sort. Appena trova un numero da scambiare lo scambia.
Probabilmente il tuo prof è abituato a scriverlo come codice cosi (in modo ricorsivo).

Eh a guardarlo volevo dirlo pure io, ma non capisco il criterio di scelta tra Bubble e Selection.
Comunque sappi che mischiare due algoritmi di sorting non è male ma vai a favorire la velocità per certe disposizioni di dati, sfavorendo altre.

Per ora attieniti all’algoritmo puro (che per quanto ho capito è proprio quello che il tuo prof vuole). Quindi trovi il minimo e lo metti nella posizione i-esima scambiandolo.

 

[DispatchCode]

Ad occhio sembra un misto tra bubble sort e selection sort. Appena trova un numero da scambiare lo scambia.
Probabilmente il tuo prof è abituato a scriverlo come codice cosi (in modo ricorsivo).

Eh a guardarlo volevo dirlo pure io, ma non capisco il criterio di scelta tra Bubble e Selection.
Comunque sappi che mischiare due algoritmi di sorting non è male ma vai a favorire la velocità per certe disposizioni di dati, sfavorendo altre.

Per ora attieniti all’algoritmo puro (che per quanto ho capito è proprio quello che il tuo prof vuole). Quindi trovi il minimo e lo metti nella posizione i-esima scambiandolo.

Se intendi la scelta tra i due, in generale, allora considera che:

- BubbleSort scambia due valori quando i+1 è maggiore di i;
- SelectionSort quando trova un elemento più piccolo di quello considerato, lo riporta indietro.

Di fatto sono due scelte non ottimali.

Mischiare due algoritmi è sensato, ma è bene sapere il modo corretto. Rimane saggio attenersi anche a quanto riconosciuto per evitare di peggiorare le prestazioni (cosa difficile se il tempo è già ~N^2).

Inviato da ONEPLUS A5000 tramite App ufficiale di Tom\'s Hardware Italia Forum

 

[_Achille]

Se intendi la scelta tra i due, in generale, allora considera che:

- BubbleSort scambia due valori quando i+1 è maggiore di i;
- SelectionSort quando trova un elemento più piccolo di quello considerato, lo riporta indietro.

Di fatto sono due scelte non ottimali.

Mischiare due algoritmi è sensato, ma è bene sapere il modo corretto. Rimane saggio attenersi anche a quanto riconosciuto per evitare di peggiorare le prestazioni (cosa difficile se il tempo è già ~N^2).

Inviato da ONEPLUS A5000 tramite App ufficiale di Tom\'s Hardware Italia Forum

Sì ma non ho capito precisamente che fa.
Comunque è vero ci sono algoritmi di sorting taaaaanto migliori (Shell Sort, Quicksort, Merge Sort...) che se combinati fanno pure meglio.
A fini didattici Selction Sort è il migliore ma a quanto ho capito il prof ha fatto ben oltre che prendere il minore e scambiarlo di posizione...