Dalam tutorial ini, Anda akan mempelajari cara kerja sortasi seleksi. Selain itu, Anda akan menemukan contoh kerja dari sortir seleksi dalam C, C ++, Java dan Python.
Sortir pilihan adalah algoritme yang memilih elemen terkecil dari daftar yang tidak diurutkan di setiap iterasi dan menempatkan elemen itu di awal daftar yang tidak diurutkan.
Bagaimana Cara Kerja Sortir Seleksi?
- Tetapkan elemen pertama sebagai
minimum.
Pilih elemen pertama sebagai minimum - Bandingkan
minimumdengan elemen kedua. Jika elemen kedua lebih kecil dariminimum, tetapkan elemen kedua sebagaiminimum.
Bandingkanminimumdengan elemen ketiga. Sekali lagi, jika elemen ketiga lebih kecil, maka tetapkanminimumke elemen ketiga jika tidak, jangan lakukan apa pun. Prosesnya berlangsung hingga elemen terakhir.
Bandingkan minimal dengan elemen yang tersisa - Setelah setiap iterasi,
minimumditempatkan di depan daftar yang tidak diurutkan.
Tukar yang pertama dengan minimum - Untuk setiap iterasi, pengindeksan dimulai dari elemen pertama yang tidak disortir. Langkah 1 sampai 3 diulangi sampai semua elemen ditempatkan pada posisi yang benar.
Iterasi pertama Iterasi 
kedua Iterasi 
ketiga Iterasi 
keempat
Algoritma Pengurutan Pilihan
selectionSort (larik, ukuran) ulangi (ukuran - 1) kali setel elemen pertama yang tidak diurutkan sebagai minimum untuk setiap elemen yang tidak diurutkan jika elemen <currentMinimum set element sebagai minimum swap minimum baru dengan posisi tidak diurutkan pertama akhir selectionSort
Contoh Python, Java dan C / C ++
Python Java 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); )
Kompleksitas
| Siklus | Jumlah Perbandingan |
|---|---|
| 1st | (n-1) |
| 2nd | (n-2) |
| 3 | (n-3) |
| … | … |
| terakhir | 1 |
Jumlah perbandingan: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2hampir sama dengan .n2
Kompleksitas =O(n2)
Juga, kita dapat menganalisis kompleksitas hanya dengan mengamati jumlah loop. Ada 2 loop jadi kerumitannya .n*n = n2
Kompleksitas Waktu:
- Kompleksitas Kasus Terburuk: Jika kita ingin mengurutkan dalam urutan naik dan array dalam urutan turun, kasus terburuk terjadi.
O(n2) - Kompleksitas Kasus Terbaik: Ini terjadi ketika array sudah diurutkan
O(n2) - Average Case Complexity: Ini terjadi ketika elemen-elemen array berada dalam urutan campur aduk (tidak naik atau turun).
O(n2)
Kompleksitas waktu dari pengurutan pilihan sama di semua kasus. Di setiap langkah, Anda harus menemukan elemen minimum dan meletakkannya di tempat yang tepat. Elemen minimum tidak diketahui hingga akhir larik tidak tercapai.
Kompleksitas Ruang:
Kompleksitas ruang O(1)karena variabel tambahan tempdigunakan.
Pilihan Sortir Aplikasi
Jenis pilihan digunakan ketika:
- daftar kecil harus disortir
- biaya swapping tidak masalah
- pemeriksaan semua elemen adalah wajib
- biaya penulisan ke memori penting seperti dalam memori flash (jumlah tulis / swap
O(n)dibandingkan dengan jenis gelembung)O(n2)
