pengertian sorting . tugas sistem informasi Universitas Teknologi Yogyakarta

Pengertian Sorting·        sorting

Pengurutan adalah sebuah algoritma dasar yang sering diperlukan dalam pembuatan program. Berbagai algoritma pengurutan telah diciptakan dan dapat digunakan. Pemahaman tentang beberapa algoritma pengurutan dasar perlu diketahui, termasuk cara penggunaannya dalam program.

Sorting merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.

Dalam Ilmu Komputer, Algoritma Sorting merupakan algoritma yang menempatkan elemen list pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical. Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini:

1.       Output merupakan urutan yang tidak menurut (nondecreasing) (setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan.

2.       Output merupakan permutasi (pengurutan kembali) dari inputan yang diberikan.

Sejak permulaan komputasi, masalah pengurutan ini telah menarik penelitian yang serius, mungkin dikarenakan kerumitan dari penyelesaian secara efisien disamping mudah, dan dengan statemen yang kita mengerti. Sebagai contoh, bubble sort pertama sekali ditemukan pada tahun 1956. Walaupun banyak yang memperkirakan masalahnya telah terselesaikan, banyak algoritma sorting baru yang masih ditemukan samap sekarang (sebagai contoh, Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006). Algoritma sorting sangat umum pada setiap kelas pengenalan bidang Ilmu Komputer, dimana banyaknya algoritma untuk masalah ini menyediakan pengenalan awal mengenai banyaknya konsep algoritma inti, seperti Notasi Big O, Algoritma Pembagi, Struktur Data, Algoritma Acak, Analisa Best, Worst, Average Case, Running Time Calculation, dan Batas Atas dan Bawah.

Algoritma sorting digunakan pada Ilmu Komputer sering diklasifikasikan dengan:

·         Kompleksitas Komputasi (Average, Best, Worst case) perbandingan elemen dengan besar list(n). Untuk beberapa Algoritma sorting kasus yang paling baiknya ialah O(n log n) dan kasus terburuknya ialah O(n²). Kasus ideal untuk masalah sorting ialah O(n), tetapi ini tidak mungkin terjadi pada average case. Sequential Sort, yang menaksir elemen dari list dari operasi perbandingan indeks abstrak, yang membutuhkan paling kurang perbandingan O(n log n) untuk paling banyak input.

·         Penukaran Kompleksitas Komputasi (untuk Algoritma "In Place")/

·         Penggunaan memori (dan menggunakan sumber daya komputer) khususnya, beberapa algoritma sorting ialah Algoritma In Place. Dengan sorting in place membutuhkan hanya O(1) memori lebih tinggi dari item yang sedang diurut; kadang-kadang memori tambahan O(log(n)) dianggap "in place"

·         Rekursif. Beberapa algoritma ada yang rekursif dan ada pula yang tidak, sedangkan beberapa yang lain bisa menjalankan keduanya sekaligus (contoh: merge sort).

·         Stabilitas: menjaga urutan relatif dari rekord dengan indeks sama (contoh: nilai).

·         Apakah dia merupakan Sorting Pembanding atau tidak. Sorting pembanding memeriksa data dengan hanya membandingkan dua elemen dengan operator pembanding.

·         Metode Umum: memasukkan, menukar, memilih, menggabungkan, dll. Sorting Penukaran mencangkup bubble sort dan quicksort. Sorting Seleksi mencangkup shaker sort dan heapsort.

·         Penyesuaian: Apakah terdapat sorting yang belum terurut atau tidak dari inputannya, segalanya akan mempengaruhi waktu kalkulasinya. Algoritma yang mengambil cara ini sebagai caranya dikenal sebagai Adaptive.

Stabilitas

Algoritma pembanding yang stabil menjaga urutan relatif dari rekord dengan indeks yang sama. (Indeks merupakan porsi dari rekors yang menjadi basis dari sorting; yang mungkin ataupun tidak termasuk dalam rekord tersebut.) Jika seluruh indeks berbeda maka perbedaan ini tidak dibutuhkan. Tetapi jika terdapat indeks yang sama, maka algoritma sorting itu stabil walaupun terdapat dua rekord (misalkan R dan S) dengan indeks yang sama, dan R muncul sebelum S pada list aslinya, kemudian R akan selalu muncul sebelum S pada list yang terurut. Ketika elemen yang sama tak dapat dibedakan, seperti dengan integer, atau secara umumnya, setiap data dimana seluruh elemen ialah nilai, tingkat kestabilannya tidak dipermasalahkan. Walaupun, asumsikan bahwa setiap angka yang ganda diurutkan berdasarkan komponen pertama mereka:

Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:

1. Urut naik (ascending)
   Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar

2. Urut turun (descending)

   Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

Ada banyak alasan dan keuntungan dengan mengurutkan data. Data yang terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah untuk dibetulkan jika terdapat kesalahan. Data yang terurut dengan baik juga mudah untuk dihapus jika sewaktu-waktu data tersebut tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka kita semakin mudah untuk menyisipkan data atapun melakukan penggabungan data.

Metode-metode sorting meliputi:

1. Insertion Sort (Metode Penyisipan)
2. Selection Sort (Metode Seleksi)
3. Bubble sort(Metode Gelembung)
4. Shell Sort (Metode Shell)
5. Quick Sort (Metode Quick)
6. Merge Sort (Metode Penggabungan)

Pada kasus ini, dua nilai yang berbeda itu bisa saja terjadi, yang pertama menjaga urutan relatif rekord dengan nilai yang sama, dan yang satunya lagi tidak.

(3, 7)  (3, 1)  (4, 2)  (5, 6)   (urutan terjaga)

(3, 1)  (3, 7)  (4, 2)  (5, 6)   (urutan berubah)

Algoritma Sorting yang tidak stabil bisa saja mengubah urutan relatif rekord dengan nilai yang sama, tetapi algoritma sorting yang stabil tidak. Algoritma sorting yang tak stabil dapat secara khusus diimplementasikan pada yang stabil. Satu cara melakukannya ialah dengan secara buatan memperluas perbandingan nilainya, jadi perbandingan di antara dua objek dengan nilai yang sama dipilih dengan menggunakan urutan dari keseluruhan urutan data asli sebagai pemutus ikatan. Oder yang teratur ini bagaimanapun, sering melibatkan Nilai Komputasional tambahan.

Urutan didasari pada nilai pertama, kedua, ketiga, dll. Nilai urutan dapat dilakukan dengan metode sorting manapun, mengambil seluruh nilai sorting pada cacatan perbandingan (dengan kata lain, menggunakan nilai urutan gabungan tunggal). Jika metode sortingnya stabil, maka juga mungkin untuk mengurutkan kelipatan item, setiap waktu dengan satu nilai urut. Pada kasus ini nilai butuh ditempatkan untuk meningkatkan prioritas.

Contoh: Gabungan dua nilai sorting seperti diatas, kemudian komponen pertama:

(4, 2)  (3, 7)  (3, 1)  (5, 6) (asli)

(3, 1)  (4, 2)  (5, 6)  (3, 7) (setelah diurutkan dengan komponen kedua)

(3, 1)  (3, 7)  (4, 2)  (5, 6) (setelah diurutkan dengan komponen pertama)

Dengan kata lain:

(3, 7)  (3, 1)  (4, 2)  (5, 6) (setelah diurutkan dengan komponen pertama)

(3, 1)  (4, 2)  (5, 6)  (3, 7) (setelah diurutkan dengan komponen kedua,  pengurutan dengan komponen pertama terganggu).

Pengertian selection sort dan insertion sort

Pengertian Selection Sort
Selection Sort merupakan salah satu algoritma pengurutan yang sederhana. 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.

Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut:

1.                   Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list

2.                   Menukarkan nilai ini dengan elemen pertama list

3.                   Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua

4.                   Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan. 

Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan.


Algoritma pengurutan selection sort ini termasuk algoritma sulit dibagi/ mudah digabung (hard split/easy join).  Dari proses pengurutannya, Selection sort ini memiliki dua buah varian yaitu :

1. Maximum Sort
Memilih data yang maksimum dari suatu kumpulan data larik, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data maksimum berikutnya.

2. Minimum Sort
Memilih data yang minimum dari suatu kumpulan data larik , lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data minimum berikutnya.
Dalam pemecahan masalah algoritma selection sort , kita dapat memilih dua metode alternatif algoritma antara lain pemecahan dengan metode Brute Force dan pemecahan dengan metode devide and conquer.

Metode Pemecahan Brute Force
Kekuatan algoritma brute force terletak pada kemampuannya untuk menemukan semua pemecahan masalah yang mungkin, akan tetapi langkah yang dibutuhkan sangat banyak sehingga tidak baik jika digunakan untuk memecahkan masalah yang memiliki masukan yang cukup besar.

Pengertian Insertion Sort
Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

Penganalogian Insertion Sort dengan pengurutan kartu
Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.

1.                   Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. dan anggaplah kita akan menyusun kartu ke tangan kiri kita.

2.                   Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.

3.                   Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.

4.                   Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).
Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya, demikian juga halnya dalam pengurutan data. Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.

