InsertSort

Z CHWiki

[editovat] Popis

Insert sort je podobný algoritmus ako select sort. Jeho princípom je, že považuje prvých k prvkov poľa za utriedených (na začiatku je k = 1, jednoprvkové pole je utriedené) a k+1 prvok zaradí na správne miesto medzi k prvých prvkov, potom bude k+1 prvkov utriedených.

[editovat] Príklad

pole na pred triedením
  6 8 4 5 2 3 1 7 0 9

1. krok
  6 | 8 4 5 2 3 1 7 0 9
  6 8 | 4 5 2 3 1 7 0 9  
2. krok  
  6 8 | 4 5 2 3 1 7 0 9
  4 6 8 | 5 2 3 1 7 0 9
3. krok  
  4 6 8 | 5 2 3 1 7 0 9
  4 5 6 8 | 2 3 1 7 0 9  
4. krok  
  4 5 6 8 | 2 3 1 7 0 9	
  2 4 5 6 8 | 3 1 7 0 9	
5. krok  
  2 4 5 6 8 | 3 1 7 0 9		
  2 3 4 5 6 8 | 1 7 0 9		
6. krok    
  2 3 4 5 6 8 | 1 7 0 9			
  1 2 3 4 5 6 8 | 7 0 9			
7. krok  
  1 2 3 4 5 6 8 | 7 0 9				
  1 2 3 4 5 6 7 8 | 0 9				
8. krok  
  1 2 3 4 5 6 7 8 | 0 9					
  0 1 2 3 4 5 6 7 8 | 9					
9. krok  
  0 1 2 3 4 5 6 7 8 | 9						
  0 1 2 3 4 5 6 7 8 9 | 						
10. krok  
  0 1 2 3 4 5 6 7 8 9 |						
  0 1 2 3 4 5 6 7 8 9 |

[editovat] Implementácia

// vloženie hodnoty hodnota na správne miesto v poli
// pole medzi prvých dlzka prvkov
function insert(pole, dlzka, hodnota)
    i := dlzka 
    while i > 0 and pole[i] > hodnota do
        pole[i+1] := pole[i]
        i := i - 1
    end while
    pole[i+1] := hodnota
end function

function insertSort(pole, dlzka)
    // i - počet prvkov na začiatku poľa, ktoré sú už utriedené
    for i := 1 to dlzka
        insert(pole, i, pole[i])
    end for
end function

Algoritmus je rovnako ako select sort triedy O(n²), narozdiel od select sortu rýchlosť závisí od vstupného poľa a pre takmer utriedené pole prebehne veľmi rýchlo.