Όλα όσα πρέπει να γνωρίζετε για τον αλγόριθμο Εισαγωγής Ταξινόμησης

Εισαγωγή

Γεια! Είμαι ο Sanjula και σε αυτόν τον οδηγό ελπίζω να σας διδάξω λίγο για τον αλγόριθμο Insertion Sort, όπως:

  • Τι είναι το είδος εισαγωγής;
  • Γιατί είναι σημαντική η εισαγωγή;
  • Απόδοση ταξινόμησης εισαγωγής
  • Πώς λειτουργεί η ταξινόμηση εισαγωγής;
  • Εφαρμογή Java τύπου εισαγωγής

Ας αρχίσουμε!

Τι είναι το είδος εισαγωγής;

Είναι ένας απλός αλγόριθμος ταξινόμησης που ταξινομεί έναν πίνακα ένα στοιχείο κάθε φορά.

Γιατί είναι σημαντική η εισαγωγή;

Το είδος εισαγωγής έχει πολλά πλεονεκτήματα όπως:

  • Η καθαρή απλότητα του αλγορίθμου.
  • Η σχετική σειρά αντικειμένων με ίσα κλειδιά δεν αλλάζει.
  • Η δυνατότητα ταξινόμησης μιας λίστας καθώς λαμβάνεται.
  • Αποτελεσματικό για μικρά σύνολα δεδομένων, ειδικά στην πράξη από άλλους τετραγωνικούς αλγόριθμους - δηλαδή O (n²).
  • Απαιτεί μόνο μια σταθερή ποσότητα επιπλέον χώρου μνήμης - O (1).

Απόδοση ταξινόμησης εισαγωγής

  • Η χειρότερη απόδοση του είδους εισαγωγής είναι οι συγκρίσεις και ανταλλαγές O (n²).
  • Η καλύτερη απόδοση είναι οι συγκρίσεις O (n) και οι ανταλλαγές O (1).
  • Η απόδοση της μέσης περίπτωσης είναι O (n²) συγκρίσεις και ανταλλαγές.

Πώς λειτουργεί η ταξινόμηση εισαγωγής;

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

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

Εφαρμογή Java τύπου εισαγωγής

PS - Προσπαθήστε να το εφαρμόσετε μόνοι σας πρώτα!

Συγχαρητήρια!!! Τώρα έχετε απορροφήσει τις βασικές αλλά ουσιαστικές γνώσεις σχετικά με τον τρόπο λειτουργίας του Insertion Sort.

Για αναφορά ή αναφορά ζητημάτων σχετικά με τον παραπάνω κώδικα, χρησιμοποιήστε τον ακόλουθο δημόσιο σύνδεσμο GitHub Gist.

Ελπίζω ότι αυτό ήταν χρήσιμο. Ευχαριστώ για την ανάγνωση! :)