Catatan : Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

·        searching

Pengertian Searching

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci( key ). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table

Pencarian data sering juga disebut table look-up atau storage and retrieval

information adalah suatu proses untuk mengumpulkan sejumlah informasi di dalam

pengingat komputer dan kemudian mencari kembali informasi yang diperlukan secepat

mungkin.

Algoritma pencarian (searching algorithm) adalah algoritma yang menerima

sebuah argumen kunci dan dengan langkah-langkah tertentu akan mencari rekaman

dengan kunci tersebut. Setelah proses pencarian dilaksanakan, akan diperoleh salah

satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak

ditemukan (unsuccessful).

Metode pencarian data dapat dilakukan dengan dua cara yaitu pencarian internal

(internal searching) dan pencarian eksternal (external searching). Pada pencarian

internal, semua rekaman yang diketahui berada dalam pengingat komputer sedangakan

pada pencarian eksternal, tidak semua rekaman yang diketahui berada dalam pengingat

komputer, tetapi ada sejumlah rekaman yang tersimpan dalam penyimpan luar misalnya  pita atau cakram magnetis.

Selain itu metode pencarian data juga dapat dikelompokka menjadi pencarian

statis (static searching) dan pencarian dinamis (dynamic searching). Pada pencarian

statis, banyaknya rekaman yang diketahui dianggap tetap, pada pencarian dinamis,

