Seleksi Menyortir Java Program dengan Contoh

Bagaimana cara kerja Pengurutan Seleksi?

Pengurutan Seleksi mengimplementasikan algoritma pengurutan sederhana sebagai berikut:

• Algoritma berulang kali mencari elemen terendah.
• Tukar elemen saat ini dengan elemen yang memiliki nilai terendah
• Dengan setiap iterasi/lulus dari jenis seleksi, elemen ditukar.

Oleh karena itu, setiap operan memperlakukan susunan sebagai dua wilayah: blok terurut yang tumbuh dari kiri dan blok tidak terurut yang menyusut di sebelah kanan. Algoritma ini menelusuri blok tidak terurut, mengingat indeks nilai terkecil yang ditemuinya, dan menukar nilai tersebut dengan posisi tidak terurut pertama.

Karena hanya terjadi satu pertukaran per putaran, sebuah array berisi n elemen akan diurutkan setelah paling banyak n-1 pertukaran. Sifat inilah yang membedakan rutinitas ini dari rutinitas tingkat pemula lainnya. Java algoritma pengurutan, yang memindahkan data jauh lebih sering.

The tracContoh di bawah ini mengikuti array sampel {860, 8, 200, 9} persis seperti yang dicetak oleh program di bagian selanjutnya saat dijalankan.

Dua detail dalam hal itu tracAda beberapa hal yang perlu diperhatikan. Pertama, pada pass 3 masih dilaporkan terjadi pertukaran meskipun urutannya tidak berubah, karena nilai terkecil yang tersisa sudah berada di indeks saat ini dan program menukar elemen tersebut dengan dirinya sendiri. Kedua, jumlah perbandingan berkurang satu pada setiap pass (tiga, kemudian dua, lalu satu), yang merupakan pola di balik angka kompleksitas di bagian bawah halaman ini.

Java Program untuk mengimplementasikan Seleksi Seleksi

Kelas di bawah ini bernama SelectionSortAlgo dan berada di dalam paket com.guru99. Metode main() mendeklarasikan array sampel, mencetaknya, menyerahkannya ke selection() untuk diurutkan, dan mencetaknya lagi. Fungsi bantu printArray() menulis semua elemen pada satu baris, yang menghasilkan log langkah demi langkah yang mudah dibaca.

Di dalam fungsi selection(), loop terluar menandai batas antara wilayah yang sudah diurutkan dan yang belum diurutkan, variabel index menyimpan posisi nilai terkecil yang telah dilihat sejauh ini, dan tiga penugasan di akhir setiap proses melakukan pertukaran.

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();
	    
	}
 
}

Keluaran:

Mengkompilasi dan menjalankan kelas tersebut menghasilkan log konsol di bawah ini, dengan satu blok keluaran per proses.

------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

Dua masalah yang sering menjebak pemula saat menjalankan contoh ini untuk pertama kalinya. Karena file tersebut mendeklarasikan package com.guru99;, sumbernya harus berada di tempat yang sesuai com/guru99 direktori, jika tidak, kompiler akan melaporkan ketidakcocokan nama paket atau kelas. Kelas tersebut kemudian harus dijalankan dengan nama lengkapnya, java com.guru99.SelectionSortAlgo, karena polos java SelectionSortAlgo Menimbulkan NoClassDefFoundError.

Batas loop adalah jebakan umum lainnya. Loop terluar berhenti di array.length - 1 dan lingkaran dalam dimulai pada i + 1; mengubah salah satu batas akan menghasilkan proses kosong tambahan atau ArrayIndexOutOfBoundsException.

Kompleksitas Waktu dan Ruang dari Pengurutan Seleksi

Loop dalam program selalu berjalan hingga akhir array, sehingga algoritma melakukan jumlah perbandingan yang sama terlepas dari bentuk datanya. Untuk array dengan n elemen, totalnya adalah n(n-1)/2, yang untuk sampel empat elemen sama dengan enam, dan output di atas memang mencetak tepat enam baris "Comparing".

Tiga konsekuensi berikut muncul dari deretan angka yang seragam tersebut:

• Algoritma pengurutan seleksi tidak adaptif. Input yang diurutkan membutuhkan biaya yang sama persis dengan input yang dibalik, sehingga tidak ada jalan pintas keluar lebih awal seperti yang diharapkan. semacam gelembung menawarkan.
• Jumlah pertukaran adalah keunggulan utama algoritma ini. Paling banyak hanya terjadi n-1 pertukaran, yang jauh lebih sedikit daripada jumlah pergerakan kuadratik yang dapat dilakukan oleh pengurutan sederhana lainnya.
• Penggunaan memori bersifat konstan. Hanya penghitung loop dan dua variabel sementara index dan smallerNumber yang dibutuhkan, sehingga ruang tambahan adalah O(1) dan pengurutan terjadi di tempat.

Pertumbuhan kuadratik adalah batas praktisnya. Menggandakan ukuran array kira-kira melipatgandakan pekerjaan perbandingan, sehingga pengurutan seleksi lebih cocok untuk pengajaran, array kecil, dan kode tertanam daripada kumpulan data produksi, di mana algoritma O(n log n) adalah pilihan yang tepat.

Keuntungan dan Kerugian dari Metode Pengurutan Seleksi

Memahami di mana algoritma membantu dan di mana ia merugikan akan memudahkan pengambilan keputusan kapan penggunaan algoritma tersebut tepat.

Kelebihan

• Logikanya singkat dan mudah dibaca, itulah sebabnya ini menjadi latihan pengurutan pertama yang standar. jenis penyisipan.
• Algoritma ini melakukan pengurutan di tempat, sehingga tidak ada array kedua yang dialokasikan dan penggunaan memori tidak bertambah seiring dengan input.
• Ia melakukan paling banyak n-1 penulisan ke array, yang penting pada penyimpanan di mana penulisan lambat atau menyebabkan keausan media.
• Waktu eksekusinya sepenuhnya dapat diprediksi, karena jumlah perbandingan hanya bergantung pada panjang array.

Kekurangan

• Setiap kasus memiliki kompleksitas O(n²), sehingga algoritma ini tidak dapat diterapkan pada koleksi data yang besar.
• Ia tidak dapat mendeteksi array yang sudah diurutkan dan oleh karena itu tidak pernah selesai lebih awal.
• Bentuk klasik yang ditunjukkan di atas tidak stabil, sehingga dua nilai yang sama mungkin akan berakhir dalam urutan yang berlawanan.
• Algoritma ini membandingkan data lebih sering daripada insertion sort pada data yang hampir terurut, di mana insertion sort mendekati waktu linear.

Singkatnya, pilih pengurutan seleksi (selection sort) ketika array berukuran kecil dan setiap penulisan memakan biaya yang besar, dan hindari pengurutan seleksi ketika kumpulan data berukuran besar atau sudah hampir terurut.

Pengurutan Seleksi vs. Bubble Sort vs Insertion Sort

Ketiga algoritma tersebut merupakan pengurutan perbandingan kuadratik di tempat, namun perilakunya berbeda begitu bentuk input berubah.

Tabel tersebut menjelaskan jawaban umum dalam wawancara. Selection sort unggul dalam jumlah pertukaran, bubble sort unggul dalam mengenali input yang sudah terurut, dan insertion sort biasanya yang tercepat dari ketiganya dalam praktiknya karena data sebenarnya sering kali sebagian sudah terurut. Tak satu pun dari mereka dapat menyaingi merge sort atau quicksort setelah array bertambah melebihi beberapa lusin elemen.

Pertanyaan Umum Demo Slot