Pengertian Sorting pada C++
Salah satu bagian
penting dari struktur data adalah proses pengurutan data. Data terkadang
akan berada dalam bentuk yang tidak berpola ataupun dengan pola
tertentu yang tidak kita inginkan. Namun dalam penggunaannya, kita akan
selalu ingin menggunakan data tersebut dalam bentuk yang rapi atau
berpola sesuai dengan yang kita inginkan. Maka dari itu proses sorting
adalah proses yang sangat penting dalam struktur data. Proses pengurutan
banyak ditemukan dalam pemrosesan komputer. Data yang sudah terurut
memiliki beberapa keuntungan. Selain mempercepat pencarian, data yang
sudah terurut juga dapat dengan mudah menentukan Nilai terbesar atau
terkecil.
Pengurutan data memang sangat relevan dan merupakan aktivitas yang
sangat penting berkaitan dengan pemrosesan data. Bahkan pengurutan data
telah banyak dilakukan dengan bantuan alat. Adanya kebutuhan terhadap
peroses pengurutan memunculkan bermacam-macam metode pengurutan yang
bertujuan untuk memperoleh metode pengurutan yang optimal.
1. Definisi Sorting pada C++
Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending), yaitu urutan objek yang disusun mulai dari Nilai terkecil hingga terbesar atau menurun (descending),
yaitu urutan objek yang disusun mulai dari Nilai terbesar hingga
terkecil. Jika N buah objek atau data disimpan di dalam array Nilai,
maka pengurutan menaik berarti menyusun elemen array sedemikian
sehingga:
NILAI[0] ≤ NILAI[1] ≤ NILAI[2] ≤ … ≤ NILAI[N-1]
Sedangkan pengurutan menurun berarti menyusun elemen array sedemikian sehingga:
NILAI[0] ≥ NILAI[1] ≥ … ≥ NILAI[N-1]
Data yang diurut dapat berupa data bertipe data dasar atau tipe data bentukan. Jika data bertipe bentukan (structure), maka harus disebutkan berdasarkan field apa data tersebut akan diurutkan.
Sama halnya dengan pencarian, pengurutan juga dibedakan menjadi dua kelompok, yaitu:
- Pengurutan Internal, yaitu pengurutan terhadap sekumpulan data yang
disimpan di dalam memori komputere. Umumnya struktur internal yang
dipakai untuk pengurutan ini adalah array, sehingga pengurutan internal
disebut dengan pengurutan array.
- Pengurutan Eksternal, yaitu pengurutan data yang disimpan di dalam
memori sekunder. Biasanya data dengan berjumlah besar sehingga tidak
mampu dimuat semuanya dalam memori komputer. Struktur eksternal yang
dipakai adalah arsip (file), maka pengurutan ini juga sering disebut dengan pengurutan arsip.
Baca juga : Pengertian dan Contoh Program Array pada C++
Karena pengaksesan memori utama lebih cepat dari pada pengaksesan
memori sekunder, maka pengurutan internal lebih cepat dibanding dengan
pengurutan eksternal.
Beberapa metode yang dapat digunakan untuk pengurutan antara lain:
- Bubble Sort
- Selection Sort
- Quick Sort
- Merge Sort
- Heap Sort
- Shell Sort
- Radix Sort
- Tree Sort
- Maximum Sort
- Insertion Sort
Banyaknya metode pengurutan yang tersedia menimbulkan pertanyaan:
algoritma manakah yang memiliki kinerja yang baik? Kinerja pengurutan
data sangat menentukan kinerja sistem, karena itu pemilihan metode
pengurutan yang cocok akan berperan dalam suatu aplikasi. Metode
pengurutan yang akan dibahas adalah metode pengurutan Bubble Sort, Quick
Sort, Maximum/Minimum Sort, Shell Sort, Merge Sort, dan Insertion.
2. Bubble Sort
Bubble Sort adalah metode yang membandingkan elemen yang
sekarang dengan elemen-elemen berikutnya. Pembandingan elemen dapat
dimulai dari awal atau mulai dari paling akhir. Apabila elemen yang
sekarang lebih besar (untuk urut menaik) atau lebih kecil (untuk urut
menaik) dari elemen berikutnya, maka posisinya ditukar, tetapi jika
tidak maka posisinya tetap.
Contoh : Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menaik dengan metode Bubble Sort: 25, 71, 30, 45, 20,
15, 6, 50. Urutan langkah pengurutannya yang dimulai dari belakang
seperti berikut dan programnya dapat dilihat pada program
Lat_Sorting_01a.
Perhatikan contoh pengurutan yang diperagakan di atas bahwa pada langkah
4 telah terurut, maka sebenarnya proses sudah dapat dihentikan. Untuk
mengatasi hal itu dalam program Lat_Sorting_01b digunakan variabel
bertipe Boolean. Demikian juga halnya pengurutan secara menaik di atas
tetap menggunakan variabel bertipe Boolean untuk mengatasi hal yang
sama.
/* Program Pengurutan Metode Bubble Sort
Pengurutan Secara Menaik
Nama File : Lat_Sorting_01a */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
int Nilai[20];
int i, j, k, N;
int temp;
bool tukar;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
}
//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
//Proses Pengurutan
i=0;
tukar = true;
while ((i<=N-2) && (tukar))
{
tukar = false;
for(j=N-1; j>=i+1; j--)
{
if(Nilai[j] < Nilai[j-1])
{
{
temp = Nilai[j];
Nilai[j] = Nilai[j-1];
Nilai[j-1] = temp;
tukar = true;
cout<<"\nUntuk j = " <<j<<" : ";
for(k=0; k<N; k++)
cout<<set(3)<<Nilai[k];
}
}
i++;
}
//Proses Cetak Setelah diurutkan
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
getch();
}3. Quick Sort
Quick Sort merupakan metode tercepat dalam proses pengurutan
data dengan menggunakan prinsip rekursif. Metode ini menggunakan
strategi “pecah-belah” dengan mekanisme berikut ini.
Misalkan kita mempunyai array Nilai[k..l]. Array dipartisi menjadi
dua bagian array kiri Nilai[k..m] dan array kanan Nilai[m+1..l]. Dasar
mempartisi array menjadi dua adalah dengan mengambil elemen pertama
sebagai elemen pivot. Letakkan semua elemen array yang lebih kecil dari
pivot ke sebelah pivot dan semua elemen array yang lebih besar dari
pivot ke sebelah kanan pivot. Elemen-elemen yang di sebelah kiri elemen
pivot merupakan elemen-elemen array Nilai[k..m] sedangkan elemen-elemen
array Nilai[m+2..l] adalah semua elemen yang lebih besar dari pivot.
Lakukan hal yang sama seperti di atas terhadap array Nilai[k..m] dan
Nilai[m+1..l] hingga tidak dapat dipartisi lagi.
Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menaik dengan metode Maximum Sort: 25, 72, 30, 45, 20,
15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya
dapat dilihat pada program Lat_Sorting_02a.
- Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen
array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan
letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan
elemen pivot.
- Gunakan array Nilai[0..2]. Ambil elemen pertama sebagai elemen
pivot, letakkan semua elemen array yang lebih kecil dari pivot ke
sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih
besar dari pivot ke sebelah kanan elemen pivot.
Perhatikan array Nilai[2] tidak dapat lagi dipartisi maka berhenti sampai disana.
- Gunakan array Nilai[0..1]. Ambil elemen pertama sebagai elemen
pivot, letakkan semua elemen array yang lebih kecil dari pivot ke
sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih
besar dari pivot ke sebelah kanan elemen pivot.
Perhatikan array Nilai[0] dan Nilai[1] tidak dapat lagi dipartisi maka berhenti sampai di sana.
- Gunakan array Nilai[4..7]. Ambil elemen pertama sebagai elemen
pivot, letakkan semua elemen array yang lebih kecil dari pivot ke
sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih
besar dari pivot ke sebelah kanan elemen pivot.
- Gunakan array Nilai[4..6]. Ambil elemen pertama sebagai elemen
pivot, letakkan semua elemen array yang lebih kecil dari pivot ke
sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih
besar dari pivot ke sebelah kanan elemen pivot.
- Gunakan array Nilai[5..6]. Ambil elemen pertama sebagai elemen
pivot, letakkan semua elemen array yang lebih kecil dari pivot ke
sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih
besar dari pivot ke sebelah kanan elemen pivot.
Karena semua elemen array sudah tidak dapat dipartisi maka proses
pengurutan berakhir dan hasilnya diperoleh seperti berikut (gabungkan
mulai Nilai[0] hingga Nilai[7]):
Untuk melakukan proses pengurutan data secara menurun dengan metode
Quick Sort dilakukan dengan meletakkan semua elemen array yang lebih
kecil dari pivot ke sebelah kanan pivot dan semua elemen array yang
lebih besar dari pivot ke sebelah kiri pivot.
/* Program Pengurutan Metode Quick Sort
Pengurutan Secara Menaik
Nama File : Lat_Sorting_02a */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void Cetak(int data[], int n)
{
int i;
for(i=0; i<n; i++)
cout<<setw(3)<<data[i];
cout<<"\n";
}
int Partisi(int data[], int p, int r)
{
int x, i, j, temp;
x = data[p];
i=p;
j=r;
while(l)
{
while(data[j]>x)
j--;
while(data[i]<x)
i++;
if(i<j)
{
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
else
return j;
}
}
void Quick_Sort(int data[], int p, int r)
{
int q;
if(p<r)
{
q=Partisi(data, p, r+1);
Quick_Sort(data, p, 1);
Quick_Sort(data, q+1, r);
}
}
void main()
{
int Nilai[20];
int i, N;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
cout<<"\nData Sebelum di urut : ";
Cetak(Nilai, N);
cout<<endl;
Quick_Sort(Nilai, 0, N-1);
cout<<"\nData Setelah di urut : ";
Cetak(Nilai,N);
getch();
}
4. Metode Maximum/Minimum Sort
Metode Maximum/Minimum Sort dilakukan berdasarkan pemilihan elemen
maksimum/minimum, maka metode ini disebut juga dengan metode
pemilihan/seleksi (Selection Sort).
4.1 Metode Maximum Sort
Metode ini disebut dengan metode Maximum karena didasarkan pada
pemilihan elemen maksimum sebagai dasar pengurutan. Konsepnya adalah
memilih elemen maksimum kemudian mempertukarkan elemen maksimum tersebut
dengan elemen paling akhir untuk urut menaik dan elemen pertama untuk
urut menurun. Selanjutnya elemen paling akhir/awal tersebut
di-“isolasi”, artinya elemen tersebut tidak disertakan lagi untuk
tahapan berikutnya. Proses yang sama dilakukan kembali terhadap elemen
array yang tersisa, yaitu memilih elemen maksimum kemudian
mempertukarkan elemen maksimum tersebut dengan elemen paling akhir/awal
dari array yang tersisa tadi. Kemudian diisolasi kembali. Demikian
seterusnya hingga semua elemen terurut.
Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menaik dengan metode Maximum Sort: 25, 72, 30, 45, 20,
15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya
dapat dilihat pada program Lat_Sorting_04a.
Langkah -1: Cari elemen maksimum di dalam array Nilai[0..7] →
Nilai[1]=72 kemudian tukarkan dengan elemen array paling akhir Nilai[7]
sehingga diperoleh array:
Langkah -2: Cari elemen maksimum di dalam array yang tersisa
Nilai[1..7] → Nilai[1]=50 kemudian tukarkan dengan elemen paling akhir
array yang tersisa Nilai[6] sehingga diperoleh array:
Langkah -3: Cari elemen maksimum di dalam array yang tersisa
Nilai[2..7] → Nilai[3]=45 kemudian tukarkan dengan elemen paling akhir
array yang tersisa Nilai[5] sehingga diperoleh array:
Langkah -4: Cari elemen maksimum di dalam array yang tersisa
Nilai[3..7] → Nilai[2]=30 kemudian tukarkan dengan elemen paling akhir
array yang tersisa Nilai[4] sehingga diperoleh array:
Langkah -5: Cari elemen maksimum di dalam array yang tersisa
Nilai[4..7] → Nilai[0]=25 kemudian tukarkan dengan elemen paling akhir
array yang tersisa Nilai[3] sehingga diperoleh array:
Langkah -6: Cari elemen maksimum di dalam array yang tersisa
Nilai[5..7] → Nilai[2]=20 kemudian tukarkan dengan elemen paling akhir
array yang tersisa Nilai[2], sehingga diperoleh array:
Langkah -7: Cari elemen maksimum di dalam array yang tersisa
Nilai[6..7] → Nilai[0]=15 kemudian tukarkan dengan elemen paling akhir
array yang tersisa Nilai[1], sehingga diperoleh array:
Selesai. Dan array telah terurut secara menarik. Program mengurutkan
secara menaik dengan metode Maximum Sort dapat dilihat pada program
Lat_Sorting_04a.
/* Program Pengurutan Metode Maximum Sort
Pengurutan Secara Menaik
Nama File : Lat_Sorting_04a */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
int Nilai[20];
int i, j, N, l;
int temp, U, Imaks;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
//Proses Pengurutan
U=N-1;
for(i=0; i<=N-2; i++)
{
Imaks = 0;
for(j=1; j<=U; j++)
{
if(Nilai[j] > Nilai[Imaks])
Imaks = j;
}
temp = Nilai[U];
Nilai[U] = Nilai[Imaks];
Nilai[Imaks] = temp;
U--;
cout<<endl;
for(l=0; l<N; l++)
cout<<setw(3)<<Nilai[l];
}
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
getch();
} Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menurun dengan metode Maximum Sort 25, 72, 30, 45, 20,
15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya
dapat dilihat pada program Lat_Sorting_04b.
Langkah -1: Cari elemen maksimum di dalam array Nilai[0..7] →
Nilai[1]=72 kemudian tukarkan dengan elemen pertama array Nilai[0]=25
sehingga diperoleh array:
Langkah -2: Cari elemen maksimum di dalam array yang tersisa
Nilai[1..7] → Nilai[7]=50 kemudian tukarkan dengan elemen pertama array
yang tersisa Nilai[1]=25 sehingga diperoleh array:
Langkah -3: Cari elemen maksimum di dalam array yang tersisa
Nilai[2..7] → Nilai[3]=45 kemudian tukarkan dengan elemen pertama array
yang tersisa Nilai[2]=30 sehingga diperoleh array:
Langkah -4: Cari elemen maksimum di dalam array yang tersisa
Nilai[3..7] →Nilai[3]=3- kemudian tukarkan dengan elemen pertama array
yang tersisa Nilai[3]=30 sehingga diperoleh array:
Langkah -5: Cari elemen maksimum di dalam array yang tersisa
Nilai[4..7] → Nilai[7]=35 kemudian tukarkan dengan elemen pertama array
yang tersisa Nilai[4]=30 sehingga diperoleh array:
Langkah -6: Cari elemen maksimum di dalam array yang tersisa
Nilai[5..7] → Nilai[7]=20 kemudian tukarkan dengan elemen pertama array
yang tersisa Nilai[5]=15 sehingga diperoleh array:
Langkah -7: Cari elemen maksimum di dalam array yang tersisa
Nilai[6..7] → Nilai[7]=15 kemudian tukarkan dengan elemen pertama array
yang tersisa Nilai[6]=6 sehingga diperoleh array:
Selesai. Dan array telah terurut secara menurun. Program mengurutkan
secara menurun dengan metode Maximum Sort dapat dilihat pada program
Lat_Sorting_04b.
/* Program Pengurutan Metode Maximum Sort
Pengurutan Secara Menurun
Nama File : Lat_Sorting_04b */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
int Nilai[20];
int i, j, N, l;
int temp, U, Imaks;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
//Proses Pengurutan
U=N-1;
for(i=0; i<=N-2; i++)
{
Imaks = i;
for(j=i+1; j<=U; j++)
{
if(Nilai[j] > Nilai[Imaks])
Imaks = j;
}
temp = Nilai[i];
Nilai[i] = Nilai[Imaks];
Nilai[Imaks] = temp;
cout<<endl;
for(l=0; l<N; l++)
cout<<setw(3)<<Nilai[l];
}
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
getch();
}
4.2. Metode Minimum Sort
Metode ini disebut dengan metode minimum karena didasarkan pada
pemilihan elemen minimum sebagai dasar pengurutan. Konsepnya adalah
memilih elemen minimum kemudian mempertukarkan elemen minimum tersebut
dengan elemen paling akhir untuk urut menaik dan elemen pertama untuk
urut menurun. Selanjutnya elemen paling akhir/pertama tersebut di
“isolasi” artinya elemen tersebut tidak disertakan lagi untuk tahapan
berikutnya. Proses yang sama dilakukan kembali terhadap elemen array
yang tersisa, yaitu memilih elemen minimum kemudian mempertukarkan
elemen minimum tersebut dengan elemen paling akhir/pertama dari array
yang tersisa tadi. Kemudian diisolasi kembali. Demikian seterusnya
hingga semua elemen terurut.
Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menaik dengan metode Minimum Sort: 25, 72, 30, 45, 20,
15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya
dapat dilihat pada program Lat_Sorting_05a.
Langkah -1: Cari elemen minimum di dalam array Nilai[0..7] →
Nilai[6]=6 kemudian tukarkan dengan elemen pertama array Nilai[0]=25
sehingga diperoleh array:
Langkah -2: Cari elemen minimum di dalam array Nilai[1..7] →
Nilai[5]=15 kemudian tukarkan dengan elemen pertama array yang tersisa
Nilai[1]=72 sehingga diperoleh array:
Langkah -3: Cari elemen minimum di dalam array Nilai[2..7] →
Nilai[4]=2- kemudian tukarkan dengan elemen pertama array yang tersisa
Nilai[2]=30 sehingga diperoleh array:
Langkah -4: Cari elemen minimum di dalam array Nilai[3..7] →
Nilai[6]=25 kemudian tukarkan dengan elemen pertama array yang tersisa
Nilai[3]=45 sehingga diperoleh array:
Langkah -5: Cari elemen minimum di dalam array Nilai[4..7] →
Nilai[4]=30 kemudian tukarkan dengan elemen pertama array yang tersisa
Nilai[4]=30 sehingga diperoleh array:
Langkah -6: Cari elemen minimum di dalam array Nilai[5..7] →
Nilai[6]=45 kemudian tukarkan dengan elemen pertama array yang tersisa
Nilai[5]=72 sehingga diperoleh array:
Langkah -7: Cari elemen minimum di dalam array Nilai[6..7] →
Nilai[7]=50 kemudian tukarkan dengan elemen pertama array yang tersisa
Nilai[6]=72 sehingga diperoleh array:
/* Program Pengurutan Metode Minimum Sort
Pengurutan Secara Menaik
Nama File : Lat_Sorting_05a */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
int Nilai[20];
int i, j, N, l;
int temp, Imin;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
//Proses Pengurutan
for(i=0; i<=N-2; i++)
{
Imin = i;
for(j=i+1; j<N; j++)
{
if(Nilai[j] < Nilai[Imin]);
Imin = j;
}
temp = Nilai[i];
Nilai[i] = Nilai[Imin];
Nilai[Imin] = temp;
cout<<endl;
for(l=0; l<N; l++)
cout<<setw(3)<<Nilai(l);
}
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
getch();
}
Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menurun dengan metode Minimum Sort: 25, 72, 30, 45, 20,
15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya
dapat dilihat pada program Lat_Sorting_05b.
Langkah -1: Cari elemen minimum di dalam array Nilai[0..7] →
Nilai[6]=6 kemudian tukarkan dengan elemen terakhir array Nilai[7]=50
sehingga diperoleh array:
Langkah -2: Cari elemen minimum di dalam array yang tersisa
Nilai[0..6] → Nilai[5]=15 kemudian tukarkan dengan elemen terakhir array
yang tersisa Nilai[6]=50 sehingga diperoleh array:
Langkah -3: Cari elemen minimum di dalam array yang tersisa
Nilai[0..5] → Nilai[4]=20 kemudian tukarkan dengan elemen terakhir array
yang tersisa Nilai[5]=50 sehingga diperoleh array:
Langkah -4: Cari elemen minimum di dalam array yang tersisa
Nilai[0..4] → Nilai[0]=25 kemudian tukarkan dengan elemen terakhir array
yang tersisa Nilai[4]=50 sehingga diperoleh array:
Langkah -5: Cari elemen minimum di dalam array yang tersisa
Nilai[0..3] → Nilai[2]=30 kemudian tukarkan dengan elemen terakhir array
yang tersisa Nilai[3]=45 sehingga diperoleh array:
Langkah -6: Cari elemen minimum di dalam array yang tersisa
Nilai[0..2] → Nilai[2]=45 kemudian tukarkan dengan elemen terakhir array
yang tersisa Nilai[2]=45 sehingga diperoleh array:
Langkah -7: Cari elemen minimum di dalam array yang tersisa
Nilai[0..1] → Nilai[0]=50 kemudian tukarkan dengan elemen terakhir array
yang tersisa Nilai[1]=72 sehingga diperoleh array:
Selesai. Dan array terurut secara menurun. Program mengurutakan
secara menurun dengan metode Minimum Sort dapat dilihat pada program
Lat_Sorting_05b.
/* Program Pengurutan Metode Minimum Sort
Pengurutan Secara Menurun
Nama File : Lat_Sorting_05b */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
int Nilai[20];
int i, j, N, l;
int temp, U, Imin;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
//Proses Pengurutan
U=N-1;
for(i=0; i<=N-2; i++)
{
Imin = 0;
for(j=1; j<=U; j++)
{
if(Nilai[j] < Nilai[Imin])
Imin = j;
}
temp = Nilai[U];
Nilai[U] = Nilai[Imin];
Nilai[Imin] = temp;
cout<<endl;
U--;
for(l=0; l<N; l++)
cout<<setw(3)<<Nilai[l];
}
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i]
getch();
}
5. Metode Shell Sort
Metode ini dinamakan sesuai dengan penciptanya, yaitu D.L. Shell.
Metode ini mirip dengan metode Bubble Sort, hanya saja perbandingan
dilakukan bukan antara dua bilangan yang berurutan, akan tetapi antara
dua bilangan dengan jarak tertentu. Jarak ditentukan dengan N Div 2,
dimana N adalah banyaknya elemen array. Lakukan pertukaran tempat jika
setiap kali perbandingan dipenuhi (lebih besar untuk urut menaik dan
lebih kecil untuk urut menurun). Setiap kali perbandingan terhadap
keseluruhan elemen selesai dilakukan, maka perbandingan yang baru
dilakukan kembali dimana jarak diperoleh dengan Jarak Div 2 (jarak
diperoleh dari Nilai jarak sebelumnya). Perbandingan keseluruhan
dilakukan sampai Nilai jarak sama dengan 1 (satu). Pada saat jarak
berNilai 1, maka metode Shell Sort sama dengan metode Bubble Sort.
Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menaik dengan metode Shell Sort: 25, 72, 30, 45, 20,
15, 6, 59. Urutan langkah pengurutannya seperti berikut.
Untuk pertama kalinya Nilai jarak (K) = 8 div 2 = 4 dan kita buat
suatu counter C=0. Kemudian proses perbandingan dilakukan berturut-turut
antara Nilai[0] dengan Nilai[4], jika Nilai[0]>Nilai[4] maka lakukan
pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[1] dengan
Nilai[5], jika Nilai[1]>Nilai[5] maka lakukan pertukaran tempat dan
jika tidak lanjutkan terhadap Nilai[2] dengan Nilai[6], jika
Nilai[2]>Nilai[6] maka lakukan pertukaran tempat dan jika tidak
lanjutkan terhadap Nilai[3] dengan Nilai[7], jika Nilai[3]>Nilai[7]
maka lakukan pertukaran tempat kemudian Nilai C=1.
Karena Nilai K masih sama dengan 4 dan Nilai C=1, maka lakukan
kembali proses perbandingan dengan menghitung Nilai jarak (K) sama
dengan 4 div 2 =2 dan membuat Nilai C=0, sekarang proses perbandingan
dilakukan berturut-turut antara Nilai[0] dengan Nilai[2], jika
Nilai[0]>Nilai[2] maka lakukan pertukaran tempat dan jika tidak
lanjutkan terhadap Nilai[1] dengan Nilai[3], jika Nilai[1]>Nilai[3]
maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap
Nilai[2] dengan Nilai[4], jika Nilai[2]>Nilai[4] maka lakukan
pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[3] dengan
Nilai[5], jika Nilai[3]>Nilai[5] maka lakukan pertukaran dan jika
tidak lanjutkan terhadap Nilai[4] dengan Nilai[6], jika
Nilai[4]>Nilai[6] maka lakukan pertukaran dan jika tidak lanjutkan
terhadap Nilai[5] dengan Nilai[7], jika Nilai[5]>Nilai[7] maka
lakukan pertukaran tempat kemudian Nilai C=1.
Karena Nilai K masih sama dengan 2 dan Nilai C=1, maka lakukan
kembali proses perbandingan dengan menghitung Nilai jarak(K) sama dengan
2 div 2 = 1 dan membuat Nilai C=0, sekarang proses perbandingan
dilakukan berturut-turut antara Nilai[0] dengan Nilai[1], Nilai[1]
dengan Nilai[2], Nilai[2] dengan Nilai[3], Nilai[3] dengan Nilai[4],
Nilai[4] dengan Nilai[5], Nilai[5] dengan Nilai[6], dan
Nilai[6]>Nilai[7], kemudian Nilai C=1 akan diperoleh hasil pertukaran
setelah perbandingan seperti berikut.
6 15 20 25 45 30 50 72
Walaupun K telah berNilai sama dengan satu, tetapi Nilai C masih
berNilai sama dengan 1 maka perbandingan harus diulang kembali dengan
memberi Nilai C=0 dan Nilai K sama seperti sebelumnya yaitu sama dengan
1. Setelah dilakukan perbandingan maka hasilnya dapat diperoleh seperti
berikut:
6 15 20 25 30 45 50 72
Karena Nilai C tidak lagi berubah menjadi 1 maka perbandingan telah
berakhir dan hasil terakhir merupakan hasil pengurutan yang diharapkan.
/* Program Pengurutan Metode Shell Sort
Pengurutan Secara Menaik
Nama File : Lat_Sorting_06a */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
int Nilai[20];
int i, N, l, k;
int temp, jarak, s;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(4)<<Nilai[i];
//Proses Pengurutan
jarak = N / 2;
cout<<"\nJarak = "<<jarak;
while(jarak >=1)
{
do
{
s=0;
for(i=0; i<=(N-jarak)-1; i++)
{
k=i+jarak;
if(Nilai[i] > Nilai[k])
{
temp = Nilai[i];
Nilai[i] = Nilai[k];
Nilai[k] = temp;
s=1;
for(l=0; l<N; l++)
cout<<setw(4)<<Nilai[i];
cout<<"\n\t";
getch();
}
}
}
while(s!=0);
jarak /= 2;
cout<<"\nJarak= "<<jarak;
}
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(4)<<Nilai[i];
getch();
}Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menurun dengan metode Shell Sort: 25, 72, 30, 45, 20,
15, 6, 50. Urutan langkah pengurutannya seperti berikut.
Dengan cara yang sama untuk pengurutan secara menaik, dengan
mengganti tanda > menjadi < maka akan diperoleh elemen array yang
terurut secara menurun. Gunakan program Lat_Sorting_06b.
/* Program Pengurutan Metode Shell Sort
Pengurutan Secara Menaik
Nama File : Lat_Sorting_06a */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
int Nilai[20];
int i, N, l, k;
int temp, jarak, s;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(4)<<Nilai[i];
//Proses Pengurutan
jarak = N / 2;
cout<<"\nJarak = "<<jarak;
while(jarak >=1)
{
do
{
s=0;
for(i=0; i<=(N-jarak)-1; i++)
{
k=i+jarak;
if(Nilai[i] > Nilai[k])
{
temp = Nilai[i];
Nilai[i] = Nilai[k];
Nilai[k] = temp;
s=1;
for(l=0; l<N; l++)
cout<<setw(4)<<Nilai[i];
cout<<"\n\t";
getch();
}
}
}
while(s!=0);
jarak /= 2;
cout<<"\nJarak= "<<jarak;
}
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(4)<<Nilai[i];
getch();
}6. Metode Merge Sort
Metode ini memanfaatkan keteraturan yang diperoleh dari hasil merging
dua buah array. Suatu array Nilai yang mempunyai N elemen
(Nilai[0..N-1]) dianggap terdiri dari N array yang masing-masing terdiri
dari satu elemen. Untuk pasangan array yang berdekatan kita lakukan
merging sehingga diperoleh N/2 buah array yang masing-masing array
memiliki 2 elemen (jika N ganjil, akan terdapat sebuah array dengan 1
elemen). Pada saat melakukan proses merging dilakukan pengaturan posisi
dengan cara elemen yang lebih kecil diletakkan di posisi awal (untuk
pengurutan secara menaik) dan elemen yang lebih besar diletakkan di
posisi awal(untuk pengurutan secara menurun). Kemudian dilakukan merging
kembali untuk setiap pasanga array seperti cara di atas sehingga kita
peroleh N/2 buah array yang masing-masing array memiliki 4 elemen.
Langkah ini kita teruskan hingga kita memperoleh sebuah array yang sudah
dalam keadaan terurut.
Misalkan
kita memiliki array Nilai[0..13] = {45, 12, 4, 78, 90, 74, 40, 20, 10,
15, 25, 22, 95, 81} maka dengan menggunakan metode Merge Sort secara
menaik dapat dilakukan seperti pada gambar.
7. Metode Insertion Sort
Metode Insertion Sort merupakan metode pengurutan dengan cara
menyisipkan elemen array pada posisi yang tepat. Pencarian yang tepat
dilakukan dengan melakukan pencarian beruntun di dalam array. Selama
pencarian posisi yang tepat dilakukan pergeseran elemen array. Algoritma
pengurutan ini tepat untuk persoalan menyisipkan elemen baru ke dalam
array yang sudah terurut. Misalnya dalam permainan kartu, kartu yang
dicabut biasanya disisipkan oleh pemain pada posisi yang tepat sehingga
penambahan kartu tersebut membuat semua kartu tetap terurut.
Misalkan kita memiliki suatu array dengan N maka pengurutan secara menaik dengan metode Insertion Sort sebagai berikut:
Langkah -1: elemen pertama Nilai[0] diasumsikan telah sesuai tempatnya.
Langkah -2: ambil elemen ke dua (Nilai[1]), cari lokasi yang tepat
pada Nilai[0..0] untuk Nilai Nilai[1]. Lakukan pergeseran ke kanan jika
Nilai[0..1] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut
menurun) dari Nilai[1]. Misalnya posisi yang tepat adalah j, maka
sisipkanlah Nilai[1] pada Nilai[j].
Langkah -3: ambil elemen ke tiga (Nilai[2]), cari lokasi yang tepat
pada Nilai[0..1] untuk Nilai[2]. Lakukan pergeseran ke kanan jika
Nilai[0..2] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut
menurun) dari Nilai[2]. Misalnya posisi yang tepat adalah j, maka
sisipkanlah Nilai[2] pada Nilai[j].
Langkah -4: ambil elemen ke empat (Nilai[3]), cari lokasi yang tepat
pada Nilai[0..3] untuk Nilai Nilai[3]. Lakukan pergeseran ke kanan jika
Nilai[0..2] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut
menurun) dari Nilai[3]. Misalnya posisi yang tepat adalah j, maka
sisipkanlah Nilai[3] pada Nilai[j].
…
Langkah –N: ambil elemen ke N (Nilai[N]), cari lokasi yang tepat pada
Nilai[0..N-1] untuk Nilai Nilai[N]. Lakukan pergeseran ke kanan jika
Nilai[0..N-1] lebih besar (untuk urut menaik) atau lebih kecil (untuk
urut menurun) dari Nilai[N]. Misalnya posisi yang tepat adalah j, maka
sisipkanlah Nilai[N] pada Nilai[j].
Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menaik dengan metode Insertion Sort: 25, 72, 30, 45,
20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut:
Langkah -1: Nilai[0] diasumsikan telah terurut.
Langkah -2: cari lokasi yang tepat untuk Nilai[1] pada Nilai[0..0].
Dalam hal ini, ternyata 72 tidak lebih besasr dari 25 maka tidak terjadi
pergeseran, sehingga diperoleh array seperti berikut:
Langkah -3: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..1].
Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1]
digeser ke kanan sehingga Nilai[2] di posisi ke 1, sehingga diperoleh
array sebagai berikut:
Langkah -4: cari lokasi yang tepat untuk Nilai[3] pada Nilai[0..2].
Dalam hal ini, ternyata lokasi yang tepat adalah 2, maka Nilai[2]
digeser ke kanan sehingga Nilai[3] di posisi ke 3, sehingga diperoleh
array seperti berikut:
Langkah -5: cari lokasi yang tepat untuk Nilai[4] pada Nilai[0..3].
Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0],
Nilai[1], Nilai[2], Nilai[3] digeser masing-masing satu posisi ke kanan
sehingga Nilai[4] di posisi ke 0, sehingga array seperti berikut:
Langkah -6: cari lokasi yang tepat untuk Nilai[5] pada Nilai[0..4].
Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0],
Nilai[1], Nilai[2], Nilai[3] dan Nilai[4] digeser masing-masing satu
posisi ke kanan sehingga Nilai[6] di posisi ke 0, diperoleh array
seperti berikut:
Langkah -7: cari lokasi yang tepat untuk Nilai[6] pada Nilai[0..5].
Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0],
Nilai[1], Nilai[2], Nilai[3], Nilai[4] dan Nilai[5] digeser
masing-masing satu posisi ke kanan sehingga Nilai[6] di posisi ke 0,
diperoleh array seperti berikut:
Langkah -8: cari lokasi yang tepat untuk Nilai[7] pada Nilai[0..6].
Dalam hal ini, ternyata lokasi yang tepat adalah 6, maka Nilai[6]
digeser satu posisi ke kanan sehingga Nilai[7] di posisi ke 6, diperoleh
array seperti berikut:
Selesai. Dan array telah terurut secara menaik. Program untuk
mengurutkan elemen array secara menaik dengan metode Insertion Sort
dapat dilihat pada program Lat_Sorting_07a.
/* Program Pengurutan Metode Insertion Sort
Pengurutan Secara Menaik
Nama File : Lat_Sorting_07a */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
int Nilai[20];
int i, j, k, N;
int temp;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
//Proses Cetak sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
//Proses Pengurutan
for(i=1; i<N; i++)
{
temp = Nilai[i];
j=i-1;
while((temp <= Nilai(j)) && (j>=1))
{
Nilai[j+1] = Nilai[j];
j--;
}
if(temp >= Nilai[j])
Nilai[j+1] = temp;
else
{
Nilai[j+1] = Nilai[j];
Nilai[j] = temp;
}
cout<<endl;
for(k=0; k<N; k++)
cout<<setw(3)<<Nilai[k];
}
//Proses Cetak Setelah diurutkan
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
getch();
}
Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan
diurutkan secara menurun dengan metode Insertion Sort: 25, 72, 30, 45,
20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut:
Langkah -1: Nilai[0] diasumsikan telah terurut
Langkah -2: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..0].
Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0]
digeser ke kanan satu posisi dan Nilai[1] menempati posisi ke 0,
sehingga diperoleh array seperti berikut:
Langkah -3: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..1].
Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1]
digeser satu posisi ke kanan sehingga Nilai[2] di posisi ke 1, sehingga
diperoleh array seperti berikut:
Langkah -4: cari lokasi yang tepat untuk Nilai[3] pada Nilai[0..2].
Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1] dan
Nilai[2] digeser satu posisi ke kanan sehingga Nilai[3] di posisi ke 1,
sehingga diperoleh array seperti berikut:
Langkah -5: cari lokasi yang tepat untuk Nilai[4] pada Nilai[0..3].
Dalam hal ini, ternyata lokasi yang tepat adalah 4, tapi karena oleh
dirinya sendiri maka tidak ada pergeseran, sehingga array seperti
berikut:
Langkah -6: cari lokasi yang tepat untuk Nilai[5] pada Nilai[0..4].
Dalam hal ini, ternyata lokasi yang tepat adalah 5, tapi karena oleh
dirinya sendiri maka tidak ada pergeseran, sehingga array seperti
berikut:
Langkah -7: cari lokasi yang tepat untuk Nilai[6] pada Nilai[0..5].
Dalam hal ini, ternyata lokasi yang tepat adalah 6, tapi karena oleh
dirinya sendiri maka tidak ada pergeseran, sehingga array seperti
berikut:
Langkah -8: cari lokasi yang tepat untuk Nilai[7] pada Nilai[0..6].
Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1],
Nilai[2], Nilai[3], Nilai[4], Nilai[5], Nilai[6] digeser satu posisi ke
kanan sehingga Nilai[7] di posisi ke 1, diperoleh array seperti berikut:
Selesai. Dan array telah terurut secara menaik. Program untuk
mengurutkan elemen array secara menaik dengan metode Insertion Sort
dapat dilihat pada program Lat_Sorting_07a.
//* Program Pengurutan Metode Insertion Sort
Pengurutan Secara Menurun
Nama File : Lat_Sorting_07b */
#include<iostream.h>
#include<conio.h>
#inlcude<iomanip.h>
void main()
{
int Nilai[20];
int i, j, k, N;
int temp;
//bool ketemu;
cout<<"Masukkan Banyak Bilangan : ";
cin>>N;
for(i=0; i<N; i++)
{
cout<<"Elemen ke-"<<i<<" : ";
cin>>Nilai[i];
}
//Proses Cetak Sebelum diurutkan
cout<<"\nData sebelum diurut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
//Proses Pengurutan
for(i=1; i<N; i++)
{
temp = Nilai[i];
j=i-1;
while((temp > Nilai[i]) && (j>=1))
{
Nilai[j+1] = Nilai[j];
j--;
}
if(temp <= Nilai[j])
Nilai[j+1] = temp;
else
{
Nilai[j+1] = Nilai[j];
Nilai[j] = temp;
}
cout<<endl;
for(k=0; k<N; k++)
cout<<setw(3)<<Nilai[k];
}
//Proses Cetak Setelah diurutkan
cout<<"\nData Setelah di urut : ";
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
getch();
}
Nama : A .MUH Alryan Pangeran Syamsibah
Nim : 200210502027
Kelas : Teknik Komputer B
