Επιλογή Ταξινόμηση σε Java Πρόγραμμα με Παράδειγμα

⚡ Έξυπνη Σύνοψη

Ταξινόμηση επιλογής Java σαρώνει επανειλημμένα το μη ταξινομημένο μέρος ενός πίνακα, βρίσκει τη μικρότερη εναπομένουσα τιμή και την αντικαθιστά στη θέση της, ολοκληρώνοντας την εργασία με το πολύ n-1 ανταλλαγές ανεξάρτητα από τη σειρά εισόδου.

  • 🔘 Ορισμός: Η ταξινόμηση με επιλογή διαιρεί τον πίνακα σε μια ταξινομημένη περιοχή και μια μη ταξινομημένη περιοχή σε κάθε πέρασμα.
  • ☑️ Διαδικασία: Κάθε πέρασμα αναζητά την μη ταξινομημένη περιοχή για το χαμηλότερο στοιχείο και το μετακινεί προς τα εμπρός.
  • ✅ Πρόγραμμα: The Java Το παράδειγμα ταξινομεί {860, 8, 200, 9} και εκτυπώνει κάθε σύγκριση και εναλλαγή.
  • 🧪 Περίπλοκο: Οι καλύτερες, οι μέσες και οι χειρότερες περιπτώσεις εκτελούνται όλες σε χρόνο O(n²) επειδή ο αριθμός των συγκρίσεων δεν συρρικνώνεται ποτέ.
  • ️ Μνήμη: Οι ανταλλαγές συμβαίνουν μέσα στον αρχικό πίνακα, επομένως ο βοηθητικός χώρος παραμένει στο O(1).
  • 📊 Η ΣΥΜΠΕΡΙΦΟΡΑ: Η κλασική έκδοση είναι ασταθής, ωστόσο εκτελεί τις λιγότερες εγγραφές από οποιαδήποτε τετραγωνική μορφή.

Επιλογή Ταξινόμηση σε Java Πρόγραμμα με Παράδειγμα

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

Το Selection Sort υλοποιεί έναν απλό αλγόριθμο ταξινόμησης ως εξής:

  • Ο αλγόριθμος αναζητά επανειλημμένα το χαμηλότερο στοιχείο.
  • Αντικαταστήστε το τρέχον στοιχείο με ένα στοιχείο που έχει τη χαμηλότερη τιμή
  • Με κάθε επανάληψη/πέρασμα επιλογής ταξινόμησης, τα στοιχεία ανταλλάσσονται.

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

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

The tracΤο παρακάτω ακολουθεί τον πίνακα δειγμάτων {860, 8, 200, 9} ακριβώς όπως τον τυπώνει το πρόγραμμα στην επόμενη ενότητα κατά τον χρόνο εκτέλεσης.

Πέρασμα Συγκρίσεις που εκτυπώνονται Βρέθηκε η μικρότερη τιμή Πίνακας μετά την εναλλαγή
Αρχική - - 860 8 200 9
1 860 και 8, 8 και 200, 8 και 9 8 8 860 200 9
2 860 και 200, 200 και 9 9 8 9 200 860
3 200 και 860 200 8 9 200 860

Δύο λεπτομέρειες σε αυτό tracΑξίζει να σταματήσουμε. Πρώτον, το πέρασμα 3 εξακολουθεί να αναφέρει μια εναλλαγή παρόλο που η σειρά δεν αλλάζει, επειδή η μικρότερη εναπομένουσα τιμή βρίσκεται ήδη στον τρέχοντα δείκτη και το πρόγραμμα ανταλλάσσει το στοιχείο με τον εαυτό του. Δεύτερον, ο αριθμός των συγκρίσεων μειώνεται κατά μία σε κάθε πέρασμα (τρεις, μετά δύο, μετά μία), το οποίο είναι το μοτίβο πίσω από τους αριθμούς πολυπλοκότητας παρακάτω στη σελίδα.

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

Η παρακάτω κλάση ονομάζεται SelectionSortAlgo και βρίσκεται στο πακέτο com.guru99. Η μέθοδος main() δηλώνει τον πίνακα-δείγμα, τον εκτυπώνει, τον παραδίδει στην selection() για ταξινόμηση και τον εκτυπώνει ξανά. Η βοηθητική printArray() γράφει όλα τα στοιχεία σε μία μόνο γραμμή, η οποία παράγει το αναγνώσιμο αρχείο καταγραφής pass-by-pass.

