promotion image of download ymail app
Promoted
Anonimo
Anonimo ha chiesto in Computer e InternetProgrammazione e Design · 2 mesi fa

Selection sort c++?

I confronti del selection sort di un array  possono essere maggiori della sua dimensione? 

2 risposte

Classificazione
  • 2 mesi fa
    Risposta preferita

    Se non ricordo male l'algoritmo di Selection Sort ordina un array selezionando di volta in volta il massimo della sua parte non ancora ordinata (oppure il minimo, a scelta, ma io assumerò che si cerchi il massimo) e poi lo posiziona nelle posizioni finali (se hai scelto il massimo, iniziali se avessi scelto il minimo) dell'array. Di volta in volta di viene chiesto di calcolare il massimo di un sottoarray di quello di partenza la cui dimensione diminuisce ad ogni passaggio: al primo, detta N quella dell'array originario, dovrai trovare il massimo di un array di dimensione N e posizionare tale massimo in fondo all'array di partenza (tramite uno scambio); al secondo passaggio dovrai trovare il massimo dell'array escludendo l'ultima posizione, dove si trova un elemento, il massimo dell'array, già nella sua posizione giusta, e quindi la dimensione sarà N-1; posizionerai il secondo massimo che trovi nella penultima posizione dell'array e via dicendo finché non arrivi ad avere un sottoarray di dimensione 1. 

    Per trovare il massimo di un array di dimensione K devi necessariamente scorrere tutti i suoi elementi (non puoi sapere che un certo valore è il massimo se non lo hai confrontato con tutti gli altri) ed il modo più efficiente per farlo richiede esattamente (K-1) confronti.

    Come conseguenza di questo il tuo Selection Sort effettuerà un numero di confronti pari ad (N-1)+(N-2)+ ... + 1 = N*(N-1)/2 confronti in totale. 

    • Commenter avatarAccedi per rispondere alle risposte
  • 2 mesi fa

    ----------------

    Si

Altre domande? Fai una domanda e ottieni le risposte che cerchi.