Dalam tutorial ini, anda akan belajar bagaimana kaedah pemilihan berfungsi. Anda juga akan mendapat contoh contoh pilihan dalam C, C ++, Java dan Python.
Jenis pemilihan adalah algoritma yang memilih elemen terkecil dari senarai yang tidak disusun dalam setiap lelaran dan meletakkan elemen itu pada permulaan senarai yang tidak disusun.
Bagaimana Urutan Pemilihan Berfungsi?
- Tetapkan elemen pertama sebagai
minimum.
Pilih elemen pertama sebagai minimum - Bandingkan
minimumdengan elemen kedua. Sekiranya elemen kedua lebih kecil daripadaminimum, tetapkan elemen kedua sebagaiminimum.
Bandingkanminimumdengan elemen ketiga. Sekali lagi, jika elemen ketiga lebih kecil, tetapkanminimumelemen ketiga jika tidak, jangan buat apa-apa. Prosesnya berterusan sehingga elemen terakhir.
Bandingkan minimum dengan unsur-unsur yang tinggal - Selepas setiap lelaran,
minimumdiletakkan di bahagian depan senarai yang tidak disusun.
Tukar yang pertama dengan minimum - Untuk setiap lelaran, pengindeksan bermula dari elemen yang tidak disusun pertama. Langkah 1 hingga 3 diulang sehingga semua elemen diletakkan pada kedudukan yang betul.
Iterasi pertama Iterasi 
kedua lelaran 
ketiga lelaran 
keempat
Algoritma Pemilihan Pilihan
Seleksi (susunan, ukuran) ulangi (ukuran - 1) kali tetapkan elemen yang tidak disusun pertama sebagai minimum untuk setiap elemen yang tidak disusun jika elemen <currentMinimum set element sebagai minimum swap minimum baru dengan pemilihan akhir kedudukan yang tidak disusun
Contoh Python, Java dan C / C ++
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Kerumitan
| Kitaran | Bilangan Perbandingan |
|---|---|
| 1hb | (n-1) |
| Ke-2 | (n-2) |
| Ke-3 | (n-3) |
| … | … |
| terakhir | 1 |
Bilangan perbandingan: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2hampir sama dengan .n2
Kerumitan =O(n2)
Kita juga dapat menganalisis kerumitan dengan hanya memerhatikan bilangan gelung. Terdapat 2 gelung sehingga kerumitannya .n*n = n2
Kerumitan Masa:
- Kerumitan Kes Terburuk: Sekiranya kita mahu menyusun mengikut tertib menaik dan susunannya berada dalam urutan menurun maka, kes terburuk berlaku.
O(n2) - Kerumitan Kes Terbaik: Ia berlaku apabila array sudah disusun
O(n2) - Kerumitan Kes Rata-rata: Ia berlaku apabila unsur-unsur array berada dalam urutan yang tidak rata (tidak menaik atau menurun)
O(n2)
Kerumitan masa jenis pemilihan adalah sama dalam semua kes. Pada setiap langkah, anda mesti mencari elemen minimum dan meletakkannya di tempat yang betul. Elemen minimum tidak diketahui sehingga akhir array tidak tercapai.
Kerumitan Ruang:
Kerumitan ruang O(1)kerana pemboleh ubah tambahan tempdigunakan.
Aplikasi Susun Pilihan
Jenis pemilihan digunakan apabila:
- senarai kecil hendak disusun
- kos pertukaran tidak menjadi masalah
- memeriksa semua elemen adalah wajib
- kos penulisan ke memori penting seperti dalam memori kilat (bilangan penulisan / pertukaran
O(n)berbanding dengan jenis gelembung)O(n2)