Μέσα στην selection(), ο εξωτερικός βρόχος σηματοδοτεί το όριο μεταξύ των ταξινομημένων και των μη ταξινομημένων περιοχών, η μεταβλητή index κρατά τη θέση της μικρότερης τιμής που έχει παρατηρηθεί μέχρι στιγμής και οι τρεις αναθέσεις στο τέλος κάθε περάσματος εκτελούν την εναλλαγή.

package com.guru99;
 
public class SelectionSortAlgo {
 
	public static void main(String a[])
	{  
		int[] myArray = {860,8,200,9}; 
		
		System.out.println("------Before Selection Sort-----");
 
		printArray(myArray);
 
 
		selection(myArray);//sorting array using selection sort  
 
		System.out.println("-----After Selection Sort-----");  
 
		printArray(myArray); 
	} 
	
		public static void selection(int[] array)
	{  
		for (int i = 0; i < array.length - 1; i++)  
		{  System.out.println("Sort Pass Number "+(i+1));
			int index = i;  
			for (int j = i + 1; j < array.length; j++)
			{   
			    System.out.println("Comparing "+ array[index]  + " and " + array[j]);  
				if (array[j] < array[index]){ 
				System.out.println(array[index]  + " is greater than " + array[j] );
					index = j;
				
				
				}  
			}  
 
			int smallerNumber = array[index];   
			array[index] = array[i];  
			array[i] = smallerNumber;  
			System.out.println("Swapping Elements: New Array After Swap");
			printArray(array);
		}  
	}  
	static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
 
}

Παραγωγή:

Η μεταγλώττιση και η εκτέλεση της κλάσης παράγει το παρακάτω αρχείο καταγραφής κονσόλας, με ένα μπλοκ εξόδου ανά πέρασμα.

------Before Selection Sort-----
860 8 200 9 
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Comparing 8 and 200
Comparing 8 and 9
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 860 and 200
860 is greater than 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860 
Sort Pass Number 3
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 9 200 860 
-----After Selection Sort-----
8 9 200 860

Δύο προβλήματα παγιδεύουν τους αρχάριους όταν εκτελούν αυτό το παράδειγμα για πρώτη φορά. Επειδή το αρχείο δηλώνει package com.guru99;, η πηγή πρέπει να βρίσκεται σε ένα αντίστοιχο com/guru99 κατάλογο, διαφορετικά ο μεταγλωττιστής αναφέρει μια αναντιστοιχία ονόματος πακέτου ή κλάσης. Η κλάση πρέπει στη συνέχεια να ξεκινήσει με το πλήρως προσδιορισμένο όνομά της, java com.guru99.SelectionSortAlgo, επειδή απλό java SelectionSortAlgo προκαλεί το σφάλμα NoClassDefFoundError.

Τα όρια του βρόχου είναι η άλλη συνηθισμένη παγίδα. Ο εξωτερικός βρόχος σταματά στο array.length - 1 και ο εσωτερικός βρόχος ξεκινά από i + 1Η αλλαγή οποιουδήποτε ορίου παράγει ένα επιπλέον κενό πέρασμα ή ένα ArrayIndexOutOfBoundsException.

Χρονική και χωρική πολυπλοκότητα της ταξινόμησης επιλογής

Ο εσωτερικός βρόχος στο πρόγραμμα εκτελείται πάντα μέχρι το τέλος του πίνακα, επομένως ο αλγόριθμος εκτελεί τον ίδιο αριθμό συγκρίσεων ανεξάρτητα από την εμφάνιση των δεδομένων. Για έναν πίνακα n στοιχείων, το σύνολο είναι n(n-1)/2, το οποίο για το δείγμα τεσσάρων στοιχείων ισούται με έξι, και η παραπάνω έξοδος πράγματι εκτυπώνει ακριβώς έξι γραμμές σύγκρισης.

Περίπτωση Συγκρίσεις Ανταλλαγές Χρονική πολυπλοκότητα Βοηθητικός χώρος
καλυτερα (ο πίνακας έχει ήδη ταξινομηθεί) n(n-1)/2 n-1 O(n²) Ο (1)
Μέσος όρος (τυχαία σειρά) n(n-1)/2 n-1 O(n²) Ο (1)
Χειρότερη (αντίστροφη ταξινόμηση) n(n-1)/2 n-1 O(n²) Ο (1)

Τρεις συνέπειες προκύπτουν από αυτή την ομοιόμορφη σειρά αριθμών:

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

Η τετραγωνική αύξηση είναι το πρακτικό όριο. Ο διπλασιασμός του μεγέθους του πίνακα τετραπλασιάζει περίπου το έργο σύγκρισης, επομένως η ταξινόμηση με επιλογή είναι κατάλληλη για διδασκαλία, μικρούς πίνακες και ενσωματωμένο κώδικα αντί για σύνολα δεδομένων παραγωγής, όπου οι αλγόριθμοι O(n log n) είναι η σωστή επιλογή.

