Struktur Data - Teknik Penyortiran
Pengurutan mengacu pada pengaturan data dalam format tertentu. Algoritme pengurutan menentukan cara untuk mengatur data dalam urutan tertentu. Urutan paling umum dalam urutan numerik atau leksikografis.
Pentingnya pengurutan terletak pada kenyataan bahwa pencarian data dapat dioptimalkan ke tingkat yang sangat tinggi, jika data disimpan dengan cara yang diurutkan. Pengurutan juga digunakan untuk merepresentasikan data dalam format yang lebih mudah dibaca. Berikut adalah beberapa contoh pengurutan dalam skenario kehidupan nyata -
Telephone Directory - Direktori telepon menyimpan nomor telepon orang yang diurutkan berdasarkan namanya, sehingga nama tersebut dapat dicari dengan mudah.
Dictionary - Kamus menyimpan kata-kata dalam urutan abjad sehingga pencarian kata apapun menjadi mudah.
Penyortiran Di Tempat dan Penyortiran Tidak Di Tempat
Algoritme pengurutan mungkin memerlukan beberapa ruang ekstra untuk perbandingan dan penyimpanan sementara dari beberapa elemen data. Algoritme ini tidak memerlukan ruang ekstra dan penyortiran dikatakan terjadi di tempat, atau misalnya, di dalam larik itu sendiri. Ini disebutin-place sorting. Jenis gelembung adalah contoh pengurutan di tempat.
Namun, dalam beberapa algoritma pengurutan, program membutuhkan ruang yang lebih dari atau sama dengan elemen yang diurutkan. Penyortiran yang menggunakan ruang yang sama atau lebih disebutnot-in-place sorting. Merge-sort adalah contoh pengurutan tidak di tempat.
Penyortiran Stabil dan Tidak Stabil
Jika algoritme pengurutan, setelah menyortir konten, tidak mengubah urutan konten serupa di mana mereka muncul, hal itu disebut stable sorting.
Jika algoritma pengurutan, setelah menyortir konten, mengubah urutan konten serupa di mana mereka muncul, itu disebut unstable sorting.
Stabilitas algoritme penting ketika kita ingin mempertahankan urutan elemen asli, seperti dalam tupel misalnya.
Algoritma Penyortiran Adaptif dan Non-Adaptif
Algoritme pengurutan dikatakan adaptif, jika memanfaatkan elemen yang sudah 'diurutkan' dalam daftar yang akan disortir. Artinya, saat menyortir jika daftar sumber memiliki beberapa elemen yang telah diurutkan, algoritme adaptif akan mempertimbangkannya dan akan mencoba untuk tidak mengurutkan ulang.
Algoritme non-adaptif adalah algoritme yang tidak memperhitungkan elemen yang sudah disortir. Mereka mencoba memaksa setiap elemen untuk diatur ulang untuk mengkonfirmasi urutannya.
Istilah Penting
Beberapa istilah umumnya diciptakan saat membahas teknik pengurutan, berikut adalah pengantar singkat untuk mereka -
Meningkatkan Ketertiban
Urutan nilai dikatakan masuk increasing order, jika elemen yang berurutan lebih besar dari yang sebelumnya. Misalnya, 1, 3, 4, 6, 8, 9 berada dalam urutan meningkat, karena setiap elemen berikutnya lebih besar dari elemen sebelumnya.
Penurunan Pesanan
Urutan nilai dikatakan masuk decreasing order, jika elemen yang berurutan lebih kecil dari yang sekarang. Misalnya, 9, 8, 6, 4, 3, 1 berada dalam urutan menurun, karena setiap elemen berikutnya lebih kecil dari elemen sebelumnya.
Pesanan Tidak Meningkat
Urutan nilai dikatakan masuk non-increasing order, jika elemen berurutan kurang dari atau sama dengan elemen sebelumnya dalam urutan tersebut. Urutan ini terjadi ketika urutan berisi nilai duplikat. Misalnya, 9, 8, 6, 3, 3, 1 berada dalam urutan tidak bertambah, karena setiap elemen berikutnya kurang dari atau sama dengan (dalam kasus 3) tetapi tidak lebih besar dari elemen sebelumnya.
Pesanan Tidak Menurun
Urutan nilai dikatakan masuk non-decreasing order, jika elemen berurutan lebih besar dari atau sama dengan elemen sebelumnya dalam urutan tersebut. Urutan ini terjadi ketika urutan berisi nilai duplikat. Misalnya, 1, 3, 3, 6, 8, 9 berada dalam urutan tidak menurun, karena setiap elemen berikutnya lebih besar dari atau sama dengan (dalam kasus 3) tetapi tidak kurang dari yang sebelumnya.