Penyortiran adalah operasi dasar di mana elemen-elemen array diatur dalam beberapa urutan tertentu untuk meningkatkan kemampuan pencariannya. Dengan kata sederhana, data diurutkan sehingga dapat dengan mudah dicari.
Grafik perbandingan
| Dasar untuk perbandingan | Penyisipan Sortir | Sortir Pilihan |
|---|---|---|
| Dasar | Data diurutkan dengan memasukkan data ke dalam file yang diurutkan yang ada. | Data diurutkan dengan memilih dan menempatkan elemen berurutan di lokasi yang diurutkan. |
| Alam | Stabil | Tidak stabil |
| Proses yang harus diikuti | Elemen diketahui sebelumnya sementara lokasi untuk menempatkannya dicari. | Lokasi sebelumnya dikenal saat elemen dicari. |
| Data segera | Jenis penyisipan adalah teknik penyortiran langsung yang dapat menangani data langsung. | Itu tidak bisa berurusan dengan data langsung, perlu hadir di awal. |
| Kompleksitas kasus terbaik | Di) | O (n 2 ) |
Definisi Jenis Penyisipan
Sortasi penyisipan berfungsi dengan menyisipkan sekumpulan nilai dalam file yang diurutkan yang ada. Itu membangun array yang diurutkan dengan memasukkan satu elemen pada suatu waktu. Proses ini berlanjut sampai seluruh array diurutkan dalam beberapa urutan. Konsep utama di balik jenis penyisipan adalah untuk menyisipkan setiap item ke tempat yang sesuai di daftar akhir. Metode penyisipan menghemat jumlah memori yang efektif.
Bekerja dari jenis Penyisipan
- Ia menggunakan dua set array di mana satu menyimpan data yang diurutkan dan lainnya pada data yang tidak disortir.
- Algoritma pengurutan bekerja sampai ada elemen dalam set yang tidak disortir.
- Mari kita asumsikan ada elemen angka 'n' dalam array. Awalnya, elemen dengan indeks 0 (LB = 0) ada di set diurutkan. Elemen yang tersisa ada di partisi daftar yang tidak disortir.
- Elemen pertama dari bagian yang tidak disortir memiliki indeks array 1 (Jika LB = 0).
- Setelah setiap iterasi, ia memilih elemen pertama dari partisi yang tidak disortir dan memasukkannya ke tempat yang tepat di set diurutkan.
Keuntungan dari jenis Penyisipan
- Mudah diimplementasikan dan sangat efisien bila digunakan dengan set data kecil.
- Persyaratan ruang memori tambahan jenis penyisipan kurang (yaitu, O (1)).
- Ini dianggap sebagai teknik penyortiran langsung karena daftar dapat diurutkan saat elemen baru diterima.
- Ini lebih cepat daripada algoritma pengurutan lainnya.
Contoh:
Definisi Pilihan Seleksi
Sortir Seleksi melakukan penyortiran dengan mencari nomor nilai minimum dan menempatkannya di posisi pertama atau terakhir sesuai dengan pesanan (naik atau turun). Proses pencarian kunci minimum dan menempatkannya di posisi yang tepat dilanjutkan sampai semua elemen ditempatkan di posisi yang tepat.
Bekerja Seleksi Seleksi
- Misalkan array ARR dengan elemen N di memori.
- Pada pass pertama, kunci terkecil dicari bersama dengan posisinya kemudian ARR [POS] ditukar dengan ARR [0]. Karenanya, ARR [0] diurutkan.
- Pada lintasan kedua, sekali lagi posisi nilai terkecil ditentukan dalam subarray elemen N-1. Pertukarkan ARR [POS] dengan ARR [1].
- Dalam pass N-1, proses yang sama dilakukan untuk mengurutkan jumlah elemen N.
Contoh:
Perbedaan Kunci Antara Sortasi Penyisipan dan Pilihan Seleksi
- Jenis penyisipan biasanya melakukan operasi penyisipan. Sebaliknya, jenis seleksi melakukan pemilihan dan posisi elemen yang diperlukan.
- Jenis penyisipan dikatakan stabil sedangkan jenis pemilihan bukan algoritma yang stabil.
- Dalam algoritma penyisipan, elemen-elemen sebelumnya dikenal. Sebaliknya, jenis seleksi berisi lokasi sebelumnya.
- Jenis penyisipan adalah teknik penyortiran langsung di mana elemen yang tiba segera diurutkan dalam daftar sedangkan jenis seleksi tidak dapat bekerja dengan baik dengan data langsung.
- Jenis sisipan memiliki O (n) waktu berjalan dalam kasus terbaik. Sebagai lawan, kompleksitas run time case terbaik dari jenis seleksi adalah O (n2).
Kompleksitas jenis Penyisipan
Kompleksitas kasus terbaik dari jenis penyisipan adalah O (n) kali, yaitu ketika array sebelumnya diurutkan. Dengan cara yang sama, ketika array diurutkan dalam urutan terbalik, elemen pertama dari array yang tidak disortir harus dibandingkan dengan setiap elemen dalam set yang diurutkan. Jadi, dalam kasus terburuk, waktu berjalan dari jenis Penyisipan adalah kuadrat, yaitu, O (n2) . Dalam kasus rata-rata juga harus membuat perbandingan minimum (k-1) / 2. Oleh karena itu, kasus rata-rata juga memiliki waktu berjalan kuadrat O (n2).
Kompleksitas Sortir Seleksi
Sebagai cara kerja seleksi, sort tidak bergantung pada urutan asli elemen dalam array, sehingga tidak ada banyak perbedaan antara kompleksitas case terbaik dan terburuk dari sort sort.
Sortir seleksi memilih elemen nilai minimum, dalam proses pemilihan semua jumlah elemen 'n' dipindai; oleh karena itu perbandingan n-1 dibuat pada lintasan pertama. Kemudian, elemen-elemen tersebut dipertukarkan. Demikian pula pada lintasan kedua juga untuk menemukan elemen terkecil kedua kita memerlukan pemindaian elemen n-1 sisanya dan proses dilanjutkan hingga seluruh array diurutkan.
Dengan demikian, kompleksitas waktu berjalan dari jenis seleksi adalah O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
Kesimpulan
Di antara kedua algoritma pengurutan, jenis penyisipan cepat, efisien, stabil, sementara pemilihan hanya berfungsi secara efisien ketika sejumlah kecil elemen terlibat atau daftar sebelumnya diurutkan sebagian. Jumlah perbandingan yang dibuat oleh sort seleksi lebih besar dari gerakan yang dilakukan sedangkan pada insert insertion berapa kali elemen dipindahkan atau ditukar lebih besar dari perbandingan yang dibuat.