Πλεονεκτήματα και μειονεκτήματα της ταξινόμησης επιλογής

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

Πλεονεκτήματα

  • Η λογική είναι σύντομη και ευανάγνωστη, γι' αυτό και αποτελεί μια τυπική άσκηση πρώτης ταξινόμησης παράλληλα με είδος εισαγωγής.
  • Ταξινομείται επιτόπου, επομένως δεν εκχωρείται δεύτερος πίνακας και η χρήση μνήμης δεν αυξάνεται με την είσοδο.
  • Εκτελεί το πολύ n-1 εγγραφές στον πίνακα, κάτι που έχει σημασία στην αποθήκευση όπου οι εγγραφές είναι αργές ή φθείρουν το μέσο.
  • Ο χρόνος εκτέλεσης είναι απολύτως προβλέψιμος, επειδή ο αριθμός συγκρίσεων εξαρτάται μόνο από το μήκος του πίνακα.

Μειονεκτήματα

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

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

Ταξινόμηση επιλογής έναντι BubblΤαξινόμηση μέσω ηλεκτρονικού ταχυδρομείου έναντι ταξινόμησης με εισαγωγή

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

Κριτήριο Ταξινόμηση επιλογής Bubblηλεκτρονική ταξινόμηση Ταξινόμηση εισαγωγής
χρόνος καλυτέρας-περίπτωσης O(n²) O (n) O (n)
Μέσος και χειρότερος χρόνος O(n²) O(n²) O(n²)
Ανταλλαγές ή μετατοπίσεις στη χειρότερη περίπτωση n-1 ανταλλαγές n(n-1)/2 ανταλλαγές Έως n(n-1)/2 βάρδιες
Σταθερός Οχι Ναι Ναι
Προσαρμόζεται στην ταξινομημένη εισαγωγή Οχι Ναι Ναι
Βοηθητικός χώρος Ο (1) Ο (1) Ο (1)
Τυπική χρήση Απαιτούνται λιγότερες εγγραφές Διδασκαλία και εντοπισμός ταξινομημένων δεδομένων Μικροί ή σχεδόν ταξινομημένοι πίνακες

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

Συχνές Ερωτήσεις

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

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

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

Η έκδοση που εμφανίζεται εδώ είναι ασταθής, επειδή μια ανταλλαγή μεγάλων αποστάσεων μπορεί να μεταπηδήσει μια ίση τιμή πάνω από μια άλλη. Shifting το μπλοκ στοιχείων αντί για swapping διατηρεί την αρχική σειρά των ίσων κλειδιών, με κόστος επιπλέον εγγραφές.

Reverse η σύγκριση μέσα στον εσωτερικό βρόχο. Έλεγχος εάν ο πίνακας[j] είναι μεγαλύτερος από τον πίνακα[index] tracks η μεγαλύτερη εναπομένουσα τιμή, έτσι ώστε κάθε πέρασμα να μετακινεί το μέγιστο προς τα εμπρός και ο τελικός πίνακας να εκτελείται από υψηλή προς χαμηλή.

Ναι. Μια αναδρομική μέθοδος βρίσκει το ελάχιστο του τρέχοντος υποπίνακα, το αντικαθιστά με το μπροστινό μέρος και, στη συνέχεια, καλεί τον εαυτό της στο υπόλοιπο. Ο αριθμός σύγκρισης παραμένει αμετάβλητος, αλλά η στοίβα κλήσεων προσθέτει χώρο O(n), επομένως προτιμάται η μορφή βρόχου.

Τα συχνά σφάλματα είναι η παράλειψη επαναφοράς του δείκτη στο i στην αρχή κάθε περάσματος, η έναρξη του εσωτερικού βρόχου στο i αντί για i + 1, και η εναλλαγή.ping array[j] αντί για array[index], το οποίο χάνει track της μικρότερης τιμής.

Όχι. Η συνάρτηση Arrays.sort() εφαρμόζει μια γρήγορη ταξινόμηση διπλού άξονα σε πρωτόγονα στοιχεία και μια ταξινόμηση TimSort σε αντικείμενα, με ταξινόμηση τύπου εισαγωγής σε μικροσκοπικά διαμερίσματα. Η ταξινόμηση με επιλογή εμφανίζεται σε διδακτικό υλικό και χειρόγραφο κώδικα αντί για την τυπική βιβλιοθήκη.

Συνοψίστε αυτήν την ανάρτηση με: