2.5. Notasi Asimptotik
Notasi asimptotik digunakan untuk menentukan kompleksitas suatu algoritma dengan melihat waktu tempuh running time sebuah algoritma. Waktu tempuh algoritma merupakan fungsi : N → R suatu algoritma dengan algoritma lainnya. Notasi asimptotik dapat dituliskan dengan beberapa simbol, yaitu : Notasi Big O, yaitu notasi asimptotik sebuah fungsi algoritma untuk batas atas. Notasi Little o, yaitu notasi asimptotik sebuah fungsi algoritma untuk batas atas namun tidak secara ketat terikat not asymptotically tight. Notasi Theta , yaitu notasi asimptotik sebuah fungsi algoritma untuk batas atas dan bawah. Notasi Omega , yaitu notasi asimptotik sebuah fungsi algoritma untuk batas bawah, notasi ini berlawanan dengan notasi little-o.2.6. Pengertian Selection Sort
Selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection Sort Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukarSwap dan begitu seterusnyaTriono 2010. Dalam tesis ini penulis menambahkan 2 metode pengurutan data dengan selection sort yang baru, yaitu: 1. Selection Sort Model Insert 2. Selection Sort Model New List Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending menaik, elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending menurun, elemen yang paling besar yang disimpan indeksnya kemudian ditukar. Universitas Sumatera Utara Algoritma selection sort memilih elemen maksimumminimum array, lalu menempatkan elemen maksimumminimum itu pada awal atau akhir array tergantung pada urutannya ascending descending. Selanjutnya elemen tersebut tidak disertakan pada proses selanjutnya. Karena setiap kali selection sort harus membandingkan elemen-elemen data, algoritma ini termasuk dalam comparison-based sorting. Seperti pada algoritma Bubble Sort, proses memilih nilai maksimum minimum dilakukan pada setiap pass. Jika array berukuran N, maka jumlah pass adalah N-1 Nugroho 2005. Terdapat pendekatan dalam metode pengurutan dengan Selection Sort : 1. Algoritma pengurutan maksimum maximum selection sort, yaitu memilih elemen maksimum sebagai basis pengurutan. 2. Algoritma pengurutan minimum minimum selection sort, yaitu memilih elemen minimum sebagai basis pengurutan2.7. Pengertian Merge Sort
Selection Sort adalah perbaikan dari algoritma bubble sort, dengan mengurangi jumlah perbandingan. Dikatakan selection sort karena algoritma ini mencoba memilih satu per satu elemen data dari posisi awal, untuk mencari data paling kecil dengan mencatat posisi index-nya saja, lalu dilakukan pertukaran hanya sekali pada akhir setiap tahapan.
Berikut ini implementasi algoritma Selection Sort untuk melakukan pengurutan data integer secara ascending dalam bahasa pemrograman PHP dengan ketentuan data di-generate secara random dari sistem dan pada akhir program di tampilkan durasi waktu eksekusi (running time).
Berikut source code dalam bahasa pemrograman PHP :
<?php
//data di-generate secara random dari sistem for($x = 1; $x <= 1000; $x++) { $angka[] = rand(1, 100000); } //fungsi SelectionSort function SelectionSort($angka) { for($y = 0; $y < count($angka); $y++) { $min = $angka[$y];
$key = $y;
for($num = $y + 1; $num < count($angka); $num++) { if($angka[$num] < $min) { $min = $angka[$num]; $key = $num; } } $temporary = $angka[$y]; $angka[$y] = $min; $angka[$key] = $temporary; } var_dump($angka); } function MicrotimeFloat() { list($usec, $sec) = explode(" ", microtime()); return ((float)$usec + (float)$sec);
}
$waktu_mulai = MicrotimeFloat(); SelectionSort($angka); $waktu_selesai = MicrotimeFloat(); $waktu = $waktu_selesai - $waktu_mulai; //tampilkan durasi waktu eksekusi (running time)
echo "Durasi waktu eksekusi $waktu detik.";
?>
Sorting merupakan salah satu hal penting yang ada di dunia komputer, sorting sering kali kita manfaatkan untuk mempermudah mendapatkan informasi tertentu secara cepat, contoh gampangnya, ketika kita ingin mencari sebuah nama di dalam buku telpon, kita cenderung akan melihat huruf pertama dari nama yang ingin kita cari dan kita akan membuka halaman dari buku telpon yang merujuk ke halaman yang notabene-nya berisi kumpulan nama-nama yang diawali huruf tersebut. Hal tersebut bisa kita lakukan karna buku telpon tersebut sudah di sorting berdasarkan alfabet. Sorting merupakan hal yang penting di dalam pemrograman dan memilih teknik sorting yang benar merupakan hal yang sangat penting di dalam pemrograman. Ada banyak teknik sorting yang bisa kita gunakan, Sebagai permulaan, maka malam ini kita akan membahas selection sort.
Selection sort merupakan teknik sorting yang paling sederhana, hal pertama yang akan dilakukan algoritma selection sort adalah menemukan elemen terkecil dalam array kita dan menukarnya (swap) dengan elemen yang ada di posisi pertama, kemudian algoritma ini akan mengulangi hal yang sama lagi yaitu mencari elemen terkecil yang ada di dalam array dan kemudian menukarnya (swap) dengan elemen yang ada di posisi kedua (mengingat elemen di posisi pertama sudah berhasil kita sorting). Proses ini akan terus berlanjut sampai semua elemen yang ada di dalam array telah berhasil kita sorting.
Untuk mempermudah penjelasan mari kita lihat penggambaran dari prosesnya.
Algoritma:
Contoh penerapan menggunakan Golang: