SORTING
Sorting adalah proses pengurutan atas sekumpulan data sejenis. Pengurutan dapat dilakukan dari yang terkecil hingga terbesar (ascending), maupun dari yang terbesar hingga terkecil (descending). Sorting dilakukan di dalam memori utama komputer (RAM), meskipun seluruh data yang disimpan sudah direkam di dalam memori eksternal, seperti hard disk. Hasil sorting itu selanjutnya bisa disimpan di memori eksternal tersebut.
Hingga saat ini, ratusan teknik sorting telah diperkenalkan orang. Beberapa teknik itu antara lain: (a) Bubble sort/ exchange sort, (b) Insertion sort, (c) Selection sort, (d) Shell sort, (e) Comb sort, (f) Merge sort, (g) Heapsort, (h) Quicksort, (i) Counting sort, (j) Bucket sort, (k) Radix sort, (l) Distribution sort, (m) Timsort, dan lain sebagainya.
TIGA TEKNIK DASAR
Ada dua hal utama yang menjonjol pada teknik sorting, yaitu banyaknya proses perbandingan data, dan banyaknya proses perpindahan tempat (penukaran posisi). Dari sekian banyak teknik sorting, berikut langkah-langkah tiga teknik utama sorting: sorting dilakukan secara ascending, dan datanya berupa angka.
Misalkan angkanya adalah: 8, 9, 1, 4, 2, 7, 3 yang akan diurut menjadi 1, 2, 3, 4, 7, 8, 9. Berikut tiga algoritmanya:
1. Teknik Bubble Sort atau Exchange Sort
Teknik sorting ini dilakukan dengan cara:
1. Dilakukan proses (pass) dari data pertama hingga satu data sebelum data terakhir;
2. Pada pass ke n, dibandingkan data ke n dengan elemen-elemen berikutnya, pada setiap perbandingan itu, tempatkan (saling tukar tempat) sehingga elemen yang lebih kecil diletakkan di posisi ke n;
3. Setiap akhir pass ke n akan akan ditempati oleh data yang tepat, yaitu urutan data terkecil ke n.
Pass 1:
Pada pass 1, nilai terkecil sudah ditempatkan di posisi pertama.
Pass 2:
Pada pass 2, nilai terkecil kedua sudah ditempatkan di posisi kedua
Pass 3:
Pada pass 3, nilai terkecil ketiga sudah ditempatkan di posisi ketiga
Pass 4:
Pada pass 4 ini, nilai terkecil keempat sudah ditempatkan di posisi keempat
Pass 5:
Pada pass 5, nilai terkecil kelima sudah ditempatkan di posisi kelima
Pass 6:
Pada pass 6, nilai terkecil keenam sudah ditempatkan di posisi keenam, dan otomatis nilai terbesar sudah berada di list terakhir.
Algoritmanya:
Algoritma 1: bubble sort
‘Proses memasukkan data
For I = 1 to 7
Input a(i)
Next i
‘proses pengurutan data
For I = 1 to 6
For j = i+1 to 7
If a(j) < a(i) then swap a(i), a(j)
Next j
Next i
‘Proses mencetak data
For I = 1 to 7
print a(i)
Next i
End
2. Teknik Insertion Sort
Jika pada teknik bubble sort di atas dapat dikatakan “posisi mencari angka yang tepat”, maka teknik insertion sort ini adalah “angka mencari posisi yang tepat.” Teknik sorting ini dilakukan dengan cara:
1. Lakukan proses (pass) yang dimulai dari elemen kedua hingga elemen terakhir;
2. Bandingkan elemen ke n dengan elemen sebelumnya (n-1). Bila elemen ke n sudah lebih besar, maka perbandingan pada pass ke n ini selesai. Bila elemen ke n lebih kecil, saling tukar posisi datanya, dan lanjutkan perbandingan ke elemen sebelumnya hingga elemen itu tidak lebih kecil dari elemen sebelumnya.
Berikut ilustrasinya:
Pass 1:
Pass 2:
Pass 3:
Pass 4:
Pass 5:
Algoritma 2: insertion sort
‘Proses memasukkan data
For I = 1 to 7
Input a(i)
Next i
‘proses pengurutan data
For I = 2 to 7 : x = i
For j = i-1 to 1 step -1
If a(x) < a(j) then swap a(x), a(j)
X = j
Next j
Next i
‘Proses mencetak data
For I = 1 to 7
print a(i)
Next i
End
3. Teknik Selection Sort
Jika pada teknik bubble sort di atas dapat dikatakan “posisi mencari angka yang tepat”, dan teknik insertion sort ini adalah “angka mencari posisi yang tepat,” maka pada selection sort dapat dikatakan “cari angka terkecil, tempatkan di posisi yang tepat”. Berikut langkah-langkahnya (dengan flag =”kecil”).
Teknik sorting ini dilakukan dengan cara:
1. Baca elemen pertama (n), anggap ia yang terkecil;
2. Bandingkan dengan seluruh elemen yang ada. Setiap perbandingan, elemen yang lebih kecil dianggap sebagai elemen terkecil. Selesai perbandingan itu, elemen terkecil itu diletakkan di elemen pertama.
3. Lanjutkan dengan elemen kedua (n+1) yang dibandingkan dengan elemen-elemen berikutnya, lakukan seperti langkah 1 dan 2, dan seterusnya hingga elemen ke n-1.
Algoritmanya:
Algoritma 11.3: selection sort
‘Proses memasukkan data
For I = 1 to 7
Input a(i)
Next i
‘proses pengurutan data
For I = 1 to 6
Kecil = a(i)
For j = i+1 to 7
If a(j) < kecil then kecil = a(j): pos = j
Next j
x = a(i)
a(i) = kecil
a(pos) = x
Next i
‘Proses mencetak data
For I = 1 to 7
print a(i)
Next i
End
Selanjutnya, silakan Saudara buat program untuk sortingnya sesuai dengan bahasa pemrograman yang Saudara sukai.
TEKNIK SORTING LAIN
1. Heapsort
Heapsort adalah teknik pengurutan yang memanfaatkan binary tree yang berjenis complete (almost complete) binary tree. Algoritmanya sederhana, misalnya untuk pengurutan yang bersifat descending, yaitu (1) masukkan elemen pertama sebagai root, (2) arahkan elemen berikutnya ke posisi node baru yang memenuhi syarat complete binary tree, yaitu disusun dari atas ke bawah dan dari kiri ke kanan. Jika node yang sedang dikunjungi nilainya lebih kecil, tempati posisinya, dan geser nilai node tersebut di node berikutnya secara rekursif. Lakukan langkah (2) ini hingga seluruh elemen telah menempati posisinya.
Contoh, kita akan mengurutkan bilangan-bilangan ini: 5, 9, 1, 8, 4, 7, 2 secara descending dengan heapsort. Maka langkah-langkah pembentukan pohon binarnya adalah:
Elemen pertama (5) dijadikan root. Dipersiapkan node baru untuk elemen berikutnya sesuai dengan kaidah pohon binar lengkap.
Elemen kedua (9) dibandingkan dengan root-nya. Karena lebih besar, maka 9 diletakkan di root-nya, dan 5 diletakkan di node baru. Disiapkan node baru berikutnya.
Elemen ketiga (1) dibandingkan dengan root-nya, karena lebih kecil, maka ia diletakkan di node barunya. Disiapkan node baru berikutnya, tetap sesuai kaidah pohon binar lengkap.
Elemen keempat (8) diarahkan ke node baru sambil dibandingkan mulai dari root. Pertama, dibandingkan dengan 9, karena lebih kecil, berlanjut bandingkan dengan 5, karena 8 lebih besar, ia menempati lokasinya, nilai 5 dipindahkan ke node baru. Siapkan node baru berikutnya.
Elemen kelima (4) diarahkan ke node baru sambil dibandingkan mulai dari root. Pertama, dibandingkan dengan 9, karena lebih kecil, berlanjut dibandingkan dengan 8, karena lebih kecil, ia menempati node barunya. Siapkan node baru berikutnya.
Elemen keenam (7) diarahkan ke node baru sambil dibandingkan mulai dari root. Pertama, dibandingkan dengan 9, karena lebih kecil, berlanjut bandingkan dengan 1, karena 7 lebih besar, ia menempati lokasinya, nilai 1 dipindahkan ke node baru. Siapkan node baru berikutnya.
Terakhir, elemen ketujuh (2) diarahkan ke node baru sambil dibandingkan mulai dari root. Pertama, dibandingkan dengan 9, karena lebih kecil, berlanjut dibandingkan dengan 7, karena lebih kecil, ia menempati node barunya.
Selanjutnya, untuk menentukan hasil, caranya: (1) keluarkan root-nya sebagai hasil, lalu tempatnya diganti oleh ‘anak’nya yang lebih besar, (2) posisi ‘anak’nya yang kosong, ditempati oleh ‘anaknya’ yang lebih besar, demikian seterusnya. Berikut penggambarannya:
Pertama, keluarkan 9 menjadi hasil. Tempat 9 akan ditempati oleh 8 (anak terbesarnya), dan posisi 8 akan ditempati oleh 5 (anaknya yang terbesar). Hasil: 9
Kedua, keluarkan 8 menjadi hasil. Tempat 8 akan ditempati oleh 7 (anak terbesarnya), dan posisi 7 akan ditempati oleh 2 (anaknya yang terbesar). Hasil: 9, 8
Ketiga, keluarkan 7 menjadi hasil. Tempat 7 akan ditempati oleh 5 (anak terbesarnya), dan posisi 5 akan ditempati oleh 4 (anaknya yang terbesar). Hasil: 9, 8, 7
Keempat, keluarkan 5 menjadi hasil. Tempat 5 akan ditempati oleh 4 (anak terakhirnya). Hasil: 9, 8, 7, 5
Kelima, keluarkan 4 menjadi hasil. Tempat 4 akan ditempati oleh 2 (anak terabesarnya). Posisi 2 akan ditempati oleh 1. Hasil: 9, 8, 7, 5, 4
Keenam, keluarkan 2 menjadi hasil. Tempat 2 akan ditempati oleh 1 (anak terakhirnya). Hasil: 9, 8, 7, 5, 4, 2
Terakhir, keluarkan root menjadi hasil. Hasil = 9, 8, 7, 5, 4, 2, 1
2. Merge Sort
Ini mungkin hanya tinggal sejarah atau sangat sedikit yang memiliki kasus seperti ini. Misalnya, di hard disk saya ada file data yang akan diurut yang berisi 1 juta records, sedangkan tempat untuk melakukan sorting adalah di memori utama komputer (RAM) yang kebetulan hanya mampu menampung 200.000 records, maka saya harus melakukan sesuatu (strategi) agar seluruh records itu bisa diurut.
Ada banyak strategi, misalnya, membagi-bagi file tersebut (divide process) menjadi 5 file yang masing-masing berisi 200.000 records. Selanjutnya, setiap file tersebut dilakukan pengurutan (conquer process) dengan salah satu teknik di atas. Setelah seluruh file sudah terurut recordsnya, kemudian dilakukan merge (gabung sekaligus urut). Misalnya, diambil masing-masing 1 record dari file I, II, III, IV, dan V, record yang ‘nilai’nya terkecil (pada pengurutan ascending) disimpan di file baru (tempat menyimpan hasil terakhir).
Demikian seterusnya diambil satu per satu record dari setiap file secara bergantian untuk dibandingkan dengan record dari files lainnya. Berikut gambarannya (setiap elemen data dianggap sebuah record):
Records di File X = 10, 43, 34, 67, 11, 78, 12, 17, 15, 13, 16, 22, 27, 33, 99, 87, 14, 89, 32, 9, 56
Misalkan, RAM kita hanya mampu menampung 5 records yang akan disorting, maka file X kita itu dibagi-bagi menjadi 5 files lain (cara mambaginya boleh denganberbagai cara), di sini dimisalkan:
File A berisi: 10, 43, 34, 67, 11
File B berisi: 78, 12, 17, 15, 13
File C berisi: 16, 22, 27, 33, 99
File D berisi: 87, 14, 89, 32, 9
File E berisi: 56
Selanjutnya, setiap file kita sort menggunakan salah satu teknik sorting di atas, sehingga hasilnya:
File A berisi: 10, 11, 34, 43, 67
File B berisi: 12, 13, 15, 17, 78
File C berisi: 16, 22, 27, 33, 99
File D berisi: 9, 14, 32, 87, 89
File E berisi: 56
Kemudian, kita masukkan satu record dari masing-masing file, untuk selanjutnya nilai yang terkecil kita simpan di file Y (penampung akhir), atau boleh juga kita re-write di file X sebelumnya.
Karena yang menjadi nilai terkecil adalah record dari file D, maka kita masukkan kembali satu record berikutnya dari file D:
Karena yang menjadi nilai terkecil adalah record dari file A, maka kita masukkan kembali satu record berikutnya dari file A:
Demikian seterusnya hingga seluruh data telah selesai diproses. Teknik merge seperti ini bukan satu-satunya cara. Ada cara lain seperti membuat bagan pertandingan, perbandingan hingga menghasilkan ‘pemenang’ (untuk ascending: nilai terkecil) ini dilakukan berulang-ulang (rekursif) hingga seluruh datanya terurut, berikut gambarannya:
Sebagai latihan untuk Anda, silakan kerjakan masalah di atas jika RAMnya hanya mampu menampung 3 records, boleh dengan berapapun input maupun output file yang digunakan pada prosesnya, yang penting hasil akhirnya sudah merupakan record terurut dalam sebuah file.
3. Quick Sort
Teknik pengurutan ini melakukan pembagian sekumpulan elemen data menjadi dua bagian secara rekursif (berulang-ulang). Teknik pembagian itu bisa bermacam-macam, yang jelas (intinya) akan ditentukan satu elemen data (disebut dengan pivot) sebagai pembatasnya, yang di sebelah kiri pivot akan berisi elemen-elemen data yang lebih kecil dari pivotnya. Sedangkan yang di sebelah kanan pivot akan berisi elemen-elemen data yang lebih besar atau sama dengan pivotnya. Pengambilan bilangan pivot dapat dilakukan dengan berbagai cara, misalnya dengan elemen pertama, elemen terakhir, elemen yang berada di posisi tengah, dan sebagainya.
Berikut ilustrasinya: 12, 34, 22, 8, 9, 4, 2, 10, 5, 20, 17
Diambil sebagai bilangan pivotnya adalah angka pertama: 12. Dengan cara membandingkan seluruh elemen dengan bilangan pivotnya, maka susunan pertama setelah pivot menempati tempatnya adalah:
8, 9, 4, 2, 10, 5, (12), 34, 22, 20, 17 …… (1)
Selanjutnya (dengan cara yang sama/ rekursif), di bagian kiri dari pivot, dipilih pivot baru, misalkan bilangan pertama yaitu 8, maka setelah dilakukan perbandingan seluruh elemen dengan bilangan pivotnya, susunan di bagian kiri itu akan menjadi:
4, 2, 5, (8), 9, 10 …… (2)
Selanjutnya, ulang lagi, di bagian kiri dari pivot, dipilih pivot baru, misalkan bilangan pertama yaitu 4, maka susunan di bagian kiri itu akan menjadi:
2, (4), 5 (sudah terurut)
Lanjutkan ke seluruh bagian yang belum diproses, misalnya jika kita kembali ke (1), di kanan pivot kita ambil elemen pertama sebagai nilai pivot baru, yaitu 34, maka susunannya akan menjadi:
22, 20, 17, (34) ….. (3)
Dilanjutkan lagi, kita ambil nilai pivot baru adalah elemen pertama, yaitu 22. Susunan-nya menjadi:
20, 17, (22)
Dilanjutkan lagi dengan nilai pivot 20. Susunannya menjadi:
17, 20 (sudah terurut)
Demikian seterusnya, setelah masing-masing bagian telah terurut, digabung kembali. Sekilas mirip dengan merge sort di atas. Silakan Anda buat algoritma atau programnya.
4. Shell Sort
Teknik ini melakukan sorting menggunakan jarak-jarak tertentu (bebas ditentukan dengan jarak berapa) hingga akhirnya berjarak 1. Sebagai contoh untuk data: 12, 34, 22, 8, 9, 4, 2, 10, 5, 20, 17 (ada 11 data, dan ditentukan jarak-jaraknya adalah 5, 3 dan 1), maka ilustrasinya sebagai berikut:
Gambar 1. Susunan elemen data awal yang akan disorting
Karena jarak yang ditentukan adalah 5, maka:
Gambar 2 Elemen-elemen data yang akan disorting dengan jarak 5 (pertama)
urutkan data (1), (6), dan (11), hasilnya:
Gambar 3 Elemen-elemen data yang akan disorting dengan jarak 5 (kedua)
Dari gambar 3, akan diurutkan data (2), dan (7), hasilnya:
Gambar 4 Elemen-elemen data yang akan disorting dengan jarak 5 (ketiga)
Dari gambar 4, akan diurutkan data (3) dan (8), hasilnya:
Gambar 5 Elemen-elemen data yang akan disorting dengan jarak 5 (keempat)
Dari gambar 5, akan diurutkan data (4) dan (9), hasilnya:
Gambar 6 Elemen-elemen data yang akan disorting dengan jarak 5 (kelima)
Dari gambar 6, akan diurutkan data (5) dan (10), hasilnya tetap karena urutannya sudah sesuai.
Gambar 7 Elemen-elemen data yang akan disorting dengan jarak 3 (pertama)
Karena jarak berikutnya yang ditentukan adalah 3, maka di gambar 7 dilakukan pengurutan data (1), (4), (7), dan (10), hasilnya:
Gambar 8 Elemen-elemen data yang akan disorting dengan jarak 3 (kedua)
Diurutkan data (2), (5), (8), dan (11), hasilnya:
Data (4) dibandingkan dengan data (7): 5 dibandingkan dengan 20, tetap
Data (7) dibandingkan dengan data (10), 20 dibandingkan dengan 34, tetap
Data (5) dibandingkan dengan data (8): 9 dibandingkan dengan 17, tetap.Data (8) dibandingkan dengan data (11): 17 dibanding dengan 22, tetap
Data (6) dibandingkan dengan data (9): 8 dibandingkan dengan 12, tetap
Selanjutnya dilakukan dengan jarak 1, maka akan dibandingkan:
Data (1) dibandingkan dengan data (2) : 4 dibandingkan dengan 2, tukar posisinya
Data (2) dibandingkan dengan data (3) : 4 dibandingkan dengan 10, tetap
Data (3) dibandingkan dengan data (4): 10 dibandingkan dengan 5, tukar posisinya
Data (4) dibandingkan dengan data (5): 10 dibandingkan dengan 9, tukar posisinya
Data (5) dibandingkan dengan data (6): 10 dibandingkan dengan 8, tukar posisinya
Data (6) dibandingkan dengan data (7): 10 dibandingkan dengan 20, tetap
Data (7) dibandingkan dengan data (8): 20 dibandingkan dengan 17, tukar posisinya
Data (8) dibandingkan dengan data (9): 20 dibandingkan dengan 12, tukar posisinya
Data (9) dibandingkan dengan data (10): 20 dibandingkan dengan 34, tetap
Data (10) dibandingkan dengan data (12): 34 dibandingkan dengan 22, tukar posisinya
Hasilnya: 2, 4, 5, 8, 9, 10, 12, 17, 20, 22, 34
Jadi, seberapa cepat sorting dapat dilakukan tergantung dari (1) berapa banyak data yang akan disorting, (2) seberapa besar memori utama yang akan digunakan untuk melakukan sorting, (3) teknik sorting apa yang akan digunakan, dan (4) susunan data yang akan disorting. Ada dua hal yang mempengaruhi algoritma dalam melakukan sorting (waktu sorting), yaitu banyaknya jumlah perbandingan data dan banyaknya jumlah penukaran tempat.
Ada tiga keadaan yang berkaitan dengan waktu sorting, yaitu:
1. Best case, yaitu saat terbaik (jumlah perbadingan dan penukaran tempatnya paling sedikit), biasanya susunan datanya sesuai dengan urutan data yang diinginkan, misalkan susunan datanya 1, 2, 3, 4, 5 dan akan diurut secara ascending;
2. Worst case, yaitu saat terburuk (jumlah perbadingan dan penukaran tempatnya paling banyak), biasanya ketika susunan data terbalik dengan urutan yang diinginkan; misalkan susunan datanya 1, 2, 3, 4, 5 dan akan diurut secara descending;
3. Average case, yaitu saat terbaik (jumlah perbadingan dan penukaran tempatnya paling sedikit).
TUGAS
Buat program animasi Sorting dengan menu seperti gambar dibawah ini
Ket :
INSERT DATA : menambah data pada array
INSERTION SORT : Sorting data menggunakan algoritma Insertion
SELECTION SORT : Sorting data menggunakan algoritma Selection
BUBBLE SORT : Sorting data menggunakan algoritma Bubble Sort
EXIT :Keluar/selesai
Tampilan menu :
SORTING DATA ARRAY
==========================
1. INSERT DATA ARRAY
2. INSERTION SORT
3. SELECTION SORT
4. BUBBLE SORT
5. EXIT
Pilihan (1 – 5)
Program menu sorting :
#include<time.h>
#include<iostream>
#include<conio.h>
#include<windows.h>
using namespace std;
int main() {
int pil;
cout << "======= Program Sorting (Bubble, Insertion, Selection) =========="<<endl<<endl;
cout << "1. Bubble sort" <<endl;
cout << "2. Insertion sort" <<endl;
cout << "3. Selection sort" <<endl<<endl;
cout << "==============================="<<endl<<endl;
cout << "Masukan pilihan anda = "; cin >> pil;
switch(pil) {
////////////////////////////////////
//// Buble start /////////////
////////////////////////
case 1:
system("cls");
cout << endl;
cout << "Bubble sort"<<endl;
cout << "=============="<<endl;
int t1,t2;
int hold;
int array[5];
cout<<"Masukan 5 angka :"<<endl;
for(int i=0; i<5; i++) {
cout << " angka ke " <<i+1 <<" = ";cin>>array[i];
}
cout<<endl;
cout<<endl;
t1=GetTickCount();
cout<<"Sebelum di sortir = ";
for(int j=0; j<5; j++) {
cout<<array[j];
cout<<" ";
}
cout<<endl;
cout <<endl<< "Urutan program"<<endl;
for(int i=0; i<4; i++) {
for(int j=0; j<4; j++) {
if(array[j]<array[j+1]) {
hold=array[j];
array[j]=array[j+1];
array[j+1]=hold;
for(int i=0; i<5; i++) {
cout<<array[i]<<" ";
}
cout<<endl;
}
}
}
cout<<endl;
cout<<"Setelah di sortir = ";
for(int i=0; i<5; i++) {
cout<<array[i]<<" ";
}
cout<<endl;
t2=GetTickCount();
cout << endl <<"Lama proses = " << (int)(t2 - t1) << " ms";
cout<<endl;
break;
//////////////////////////////////////////////////////////
/////// Insertion start /////////
////////////////////////////////////////////////
case 2:
system("cls");
cout << "Insertion sort";
cout <<endl<<"============="<<endl;
cout<<endl;
int t3,t4;
int Key;
int array1[5];
cout<<"Masukan 5 angka : "<<endl;
for(int i=0; i<5; i++) {
cout << " angka ke " <<i+1 <<" = ";cin>>array1[i];
}
cout<<endl;
t3=GetTickCount();
cout<<"Angka sebelum di sortir = ";
for(int j=0; j<5; j++) {
cout<<array1[j]<<" ";
}
cout<<endl;
cout<<endl<< "Data proses "<<endl;
for(int j=1 ; j < 5 ; j++) {
Key = array1[j];
int i = j-1;
while(i >= 0 && array1[i] < Key) {
array1[i + 1] = array1[i];
i = i - 1;
}
array1[i + 1] = Key;
for(int l=0; l<5; l++) {
cout<<array1[l]<<" ";
}
cout<<endl;
}
cout<<endl<<"Angka setelah disortir = ";
for(int i=0; i<5; i++) {
cout<<array1[i]<<" ";
}
t4=GetTickCount();
cout << endl<<endl <<"Lama proses = " << (int)(t4 - t3) << " ms";
cout<<endl;
break;
////////////////////////////////////////////////////////
////////////// Selection start /////////////////////
///////////////////////////////////// case 3:
system("cls");
cout << "Selection sort";
cout <<endl<< "================="<<endl<<endl;
int t5,t6;
int arr[5];
int mini,temp;
cout<<"masukan 5 angka ="<<endl;
for(int i=0; i<5; i++) {
cout << " angka ke " <<i+1 <<" = ";cin>>arr[i];
}
t5=GetTickCount();
cout<<endl;
cout<<"Angka sebelum di sortir = ";
for(int j=0; j<5; j++) {
cout<<arr[j]<<" ";
}
for(int r1=0;r1<4;r1++) {
mini=r1;
for(int r2=r1+1; r2<5; r2++)
if(arr[r2]>arr[mini])
mini=r2;
if(mini !=r1) {
temp=arr[r1];
arr[r1]=arr[mini];
arr[mini]=temp;
}
}
cout<<endl;
cout<<endl;
cout<<"Setelah di sortir = ";
for(int q=0; q<5; q++) {
cout<<arr[q]<< " " ;
}
t6=GetTickCount();
cout << endl<<endl <<"Lama proses = " << (int)(t6 - t5) << " ms";
cout<<endl;
break;
//////////////////////////////////////////
////// PILIHAN TIDAK ADA /////////
////////////////////////////////////////// default:
system("cls");
cout << "Pilihan tidak ada";
break;
} getch();
}
#include<iostream>
#include<conio.h>
#include<windows.h>
using namespace std;
int main() {
int pil;
cout << "======= Program Sorting (Bubble, Insertion, Selection) =========="<<endl<<endl;
cout << "1. Bubble sort" <<endl;
cout << "2. Insertion sort" <<endl;
cout << "3. Selection sort" <<endl<<endl;
cout << "==============================="<<endl<<endl;
cout << "Masukan pilihan anda = "; cin >> pil;
switch(pil) {
////////////////////////////////////
//// Buble start /////////////
////////////////////////
case 1:
system("cls");
cout << endl;
cout << "Bubble sort"<<endl;
cout << "=============="<<endl;
int t1,t2;
int hold;
int array[5];
cout<<"Masukan 5 angka :"<<endl;
for(int i=0; i<5; i++) {
cout << " angka ke " <<i+1 <<" = ";cin>>array[i];
}
cout<<endl;
cout<<endl;
t1=GetTickCount();
cout<<"Sebelum di sortir = ";
for(int j=0; j<5; j++) {
cout<<array[j];
cout<<" ";
}
cout<<endl;
cout <<endl<< "Urutan program"<<endl;
for(int i=0; i<4; i++) {
for(int j=0; j<4; j++) {
if(array[j]<array[j+1]) {
hold=array[j];
array[j]=array[j+1];
array[j+1]=hold;
for(int i=0; i<5; i++) {
cout<<array[i]<<" ";
}
cout<<endl;
}
}
}
cout<<endl;
cout<<"Setelah di sortir = ";
for(int i=0; i<5; i++) {
cout<<array[i]<<" ";
}
cout<<endl;
t2=GetTickCount();
cout << endl <<"Lama proses = " << (int)(t2 - t1) << " ms";
cout<<endl;
break;
//////////////////////////////////////////////////////////
/////// Insertion start /////////
////////////////////////////////////////////////
case 2:
system("cls");
cout << "Insertion sort";
cout <<endl<<"============="<<endl;
cout<<endl;
int t3,t4;
int Key;
int array1[5];
cout<<"Masukan 5 angka : "<<endl;
for(int i=0; i<5; i++) {
cout << " angka ke " <<i+1 <<" = ";cin>>array1[i];
}
cout<<endl;
t3=GetTickCount();
cout<<"Angka sebelum di sortir = ";
for(int j=0; j<5; j++) {
cout<<array1[j]<<" ";
}
cout<<endl;
cout<<endl<< "Data proses "<<endl;
for(int j=1 ; j < 5 ; j++) {
Key = array1[j];
int i = j-1;
while(i >= 0 && array1[i] < Key) {
array1[i + 1] = array1[i];
i = i - 1;
}
array1[i + 1] = Key;
for(int l=0; l<5; l++) {
cout<<array1[l]<<" ";
}
cout<<endl;
}
cout<<endl<<"Angka setelah disortir = ";
for(int i=0; i<5; i++) {
cout<<array1[i]<<" ";
}
t4=GetTickCount();
cout << endl<<endl <<"Lama proses = " << (int)(t4 - t3) << " ms";
cout<<endl;
break;
////////////////////////////////////////////////////////
////////////// Selection start /////////////////////
///////////////////////////////////// case 3:
system("cls");
cout << "Selection sort";
cout <<endl<< "================="<<endl<<endl;
int t5,t6;
int arr[5];
int mini,temp;
cout<<"masukan 5 angka ="<<endl;
for(int i=0; i<5; i++) {
cout << " angka ke " <<i+1 <<" = ";cin>>arr[i];
}
t5=GetTickCount();
cout<<endl;
cout<<"Angka sebelum di sortir = ";
for(int j=0; j<5; j++) {
cout<<arr[j]<<" ";
}
for(int r1=0;r1<4;r1++) {
mini=r1;
for(int r2=r1+1; r2<5; r2++)
if(arr[r2]>arr[mini])
mini=r2;
if(mini !=r1) {
temp=arr[r1];
arr[r1]=arr[mini];
arr[mini]=temp;
}
}
cout<<endl;
cout<<endl;
cout<<"Setelah di sortir = ";
for(int q=0; q<5; q++) {
cout<<arr[q]<< " " ;
}
t6=GetTickCount();
cout << endl<<endl <<"Lama proses = " << (int)(t6 - t5) << " ms";
cout<<endl;
break;
//////////////////////////////////////////
////// PILIHAN TIDAK ADA /////////
////////////////////////////////////////// default:
system("cls");
cout << "Pilihan tidak ada";
break;
} getch();
}
