inf202: struktur data pengurutan (sorting -...
TRANSCRIPT
Sorting • Pengurutan data dalam struktur data sangat penting
untuk data yang beripe data numerik ataupun karakter.
• Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
• Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.
• Contoh: – Data Acak : 5 6 8 1 3 25 10
– Ascending : 1 3 5 6 8 10 25
– Descending : 25 10 8 6 5 3 1
Metode Pengurutan Data • Pengurutan berdasarkan perbandingan (comparisoncomparison--based based
sortingsorting))
– Bubble sort, exchange sort
• Pengurutan berdasarkan prioritas (priority queue sorting priority queue sorting methodmethod))
– Selection sort, heap sort (menggunakan tree)
• Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted methodinsert and keep sorted method)
– Insertion sort, tree sort
• Pengurutan berdasarkan pembagian dan penguasaan (devidedevide and conquer methodand conquer method)
– Quick sort, merge sort
• Pengurutan berkurang menurun (diminishing increment sort diminishing increment sort methodmethod)
– Shell sort (pengembangan insertion)
Algoritma pengurutan (sorting) :
• Bubble sort (gelembung)
• Selection sort (maksimum/minimun)
• Insertion sort (sisip)
• Heap sort
• Shell sort
• Quick sort
• Merge sort
• Radix sort
• Tree sort
Deklarasi Array
• Deklarasikan: int data[100]; int n; //untuk jumlah data
• Fungsi untuk Tukar 2 Buah Data (by reference):
void tukar(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
1a. Bubble Sort
• 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.
Bubble Sort (2)
• Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.
• Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.
• Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya, asc atau desc.
• Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1.
• Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Bubble Sort (6)
• Dengan prosedur diatas, data terurut naik
(ascending), untuk urut turun (descending)
silahkan ubah bagian:
if (data[j]<data[j-1]) tukar(&data[j],&data[j-1]);
Menjadi:
if (data[j]>data[j-1]) tukar(&data[j],&data[j-1]);
• Teknik bubble sort mudah difahami, namun
pelaksanaannya adalah lambat.
1b. Exchange Sort
• Sangat mirip dengan Bubble Sort
• Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort
• Perbedaan : 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 tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
Contoh program bubble sort: #include <iostream>
using namespace std;
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; j>=i; j--) {
if(data[j] < data[j-1])
{
tukar(j, j-1);
}
}
}
}
main()
{
cout << "Masukkan jumlah data: ";
cin >> n;
cout << endl;
for(int i=1; i<=n; i++) {
cout << "Masukkan data ke-" << i << ": ";
cin >> data[i];
data2[i] = data[i]; }
bubble_sort();
cout << "\nData Setelah diurutkan" <<
endl;
cout << "------------------------" << endl;
for(int i=1; i<=n; i++)
{
cout << data[i] << " ";
}
cout << endl;
system("pause");
}
2. 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 pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
Program selection sort: #include <iostream>
#include <conio.h>
#include <stdio.h>
#include <iomanip>
using namespace std;
int main() {
int x[5]; int i; int temp; int minindex;
int j;
cout<<" >> Welcome To The Program
Selection Sort << \n" <<endl;
cout<<"masukkan nilai x :\n";
for(i=0; i<5; i++)
{ cout<<"x["<<i<<"] = ";cin>>x[i]; }
cout<<"\n data sebelum di sort :";
for(i=0; i<5;i++)
{ cout<<setw(4)<<x[i]; }
for(i=0; i<5-1; i++) //perulangan iterasi
{
minindex=i;
for(j=i+1; j<5; j++) //perulangan
membandingkan data
{
if(x[minindex]>x[j])
{
minindex=j;
}
}
temp=x[i];
x[i]=x[minindex];
x[minindex]=temp;
}
cout<<"\n\nData setelah di sort :";
for(i=0; i<5; i++)
{
cout<<setw(4)<<x[i];
}
getch();
}
3. Insertion 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 (diinsert) diposisi yang
seharusnya.
• Pada penyisipan elemen, maka elemen-elemen lain
akan bergeser ke belakang
Contoh Data awal: [5, 2, 4, 6, 1, 3]. Jumlah index adalah 6, dimulai dari
0 sampai 5. Anggaplah index adalah “I”, dimana untuk setiap
proses pengurutan, perbandingan data akan dimulai dari index
kedua (dalam hal ini i=1). Perhatikan algoritmanya.
Proses I: i=1, x=1; j=0
x<j à2<5? — true = 2, 5, 4, 6, 1, 3
Proses II i=2, j=1, x=2
x<j à 4<5 — true = 2, 4, 5, 6, 1, 3; j=j-1. Artinya jika proses benar,
maka “x=x-1”
x<j à4<2 — false = 2, 4, 5, 6, 1, 3
Proses III I=3, j=2, x=3
x<j à6<5 — false = 2, 4, 5, 6, 1, 3; j=j-1. Artinya jika sebuah proses
bernilai false, maka proses tersebut tidak akan dilanjutkan, karena semua
data yang ada di sebelah kiri sudah terurut dengan benar secara otomatis
.
Contoh sambungan…. Proses IV:
i=4, j=3, x=4
x<j à1<6 — true = 2, 4, 5, 1, 6, 3; j=j-1, jika benar maka x=x-1
x<j à 1<5 — true = 2, 4, 1, 5,6, 3; j=j-1, jika benar maka x=x-1
x<j à1<4 — true = 2, 1, 4, 5,6, 3; j=j-1, jika benar maka x=x-1
x<j à 1<2 — true = 1, 2, 4, 5,6, 3
Proses V:
i=5, j=4, x=5
x<j à3<6 — true = 1, 2, 4, 5,3, 6 j=j-1, jika benar maka x=x-1
x<j à3<5 — true = 1, 2, 4, 3, 5, 6 j=j-1, jika benar maka x=x-1
x<j à3<4 — true = 1, 2, 3, 4, 5, 6 j=j-1, jika benar maka x=x-1
x<jà3<2 — false = 1, 2, 3, 4, 5, 6 j=j-1
Programnya: #include<iostream> #include <conio.h> int main() { int data[]={5, 2, 4, 6, 1, 3}; cout<<“sebelum disorting: “; for(int i=0; i<6; i++) cout<<data[i] <<“, “; cout<<endl <<endl; for(int i=1; i<6; i++) { int j=i; while(data[j]<data[j-1])
{ int tmp=data[j]; data[j]=data[j-1]; data[j-1]=tmp; j–; } } cout<<“Setelah disorting: “; for(int i=0; i<6; i++) cout<<data[i] <<“, “; getch(); }
Output:
LATIHAN 13 1. Buat program sorting “insertion sort” dengan output:
2. Buat algoritma mengurutkan data berikut “8 17 20 11 5”, mengurutkan
array dari angka terendah ke nomor terbesar menggunakan bubble sort.
Dalam setiap langkah, unsur-unsur yang ditulis dalam huruf tebal
sedang dibandingkan.
3. Buat program pengurutan secara ascending dan descending dengan
selection sort.