Materi Struktur Organisasi Data Sorting
Hay sahabat blogger, tanpa panjang lebar nih aku mau memberikan materi yang bisa dibilang mudah tapi bisa membuat kalian bingung dengan tiba-tiba, materinya adalah sorting hehe, kalian gaakan bingung kalau kalian mengerti jadi silahkan dibaca yaa temen-temen.. XD
SORTING
Pengurutan data dalam struktur data sangat penting terutama
untuk data yang bertipe data numerik ataupun karakter. Pengurutan dapat
dilakukan secara ascending (urut naik) dan descending (urut turun). Pengurutan
(Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak
sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak
|
3 9 6
|
21 10 1 13
|
Ascending
|
1 3 6
|
9 10 13 21
|
Descending
|
21 13
|
10 9 6 3 1
|
Deklarasi Array Sorting
Mendeklarasikan
array secara global:
int data[100];
int n; //untuk jumlah data
Fungsi Tukar 2 Buah
Data:
void tukar (int a, int b) {
int tmp;
tmp = data
[a] ; data [a] = data [b] ; data [b] = tmp ;
BUBBLE SORT
Merupakan metode sorting termudah, diberi nama “Bubble”
karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke
posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara
membandingkan elemen sekarang dengan elemen berikutnya. Jika elemen sekarang
lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar, jika
pengurutan ascending. Jika elemen sekarang lebih kecil dari elemen berikutnya,
maka kedua elemen tersebut ditukar, jika pengurutan descending. Algoritma ini
seolah-olah
menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika
satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian
seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah
diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai
perurutan yang telah diinginkan.
Gambar 1. Proses ke-1 Algoritma Bubble Sort
Pada gambar di atas, pengecekan dimulai dari data yang paling akhir,
kemudian dibandingkan dengan data di depannya, jika data di
depannya lebih besar maka akan ditukar.
Gambar 2. Proses ke-2 Algoritma Bubble Sorting
Pada proses ke-2, pengecekan dilakukan sampai dengan data
ke-2 karena data pertama pasting sudah paling kecil.
Gambar 3. Proses
ke-3 Algoritma Bubble Sorting
Gambar 4. Proses
ke-4 Algoritma Bubble Sorting
Gambar 5. Proses
ke-5 Algortima Bubble Sorting
Sintaks program
fungsi Bubble Sort
void
bubble sort () {
for
(int i = 1; i<n; i++) {
for (int j = n-1; j>=1; j--) {
if (data [j] < data [j-1])
tukar (j, j-1); // ascending
}
}
Dengan
prosedur di atas, data terurut naik (ascending), untuk urut turun (descending)
silahkan ubah bagian:
if
(data [j] < data [j-1] )
Menjadi:
if
(data [j] > data [j-1])
tukar
(j, j-1);
Algoritma
Bubble Sorting mudah dalam sintaks, tetapi lebih hemat dibandingkan dengan
algoritma sorting yang lain.
EXCHANGE SORT
Sangat mirip dengan Bubble Sort, dan banyak yang mengatakan Bubble Sort sama dengan Exchange Sort. Perbedaan ada dalam hal bagaimana membandingkan antar elemen-elemennya. Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot). Sedangkan Bubble Sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
Sintaks program
fungsi Exchange Sorting
void
exchange sort ()
{
for
(int i=0; i<n-1; i++) {
for
(int j=(i+1); j<n; j++) { if (data [i] < data[j])
tukar(i,j);
//descending
}
}
}
SELECTION SORT
Merupakan kombinasi antara sorting dan
searching. Untuk setiap proses, akan dicari elemen- elemen yang belum diurutkan
yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang
tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan
nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada
putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks
kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada
indeks pembandingan saja, pertukaran data secara fisik terjadi pada akhir proses.
Gambar 7. Proses Algoritma Selection Sorting
Sintaks program
fungsi Selection Sorting
void selection_sort () {
for
(int i=0; i<n-1; i++) { pos = i;
for (int j=i+1; j<n; j++) {
if
(data[j] < data[pos]) pos = j; //ascending
}
If (pos != i) tukar(pos, i);
}
}
INSERT SORT
Mirip dengan cara orang mengurutkan kartu, selembar demi
selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.
Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan
data yang lebih kecil, maka akan ditempatkan (di-insert) diposisi yang seharusnya. Pada penyisipan elemen, maka
elemen-elemen lain akan bergeser ke belakang.
Gambar 9. Proses Algoritma Insertion Sorting
Sintaks program
fungsi Insertion Sort
void
insertion_sort () { int temp;
for(int
i=1; i<n; i++) { temp = data[i];
j = i-1;
while
(data[j]>temp && j>=0) { data[j+1] = data[j];
j--;
}
Data[j+1] = temp;
}
}
Program lengkapnya: (PERCOBAAN LATIHAN)
#include <stdio.h> #include <conio.h>
int data[10], data2[10]; int n;
void
tukar (int a, int b) { int t;
t = data[b]; data[b] = data[a]; data[a] = t;
}
void bubble_sort ()
{
for (int i=1;
i<n; i++) {
for (int j=n-1;
j>=i; j--) {
if (data[j] <
data[j-1])
tukar(j, j-1);
}
}
printf (“bubble sort selesai!\n”);
}
void exchange_sort
() {
for (int i=0;
i<n-1; i++) {
for
(int j = (i+1); j<n; j++) { if (data [i] > data[j])
tukar (i, j);
}
}
printf (“exchange sort selesai!\n”);
}
void
selection_sort () { int pos, i, j;
for
(i=0; i<n-1; i++) { pos = i;
for (j = i+1;
j<n; j++) {
if (data [j] < data[pos]) pos = j;
}
if (pos != i) tukar
(pos, i);
}
printf (“selection sort selesai!\n”);
}
void
insertion_sort () { int temp, i, j;
for (i=1; i<n;
i++) {
temp = data[i]; j = i-1;
while (data[j] > temp &&
j>=0) { data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
printf(“insertion sort selesai!\n”);
}
void Input () {
printf (“Masukkan jumlah
data = ”); scanf (“%d”, &n);
for(int i=0; i<n;
i++) {
printf (“Masukkan data ke-%d = ”, (i+1)); scanf (“%d”, &data[i]);
data2[i] = data[i];
}
}
void AcakLagi () {
for (int i=0; i<n; i++) { data[i] =
data2[i];
}
printf (“Data sudah teracak!\n”);
}
void
Tampil () {
printf (“Data : ”);
for
(int i=0; i<n; i++) { print (“%d ”, data[i]);
}
printf (“\n”);
}
void main() { clrscr();
int pil; do {
clrscr ();
printf (“1. Input
Data\n”); printf(“2. Bubble Sort\n”); printf(“3. Exchange Sort\n”); printf(”4.
Selection Sort\n”); printf(“5. Tampilkan Data\n”); printf(“6. Acak\n”);
printf(“7. Exit”);
printf(“Pilihan = ”);
scanf(“%d”, &pil); switch(pil) {
case 1: Input();
break;
case 2: bubble_sort(); break; case 3: exchange_sort(); break;
case 4: selection_sort(); break; case 5: Tampil(); break;
case
6: AcakLagi(); break;
}
getch();
}
while (pil!=7);
}
0 komentar :
Posting Komentar