Sorting and Searching
Sorting adalah sebuah cara untuk mengurutkan data yang berbasis sebuah variable. Jadi bisa diurutkan dengan angka nya, atau alphabet secara descending ataupun ascending.
Sorting ada beberapa macam yaitu :
1. Bubble Sort
Sorting ini adalah sorting yang paling mudah tetapi sorting ini paling tidak efektif dikarenakan bubble sort akan mengurutkan satu persatu dari semua data sehingga kompilasi nya adalah n kuadrat.
Jika ada 10 data dan semua nya teracak maka worst case adalah komputer akan melakukan loopingan sebanyak 100 kali.
2. Selection Sort
Selection Sort adalah sorting yang mencari nilai yang terkecil dari sekumpulan data dan memindahkan nya satu persatu. Jadi jika sudah ditemukan nilai minimal nya maka dia akan mencari nilai yang terkecil tetapi lebih besar dari nilai minimal yang sudah ditemukan sebelumnya.
0 1 2 3 4 -> index
50 60 20 10 70 -> maka nilai minimal nya 10 maka, nilai 10 ditukar dengan nilai 50
10 60 20 50 70 -> maka nilai minimal nya 10 dan akan dicari nilai yang paling kecil tetapi tidak lebih kecil dari 10 atau index nya dimulai dari 1
10 20 60 50 70 -> dan seterusnya
3. Insertion Sort
Sort ini sama seperti dengan selection sort tetapi sorting nya menggunakan temp sehingga lebih mudah meng-swap data yang ada.
4. Quick Sort
Quick sort adalah sorting yang paling tercepat, quick sort menggunakan tehnik rekursif dan dia akan meng-swap data dari kiri dan kanan sehingga komplikasinya Ω(n log(n)) [Best Scenario].
Quick sort akan memilih sebuah nilai sebagai sebuah acuan sehingga ia membandingkan data dari kiri dan dari kanan hingga tidak ada nilai yang lebih rendah dari acuan tersebut, setiap ada nilai yang lebih rendah dari nilai acuan akan diletakan di sebelah kanan nilai acuan dan seterusnya, setelah tidak ada nilai yang lebih rendah dari nilai acuan maka nilai acuan akan dipindahkan ke kanannya nilai yang lebih rendah dari nilai acuan lalu, nilai acuan akan berpindah ke angka disebelah kanan nilai acuan sebelumnya
5. Merge Sort
Merge sort adalah salah satu divide and conquer algorithm dimana kita memiliki sebuah problem maka akan dibagi menjadi problem - problem kecil dan diselesaikan secara satu persatu. Jadi semua data akan kita pisah, dibagi - bagi, setiap data akan memiliki 2 data lalu diurutkan sesuai dengan value yang ada di dalamnya.
Contoh :
5 2 4 6 1 3 2 6
pertama - tama diurutkan dari masing - masing data
2 5 4 6 1 3 2 6
Lalu tiap 2 data akan digabung dan diswap masing - masing data yang ada
2 4 5 6 1 2 3 6
Lalu dari 4 data yang digabungkan maka akan di gabung lagi menjadi 1 data dan di swap lagi
1 2 2 3 4 5 6 6
Searching
Kita biasa menggunakan array ataupun struct untuk menyimpan data, maka dari itu untuk mencari data yang kita masukkan kita menggunakan searching. Searching dilakukan dengan cara membandingkan sebuah nilai yang ingin kita cari dengan nilai yang berada di dalam array / struct yang ada.
Searching dibagi menjadi 3 macam yaitu ;
1. Linear Search
Linear Search termasuk searching yang paling lambat dikarenakan dia akan membandingan nilai satu persatu dari array awal hingga bertemu dengan array yang dicari, maka dari itu linear search memiliki komplikasi n, worst case nya adalah jika kita tidak menemukan data yang kita cari ataupun data yang kita cari berada di akhir array.
2. Binary Search
Binary search, searching ini dilakukan dengan cara membagi data yang ada menjadi 2, data yang berada ditengah disebut root. jadi dari root kita akan mencari, data yang kita cari valuenya lebih besar atau lebih kecil dari root, jika lebih kecil maka data akan di search ke arah kiri jika lebih besar maka, data akan di search ke arah kanan.
3. Interpolation search
Interpolation adalah search yang menggunakan rumus sebagai berikut :
MID = (key - data[minimal]) / (data[max] - data[minimal]) * (max - min) + minimal
Sehingga interpolation search akan mencari data yang mendekati dengan key(value yang kita cari) sehingga data akan ditemukan lebih cepat daripada linear ataupun binary search.
Sorting ada beberapa macam yaitu :
1. Bubble Sort
Sorting ini adalah sorting yang paling mudah tetapi sorting ini paling tidak efektif dikarenakan bubble sort akan mengurutkan satu persatu dari semua data sehingga kompilasi nya adalah n kuadrat.
Jika ada 10 data dan semua nya teracak maka worst case adalah komputer akan melakukan loopingan sebanyak 100 kali.
2. Selection Sort
Selection Sort adalah sorting yang mencari nilai yang terkecil dari sekumpulan data dan memindahkan nya satu persatu. Jadi jika sudah ditemukan nilai minimal nya maka dia akan mencari nilai yang terkecil tetapi lebih besar dari nilai minimal yang sudah ditemukan sebelumnya.
0 1 2 3 4 -> index
50 60 20 10 70 -> maka nilai minimal nya 10 maka, nilai 10 ditukar dengan nilai 50
10 60 20 50 70 -> maka nilai minimal nya 10 dan akan dicari nilai yang paling kecil tetapi tidak lebih kecil dari 10 atau index nya dimulai dari 1
10 20 60 50 70 -> dan seterusnya
3. Insertion Sort
Sort ini sama seperti dengan selection sort tetapi sorting nya menggunakan temp sehingga lebih mudah meng-swap data yang ada.
4. Quick Sort
Quick sort adalah sorting yang paling tercepat, quick sort menggunakan tehnik rekursif dan dia akan meng-swap data dari kiri dan kanan sehingga komplikasinya Ω(n log(n)) [Best Scenario].
Quick sort akan memilih sebuah nilai sebagai sebuah acuan sehingga ia membandingkan data dari kiri dan dari kanan hingga tidak ada nilai yang lebih rendah dari acuan tersebut, setiap ada nilai yang lebih rendah dari nilai acuan akan diletakan di sebelah kanan nilai acuan dan seterusnya, setelah tidak ada nilai yang lebih rendah dari nilai acuan maka nilai acuan akan dipindahkan ke kanannya nilai yang lebih rendah dari nilai acuan lalu, nilai acuan akan berpindah ke angka disebelah kanan nilai acuan sebelumnya
5. Merge Sort
Merge sort adalah salah satu divide and conquer algorithm dimana kita memiliki sebuah problem maka akan dibagi menjadi problem - problem kecil dan diselesaikan secara satu persatu. Jadi semua data akan kita pisah, dibagi - bagi, setiap data akan memiliki 2 data lalu diurutkan sesuai dengan value yang ada di dalamnya.
Contoh :
5 2 4 6 1 3 2 6
pertama - tama diurutkan dari masing - masing data
2 5 4 6 1 3 2 6
Lalu tiap 2 data akan digabung dan diswap masing - masing data yang ada
2 4 5 6 1 2 3 6
Lalu dari 4 data yang digabungkan maka akan di gabung lagi menjadi 1 data dan di swap lagi
1 2 2 3 4 5 6 6
Searching
Kita biasa menggunakan array ataupun struct untuk menyimpan data, maka dari itu untuk mencari data yang kita masukkan kita menggunakan searching. Searching dilakukan dengan cara membandingkan sebuah nilai yang ingin kita cari dengan nilai yang berada di dalam array / struct yang ada.
Searching dibagi menjadi 3 macam yaitu ;
1. Linear Search
Linear Search termasuk searching yang paling lambat dikarenakan dia akan membandingan nilai satu persatu dari array awal hingga bertemu dengan array yang dicari, maka dari itu linear search memiliki komplikasi n, worst case nya adalah jika kita tidak menemukan data yang kita cari ataupun data yang kita cari berada di akhir array.
2. Binary Search
Binary search, searching ini dilakukan dengan cara membagi data yang ada menjadi 2, data yang berada ditengah disebut root. jadi dari root kita akan mencari, data yang kita cari valuenya lebih besar atau lebih kecil dari root, jika lebih kecil maka data akan di search ke arah kiri jika lebih besar maka, data akan di search ke arah kanan.
3. Interpolation search
Interpolation adalah search yang menggunakan rumus sebagai berikut :
MID = (key - data[minimal]) / (data[max] - data[minimal]) * (max - min) + minimal
Sehingga interpolation search akan mencari data yang mendekati dengan key(value yang kita cari) sehingga data akan ditemukan lebih cepat daripada linear ataupun binary search.
Comments
Post a Comment