SORTING
Insertion Sort
SORTING (PENGURUTAN DATA)
Data
terkadang berada dalam bentuk yang tidak berpola ataupun dengan pola tertentu
yang diinginkan. Tidak ada algoritma terbaik untuk semua keadaan, kadang kala
sebuah algortitma sangat efisien ketika jumlah datanya sedikit, namun
kinerjanya menjadi berkurang ketika jumlah data ditambahkan atau meningkat.
Meskipun memiliki kemampuan komputasi yang lebih tinggi, namun jika menggunakan
algoritma yang kurang efisien, maka akan membutuhkan waktu lebih lama. Sehingga
untuk memecahkan permasalahan diperlukan sebuah algoritma yang efektif dan
efisien agar persoalan komputasi serta terbatasnya alokasi memori dapat
diatasi.
Secara
umum ada dua jenis pengurutan data yaitu :
1) Model urut naik (ascending) yang mengurutkan data dari
yang mempunyai nilai terkecil sampai terbesar.
2) Model urut turun (descending) yang mengurutkan data dari
yang mempunyai nilai terbesar sampai terkecil.
Jika N buah data disimpan
didalam sebuah array Nilai, maka
pengurutan ascending berarti menyusun
elemen array sedemikian hingga:
NILAI[0] ≤ NILAI[1] ≤ NILAI[2] ≤ ... ≤ NILAI[N-1] (1)
Sedangkan
pengurutan descending berarti
menyusun elemen array sedemikian
hingga:
NILAI[0] ≥ NILAI[1] ≥ NILAI[2] ≥ ...
≥ NILAI[N-1](2)
Algoritma pengurutan
data yang sering ditemukan dalam literatur komputer
antara lain
bubble sort, selection sort, insertion
sort, heap sort, shell sort, quick sort, merge sort, radix sort,dan tree sort. Semua algoritma pengurutan selalu
melakukan operasi perbandingan data untuk menemukan posisi urutan yang tepat.
Berdasarkan tempat penyimpanan data, sorting
dibedakan antara external sort dan
internal sort.External sort bila datanya berada
dalam media external, atau external storage seperti hardisk. Internal sort bila datanya ada dalam internal storage atau memory komputer
Insertion Sort
Insertion sort adalah suatu metode pengurutan
data dengan cara menyimpan data ke suatu variabel sementara, kemudian
dibandingkan dengan data-data lainnya yang ada disebelah kiri posisi data tersebut. Demikian
seterusnya hingga data terakhir
Algoritma Insertion Sort
Algoritma insertion sort, adalah metode pengurutan
dengan cara menyisipkan elemen data pada posisi yang tepat. Pencarian posisi
yang tepat dilakukan dengan melakukan pencarian berurutan didalam barisan
elemen, selama pencarian posisi yang tepat dilakukan pergeseran elemen. Pengurutan insertion
sort sangat mirip dengan konsep permainan kartu, bahwa setiap kartu
disisipkan secara berurutan dari kiri ke kanan sesuai dengan besar nilai kartu
tersebut, dengan syarat apabila sebuah kartu disisipkan pada posisi tertentu
kartu yang lain akan bergeser maju atau mundur sesuai dengan besaran nilai yang
dimiliki. Proses pengurutan data dalam sebuah array menggunakan algoritma insertion sort tersebut dapat dilihat
pada gambar
terlihat
pergeseran array dilakukan dari i=1 yang kemudian dibandingkan dengan array yang berada disebelah kiri.
Apabila array kedua lebih kecil dari array pertama, akan dilakukan penukaran.
Selanjutnya dengan looping secara
perlahan indeks dari array
sebelah kanan
dibandingkan lagi dengan array sebelah
kiri yang sudah tersusun rapi sehingga apabila ditemukan nilai sebelah kanan
lebih kecil dari nilai sebelah kiri yang sudah tersusun rapi, pergeseran dan
penukaran akan dilakukan.
1 Selection Sort
s Selection Sortadalah suatu metode
pengurutan data dengan cara memilih
suatu data pada urutan
tertentu, kemudian membandingkannya dengan data-data lainnya mulai dari posisi
[posisi data+1] sampai dgn data pada posisi
ke-n, untuk mencari
data terkecil pada rentang posisi
tersebut. Jika data terkecil ditemukan, maka pindahkan
data terkecil tersebut ke posisi [posisi data], dan data yang semula berada di
posisi[posisi data] dipindahkan ke posisi dimana data terkecil tadi ditemukan.
Demikian seterusnya hingga data terakhir
Algoritma Selection Sort
Algoritma
selection sort sering juga disebut
dengan metode maksimum atau minimum. Metode maksimum karena didasarkan pada
pemilihan data atau elemen maksimum sebagai dasar pengurutan. Konsepnya dengan
memilih elemen maksimum kemudian mempertukarkan elemen maksimum tersebut dengan
elemen paling akhir untuk urutan ascending
dan elemen pertama untuk descending.
Algoritma
selection sort disebut juga dengan
metode minimum karena didasarkan pada pemilihan elemen minimum sebagai dasar
pengurutan. Konsepnya dengan memilih elemen minimum kemudian mempertukarkan
elemen minimum dengan elemen paling akhir untuk urutan ascending dan elemen pertama untuk urutan descending. Proses yang dilakukan oleh algoritma selection sort adalah mengambil nilai
terbesar dari susunan data dan menggantikannya dengan data yang paling kanan.
Proses pengurutan data dalam sebuah array menggunakan algoritma selection
sort
tersebut dapat dilihat pada gambar
Terlihat
proses yang dilakukan oleh algoritma selection
sort adalah mengambil nilai terbesar dari susuna array dan menggantikannya dengan array yang paling kanan. Algoritma selection sort selalu menganggap nilai pada index pertama sebagai
nilai maksimum (max=0), kemudian
membandingkan nilai dari indeks pertama tersebut (array[max]) dengan nilai-nilai pada indeks berikutnya. Apabila
nilai dari indeks yang dibandingkan lebih tinggi dari nilai indeks pertama,
nilai tersebut diambil sebagai nilai max
(max=i). Pembandingan tersebut dilakukan sebanyak ukuran array atau sejumlah elemen data yang
akan diurutkan.
Visual Basic.Net
merupakan core dari pembuatan
aplikasi berbasis .Net, model untuk development dimana platform dan aplikasi bisa dibuat dan dijalankan tanpa bergantung
pada alat (device) yang dipakai. Pada penelitian ini Visual Basic .Net digunakan sebagai antar muka dalam perbandingan algoritma insertion sort dan selection sort
Bubble sort
(metode gelembung) adalah
metode/algoritma pengurutan dengan dengan cara melakukan
penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa
dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada
perubahan berarti data sudah terurut
Algoritma
Bubble Sort
Algoritma merupakan susunan atau
struktural yang diaplikasikan kedalam bahasa komputer atau pemrograman dengan
tujuan membantu dalam menyelesaikan permasalahan dimana akan ada data sebagai
masukan dan keluaran sebagai hasil dari proses yang dilakukan. Algoritma
pengurutan memiliki kelebihan dan kelemahan masing-masing, tidak semua
algoritma dapat digunakan untuk melakukan pengurutan data. Algoritma bubble sort adalah salah satu dari
beberapa jenis sorting yang digunakan untuk mengurutkan data. Cara kerja dari
algoritma ini yaitu mengulangi sebuah proses, lalu melakukan perbandingan di
masing-masing dari elemen array dan melakukan pergantian posisi jika urutannya
sudah sesuai. Pembandingan dari setiap elemen-elemen array ini akan terus dilakukan hingga kondisi yang ditentukan telah
sesuai. Jenis dari algoritma ini termasuk kedalam jenis algoritma comparison sort, karena melakukan perbandingan dalam operasi
diantara elemen- elemen array yang
disediakan.
Tahapan-tahapan didalam
algoritma bubble sort sebagai berikut
:
Langkah Pertama
1. Melakukan perbandingan array x[1] dengan array x[2],
lalu disusun kembali berdasarkan urutan yang sudah disesuaikan, sehingga x[1]
< x[2].
2. Melakukan perbandingan kembali terhadap array x[2] dengan array x[n], lalu disusun kembali berdasarkan urutan yang sudah
disesuaikan, sehingga x[2] < x[n].
3. Melakukan perbandingan array x[n-1] dengan array x[n],
lalu disusun kembali berdasarkan urutan yang sudah disesuaikan, sehingga array x[n-1] < x[n], setelah (n-1)
kali perbandingan, x[n] akan merupakan elemen array terbesar atau terkecil
pertama yang sudah terurut.
Langkah
Kedua
# Ulangi perbandingan bagian kedua hingga telah
membandingkan dan kemungkinan menyusun x[n-2],
x[n-1]
2 # Setelah
elemen array ke (n-2) perbandingan, (n-1) akan merupakan elemen terbesar ke-dua
#Dan dilanjutkan langkah berikutnya Langkah ke (n-1)
1. Melakukan perbandingan x[1] dengan x[2] lalu
disusun kembali sehingga memunculkan urutan x[1] < x[2]. Sesudah elemen array ke (n-1) langkah, elemen array
akan tersusun dalam urutan naik ataupun turun sesusai dengan ketentuan yang
sudah ditetapkan.
2. Dan
dilanjutkan langkah berikutnya sampai proses akhir selesai.
Bila diketahui sampel data array awal berupa 10,
6, 9, 8 dan 7, langkah untuk mengurutkan data tersebut dengan menggunakan
algoritma bubble sort adalah sebagaimana gambar
Sekarang kita masuk ke contoh soal dari ketiga metode program diatas
CONTOH SOAL INSERTION SORT
Buatlah sebuah program C++ dengan menggunakan metode Insertion Sort!!!
Catatan : Jumlah data yang diurutkan sesuai dengan Angka pada NIM (Nomor Induk Mahasiswa) Terakhir anda +5
Contoh : Jika NIM terakhir anda =8, maka jumlah datanya = >8 +5 = 13
Setiap Program Cantumkan Nama dan Nim anda
JAWABAN SOAL INSERTION SORT
#include <iostream>
using namespace std;
void tukar(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void insertion_sort(int data[])
{
for (int i = 0; i < 14; i++)
{
int index = i;
while ((index > 0) && (data[index] < data[index - 1]))
{
tukar(data[index], data[index - 1]);
index--;
}
}
}
int main()
{
cout << "NAMA : LDLTY LTDL" << endl;
cout << "NIM : 123456789" << endl;
cout << "KELAS : COMPUTER SCIENCE" << endl;
int data[14];
cout << "Silahkan input data : " << endl;
for (int i = 0; i < 14; i++)
{
cin >> data[i];
}
insertion_sort(data);
cout << "Data setelah diurutkan : " << endl;
for (int i = 0; i < 14; i++)
{
cout << data[i] << endl;
}
return 0;
}
CONTOH SOAL SELECTION SORT
Buatlah sebuah program C++ dengan menggunakan metode Insertion Sort!!!
Catatan : Jumlah data yang diurutkan sesuai dengan Angka pada NIM (Nomor Induk Mahasiswa) Terakhir anda +5
Contoh : Jika NIM terakhir anda =6, maka jumlah datanya = >6 +5 = 11
Setiap Program Cantumkan Nama dan Nim anda
JAWABAN SOAL SELECTION SORT
#include <iostream>
#include <algorithm>
using namespace std;
void tukar(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void selection_sort(int data[])
{
int index;
for (int i = 0; i < 4; i++)
{
index = i;
for (int j = i + 1; j < 4; j++)
{
if (data[j] < data[index])
index = j;
}
tukar(data[i], data[index]);
}
}
int main(int argc, char const *argv[])
{
cout << "NAMA : LDLTY LTDL" << endl;
cout << "NIM : 1234567899" << endl;
cout << "KELAS : COMPUTER SCIENCE" << endl;
int data[4];
cout << "Silahkan input data : " << endl;
for (int i = 0; i < 4; i++)
{
cin >> data[i];
}
selection_sort(data);
cout << "Data setelah diurutkan : " << endl;
for (int i = 0; i < 4; i++)
{
cout << data[i] << endl;
}
return 0;
}
CONTOH SOAL BUBBLE SORT
Buatlah sebuah program C++ dengan menggunakan metode Insertion Sort!!!
Catatan : Jumlah data yang diurutkan sesuai dengan Angka pada NIM (Nomor Induk Mahasiswa) Terakhir anda +5
Contoh : Jika NIM terakhir anda =3, maka jumlah datanya = >3 +5 = 8
Setiap Program Cantumkan Nama dan Nim anda
JAWABAN SOAL BUBBLE SORT
#include <iostream>
using namespace std;
void tukar(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void bubble_sort(int data[])
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 4 - i; j++)
{
if (data[j] > data[j + 1])
tukar(data[j], data[j + 1]);
}
}
}
int main()
{
cout << "NAMA : LDLTY LTDL" << endl;
cout << "NIM : 1234567899" << endl;
cout << "KELAS : COMPUTER SCIENCE" << endl;
int data[4];
cout << "Silahkan input data : " << endl;
for (int i = 0; i < 4; i++)
{
cin >> data[i];
}
bubble_sort(data);
cout << "Data setelah terurut " << endl;
for (int i = 0; i < 4; i++)
{
cout << data[i] << endl;
}
return 0;
}
SEKIAN LAH PENJELASAN YANG SAYA BUAT DIATAS TERSEBUT SEMOGA ANDA ANDA SEMUA BISA MEMAHAMINYA DEENGAN MUDAH
TERIMAKASIH
ASSALAMUALAIKUM WR.WB
BACA JUGA WEBSITE BERIKUT INI
BACA JUGAA WEBSITE BERIKUT INI
