2016-06-08 17 views
6

Sto imparando gli algoritmi e provo a scambiare i numeri interi in un array usando Swift, so che è efficace usare la funzione 'swap' ma cerco di imparare approcci diversi. così cerco metodi diversi e non capisco una cosa - ho una serie di 200 int e quando uso questo metodo:Algoritmo di scambio di interi

func selectionSort(var array: [Int]) { 
print("Selection Sort") 
for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
      let temp = array[j] //runs 7282 times 
      array[j] = array[i] // runs 7282 times 
      array[i] = temp  // runs 7282 times 
     } 
    } 
} 
print(array) 
} 

corre per 7 secondi e il codice di swap viene eseguito 7282 (o giù di lì) volte, ma quando uso questo:

func selectionSort(var array: [Int]) { 
    print("Selection Sort") 
    for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
      array.insert(array[j], atIndex: i) 
      array.removeAtIndex(j+1) 

     } 
    } 
    } 
    print(array) 
} 

funziona solo 198 volte in 1,3 secondi?

Non capisco perché il numero di esecuzioni è così diverso? Appare solo in selezione. Non vi sono differenze di questo tipo nel numero di esecuzioni se utilizzo, ad esempio, il bubble sort.

+0

Si ottengono array ordinati in entrambi gli esempi? Sembra che il secondo metodo rimuova uno dei valori e duplichi l'altro valore, il che significa che l'implementazione potrebbe essere errata. Ci si aspetterebbe meno esecuzioni del codice menzionato perché il predicato attorno ad esso non si terrà più spesso se si duplica ogni valore nell'array. – Glubus

risposta

3

In seguito, ho trovato il problema. Il primo tipo dovrà spostare il numero più volte per farlo nella sua posizione corretta. Il secondo ordinamento sposta più numeri allo stesso tempo perché l'inserto sostituirà altri numeri nell'array. L'ho testato con una serie di 5 numeri interi.

Ecco il debugger prima che il primo metodo di ordinamento inizia:

enter image description here

Notate come 3 è lontano dalla sua posizione corretta, ora, dopo il primo metodo ordina una volta, la matrice ora assomiglia a questo

enter image description here

Ora 3 è nella posizione corretta, ma 4 è ora lontano dalla sua posizione corretta. Dovrà ripetere questo e spostarsi 4 molte volte fino a raggiungere la sua posizione finale. Il prossimo scambio assomiglia a questo

enter image description here

Ora 14 è stato spostato di fronte a 17 come si deve, ma la sua ancora lontano dalla sua posizione corretta. Quindi dovrà essere spostato di nuovo!


Diamo un'occhiata al secondo metodo di ordinamento.

Ecco come si presenta prima che il tipo

enter image description here

e dopo il primo swap sembra che questo

enter image description here

Ora si può vedere che dopo un solo di swap, 3 E 4 sono nelle posizioni corrette. 3 è stato spostato solo una volta e per questo è stato spostato davanti a 4, che si è spostato 4 nella posizione corretta.

Ora dopo un altro scambio ...

enter image description here

Ora si può vedere che già sia ordinato correttamente dopo 2 swap utilizzando il secondo metodo, ma ci sono voluti il ​​primo metodo 4 swap. La differenza cresce solo quando si dispone di un array più grande.

Il secondo metodo sposta più numeri spingendo numeri indietro di un indice ogni volta inserisce ...

un esempio: 4,17,14,3,20

  • 4 è attualmente indice 0
  • 17 è attualmente all'indice 1
  • 14 è attualmente dall'indice 2

se inserisco 3 in th e davanti ...

3,4,17,14,3,20

ora rimuovere il precedente 3 ...

3,4,17,14,20

  • 4 è ora all'indice 1!
  • 17 è ora all'indice 2!
  • 14 è ora all'indice 3!
+1

sta usando un inserto e lo rimuove ogni volta, il che mantiene il conteggio dell'array lo stesso – Scriptable

+0

@Scriptable hai ragione. Ero così sbagliato, ho modificato la mia risposta. Penso di aver trovato il problema –

+0

Buona investigazione, il codice si legge come se fosse la stessa identica funzionalità ma non lo è. Ancora non ha senso per me come si muove più numeri :( – Scriptable

2

I metodi sono abbastanza diversi.

Il primo esegue un semplice scambio ogni volta array[j] < array[i], come previsto.

Il secondo, quando array[j] < array[i] è vero, sposta array[j] nella posizione -esimo i e sposta il resto della matrice di una posizione.

Detto questo, ho avuto un po 'di tempo sulle mie mani, così ho deciso di scrivere gli algoritmi a Swift 3 (si prega di notare come si può evitare di usare temp):

func selectionSort(_ array: [Int]) { 
    var array = array 
    for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
     (array[j], array[i]) = (array[i], array[j]) 
     } 
    } 
    } 
    print(array) 
} 

func selectionSort2(_ array: [Int]) { 
    var array = array 
    for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
     array.insert(array[j], at: i) 
     array.remove(at: j+1) 
     } 
    } 
    } 
    print(array) 
} 

Cheers!