banyaknya rekaman yang diketahui bisa berubah-ubah yang disebabkan oleh

penambahan atau penghapusan suatu rekaman.

Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner.

Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial

digunakan apabila data dalam keadaan acak atau tidak terurut. Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut.

1.       Pencarian Berurutan (Sequential Searching)

Pencarian berurutan sering disebut pencarian linear merupakan metode pencarian

yang paling sederhana. Pencarian berurutan menggunakan prinsip sebagai berikut : data

yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data

tersebut ditemukan atau tidak ditemukan.

Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai

dengan jumlah data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang

dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir

pengulangan tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling

buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.

Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

1 i ← 0

2 ketemu ← false

3 Selama (tidak ketemu) dan (i <= N) kerjakan baris 4

4 Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1

5 Jika (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak Ditemukan

2.       Pencarian Biner (Binary Search)

Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah dalam

keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner

tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering

menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus

Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula diambil

posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus

(posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data

tengah. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama

dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi posisi awal

dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah sama dengan yang dicari.
Pencarian biner merupakan salah satu cara atau metode untuk melaksanakan proses pencarian. Cara ini merupakan cara yang paling cepat di antara metode-metode yang lainnya. Metode pencarian biner dapat dijelaskan sebagai berikut. Pertama-tama data-data yang sduah ada harus diurutkan dahulu. Selanjuutnya data yang sudah diurutkan tadi disebut sebagai vektor. Kemudian vektor tadi dibagi menjadi dua subvektor yang memiliki jumlah elemen yang sama, kemudian data yang dicari dibandingkan dengan data terakhir dari subvektor pertama. Jika data tersebut lebih kecil maka berarti data kemungkinan ada di subvektor pertama, sehingga pencarian dapat dilakukan di subvektor pertama dengan terlebih dahulu membagi subvektor tadi menjadi dua subvektor. Jika lebih besar maka berarti data kemungkinan ada di subvektor kedua, sehingga pencarian dapat dilakukan di subvektor kedua dengan terlebih dahulu menbagi subvektor tadi menjadi dua subvektor.

PENGERTIAN SEARCHING

SEARCHING adalah mesin pencari WEB atau yang lebih dikenal dengan istilah WEB SEARCH merupakan program komputer yang dirancang untuk mencari informasi yang tersedia didalam dunia maya.

Cara Efektif Searching di Google

search di google terbagi dua jenis pencarian : Basic Search dan Advanced Search, Basich Search adalah fitur pencarian yang sudah biasa kita gunakan yaitu ketika mengakses google secara langsung.

Sedangkan yang Advanced Search menyediakan berbagai pilihan fitur pencarian baik secara operator dasar, file format yang kira ingin cari, bahasa dan lainnya.
FITUR DASAR PENCARIAN

1. AND : Mencari informasi yang mengandung kedua kata yang kita cari. contoh ukiran jepara maka masukan ukiran and jepara atau ukiran+jepara
2. OR :Mencari infornasi yang mengandung salah satu dari kedua kata. contoh sayur or ikan atau sayur | ikan
3. FRASE : Mencari informasi yang mengandung frase yang dicari dengan menggunakan tanda ” “. contoh “perangkat lunak”
4. NOT : Hasil pencarian yang mengandung kata yang di depan, tapi tidak dibelakang (-). contoh, ikan -nila kata tersebut akan mencari kata ikan tapi tidak untuk nila
5. SINONIM (~) : Mencari kata beserta sinonim-sinonimnya. contoh, ~mobil akan membawa hasil pencarian mobil dan sinonim-sinonimnya.
6. ASTERIK (*) : Karekter pengganti kata. dari contoh, hasil yang didapat bisa: ayam bakar pedas, ayam goreng dan lainnya ayam*pedas
7. TANDA TIKIK(.) : Karakter pangganti kata.Dari contoh ko.i dari contoh bisa didafatkan koki, kopi dan lainnya.
8. CASE INSENTITIVE : Pencarian di google menangkap kapital dan bukan kapital sebagai sesuatu yang sama. Jadi Bloger, bLoger, BloGER semuanya akan membawa pancarian yang sama
9. PENGABAIAN KATA : Google mengabaikan keyword berupa karakter tunggal dan kata-kata berikut : a, about, an, and, are, as, dan lainnya. tapi misalnya kita inginkan juga bisa dengan menggunakan karakter + di depan kata yang di cari (Misal : “SWars Episode + I”)

10. I’M FEELING LUCY : Akan membawa kita langsung menuju ke hasil pencarian pertama query kita.

FITUR PENCARIAN LANJUT

1. DEFINE : Mencari definisi dari sebuah terminologi. Dari contoh di bawah, hasil yang didapat adalah berbagai definisi tentang e-learning dari berbagai sumber. define:e-learning
2. CHACE : Menampilakn situs web yang telah diindeks oleh google meskipun sudah tidak aktif lagi. cache:cyberdeath.co.cc
3. LINK : Menampilkan daftar link yang mengarah ke sebuah situs. Contoh link:f4hrublogspot.com
4. RELATED : Menampilkan daftar situs yang serupa, mirip atau memiliki hubungan dengan suatu situs. Contoh related:f4hru.blogspot.com
5. INFO : Menampilkan informasi yang google ketahui tentang sebuah situs. contoh info:f4hru.blogspot.com
6. FILETYPE : Menampilkan jenis pencarian yang berupa extensi file tertentu. sedangkan jenis filenya adalah : doc, xls, rtf, swf, ps, lwp, wri, ppt, pdf, mdb, txt dan lainnya. Contoh : pemrograman website filetype:pdf atau filetype:pdf pemrograman website.
7. ALLINTITLE : Menampilkan seluruh kata yang dicari dalam TITLE halaman. Contoh allintitle:pemrograman
8. INTITLE : Menampilkan satu kata yang dicari di dalam TITLE halaman. Contoh intitle:pemrograman
9. SITE : Menampilkan pencarian khususdi suatu situs yang ditunjuk. Contoh pemrograman:f4hru.blogspot.com

10. INURL : Menampilkan seluruh kata yang dicari dalam URL. Menghasilkan daftar URL yang mengandung kata pemrograman. Contoh inurl:pemrograman

11. ALLINURL : Menampilkan seluruh kata yang dicari dalam URL.

Daftar referensi

-        https://id.wikipedia.org/wiki/Sorting

-        sisinform-aaf1231072.blogspot.com/2013/02/pengertian-sorting.html

-        andiagusta.blogspot.com/2014/02/algoritma-pencarian-searching.html

-        entin.lecturer.pens.ac.id/...%20Algoritma/.../Data%20Structure%20-%20

-        https://id.wikipedia.org/wiki/Algoritma_pencarian