Ταξινόμηση εισαγωγής: Τι είναι και πώς λειτουργεί

Η ταξινόμηση εισαγωγής είναι ένας απλός αλγόριθμος ταξινόμησης για έναν μικρό αριθμό στοιχείων.

Παράδειγμα:

Στο είδος Εισαγωγής, συγκρίνετε το keyστοιχείο με τα προηγούμενα στοιχεία. Εάν τα προηγούμενα στοιχεία είναι μεγαλύτερα από το keyστοιχείο, τότε μετακινείτε το προηγούμενο στοιχείο στην επόμενη θέση.

Ξεκινήστε από το ευρετήριο 1 έως το μέγεθος του πίνακα εισαγωγής.

[8 3 5 1 4 2]

Βήμα 1 :

[8 3 5 1 4 2]
 key = 3 //starting from 1st index. Here `key` will be compared with the previous elements. In this case, `key` is compared with 8. since 8 > 3, move the element 8 to the next position and insert `key` to the previous position. Result: [ 3 8 5 1 4 2 ]

Βήμα 2 :

[3 8 5 1 4 2]
 key = 5 //2nd index 8 > 5 //move 8 to 2nd index and insert 5 to the 1st index. Result: [ 3 5 8 1 4 2 ]

Βήμα 3:

[3 5 8 1 4 2]
 key = 1 //3rd index 8 > 1 => [ 3 5 1 8 4 2 ] 5 > 1 => [ 3 1 5 8 4 2 ] 3 > 1 => [ 1 3 5 8 4 2 ] Result: [ 1 3 5 8 4 2 ]

Βήμα 4:

[1 3 5 8 4 2]
 key = 4 //4th index 8 > 4 => [ 1 3 5 4 8 2 ] 5 > 4 => [ 1 3 4 5 8 2 ] 3 > 4 ≠> stop Result: [ 1 3 4 5 8 2 ]

Βήμα 5:

[1 3 4 5 8 2]
 key = 2 //5th index 8 > 2 => [ 1 3 4 5 2 8 ] 5 > 2 => [ 1 3 4 2 5 8 ] 4 > 2 => [ 1 3 2 4 5 8 ] 3 > 2 => [ 1 2 3 4 5 8 ] 1 > 2 ≠> stop Result: [1 2 3 4 5 8]
[1 2 3 4 5 8]

Ο αλγόριθμος που εμφανίζεται παρακάτω είναι μια ελαφρώς βελτιστοποιημένη έκδοση για να αποφευχθεί η εναλλαγή του keyστοιχείου σε κάθε επανάληψη. Εδώ, το keyστοιχείο θα αλλάξει στο τέλος της επανάληψης (βήμα).

 InsertionSort(arr[]) for j = 1 to arr.length key = arr[j] i = j - 1 while i > 0 and arr[i] > key arr[i+1] = arr[i] i = i - 1 arr[i+1] = key

Ακολουθεί μια λεπτομερής εφαρμογή σε JavaScript:

function insertion_sort(A) { var len = array_length(A); var i = 1; while (i 
    
     = 0 && A[j] > x) { A[j + 1] = A[j]; j = j - 1; } A[j+1] = x; i = i + 1; } }
    

Μια γρήγορη εφαρμογή στο Swift φαίνεται παρακάτω:

 var array = [8, 3, 5, 1, 4, 2] func insertionSort(array:inout Array) -> Array{ for j in 0..
    
      0 && array[i] > key){ array[i+1] = array[i] i = i-1 } array[i+1] = key } return array }
    

Το παράδειγμα Java εμφανίζεται παρακάτω:

public int[] insertionSort(int[] arr) for (j = 1; j 
    
      0 and arr[i] > key) { arr[i+1] = arr[i] i -= 1 } arr[i+1] = key } return arr;
    

είδος εισαγωγής σε γ ....

void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i = 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } 

Ιδιότητες:

  • Διαστημική πολυπλοκότητα: O (1)

Πολυπλοκότητα χρόνου: O (n), O (n * n), O (n * n) για τις καλύτερες, μέσες, χειρότερες περιπτώσεις αντίστοιχα.

  • Καλύτερη περίπτωση: ο πίνακας έχει ήδη ταξινομηθεί
  • Μέση περίπτωση: ο πίνακας ταξινομείται τυχαία
  • Χειρότερη περίπτωση: ο πίνακας ταξινομείται αντίστροφα.
  • Ταξινόμηση στη θέση: Ναι
  • Σταύλος: Ναι

Άλλοι πόροι:

  • Βικιπαίδεια
  • CS50 - YouTube
  • SortInsertion - GeeksforGeeks, YouTube
  • Οπτικοποίηση ταξινόμησης εισαγωγής
  • Ταξινόμηση εισαγωγής - MyCodeSchool
  • Ταξινόμηση εισαγωγής - VisuAlgo