Tugas Analisa Algoritma
June 13, 2009
Buat sebuah program yang bisa mengecek pernyataan dalam paper ini. Yaitu bahwa insertion sort lebih cepat dari selection sort, dan selection sort lebih cepat dari bubble sort walaupun kompleksitasnya sama.
Skenario program adalah sebagai berikut:
- Program generate bilangan random dengan banyak sesuai yang diinputkan user
- Simpan bilangan2 tsb dalam array saja
- Urutkan data dengan 3 algoritma di atas dan langkah dihitung dengan menggunakan aturan penghitungan running time yang telah dibahas.
- Urutkan lagi data2 di atas tanpa disertai penghitungan langkah, namun dihitung banyak waktu yang dihabiskan oleh tiap algoritma
- Dimasukkan data sebanyak 10, 50, 100, 200, 300, dst
- Catat tiap hasil yang dikeluarkan untuk tiap inputan
- Untuk lebih jelasnya, urutan tampilan program adalah sbg berikut
Generate data sebanyak: 10
Data telah digenerate dengan hasil:
13 40 21 22 6 78 9 5 12 1
Yakin akan memproses data tersebut? Y
Penghitungan banyak langkah dengan bubble sort selesai
1 5 6 9 12 13 21 22 40 78
Penghitungan banyak langkah dengan selection sort selesai
1 5 6 9 12 13 21 22 40 78
Penghitungan banyak langkah dengan insertion sort selesai
1 5 6 9 12 13 21 22 40 78
Penghitungan waktu bubble sort selesai
1 5 6 9 12 13 21 22 40 78
Penghitungan waktu selection sort selesai
1 5 6 9 12 13 21 22 40 78
Penghitungan waktu insertion sort selesai
1 5 6 9 12 13 21 22 40 78
Hasil:
Banyak langkah bubble sort: 123
Banyak langkah selection sort: 120
Banyak langkah insertion sort: 100
Waktu bubble sort: 0.5 detik
Waktu selection sort: 0.45 detik
Waktu insertion sort: 0.4 detik
Catat tiap hasil ke dalam tabel dan grafik. Buat laporan hasil analisanya. Tugas bisa dikerjakan dengan bahasa apapun, namun direkomendasikan C. Jika ada yang kurang jelas silakan ditanyakan. Selamat mengerjakan…..
Entry Filed under: Tip & Trik. .
18 Comments Add your own
Leave a Comment
Some HTML allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>
Trackback this post | Subscribe to the comments via RSS Feed
1.
Uji Nadhriyatul H | June 20, 2009 at 9:47 am
Bu…Tugasnya tuch gimana???
2.
tutus L | June 22, 2009 at 3:11 am
Maaf Bu ??Saya gak Mudeng Maksudnya,Meski kemaren sempat Ngikutin! Habis Sript/Syntax nya Ada yang Ditambah2in ?Spidolnya ngacow Lagi ?
Dan Saya yakin 99% anak semester 4 merasakan Hal Yang Sama ??:-)
Wassalam
3.
tutus L | June 22, 2009 at 3:16 am
Ops . . . . . . .. ???
Monggo Bu Pinarak Dateng Mhs-Pean
4.
riza | June 22, 2009 at 6:46 am
Langkah pertama, user diminta memasukkan suatu bilangan. Kalau sudah, maka dibuat bilangan sebanyak yang dimasukkan user tadi. Misal user memasukkan 5, maka program membuat bilangan sebanyak 5 namun besarnya tidak teratur karena dibuat secara acak. Misal: 9 4 7 5 2 atau 13 9 67 2 1. Setelah itu copy data itu ke 6 array. Tiap array diurutkan dengan berbagai macam metode sorting yang dipilih(bubble, selection, insertion). Misal array1 diurutkan dengan bubblesort sambil dihitung langkahnya, array2 diurutkan dengan selectionsort sambil dihitung langkahnya, array3 diurutkan dengan insertionsort sambil dihitung langkahnya, array4 diurutkan dengan bubblesort tanpa dihitung langkahnya tapi dihitung lama sorting dilakukan, array5 diurutkan dengan selectionsort tanpa dihitung langkahnya tapi dihitung lama sorting dilakukan dan array6 diurutkan dengan insertionsort tanpa dihitung langkahnya tapi dihitung lama sorting dilakukan.
Catat data yang diperoleh. Sajikan dalam bentuk tabel dan grafik. Buat analisa dari data yang diperoleh. Kalau belum paham juga, baca artikel dan komen ini berulang2 sambil minum teh pagi2 (rileks). So… you’ll find that it’s easy! Tugasnya mudah koq. Selamat mencoba
5.
amburadol | June 28, 2009 at 12:59 pm
Bu,
tolong di upload fotokopian yang kemaren, MAHASIWAx banyak yg g’ punya
sekalian dikasih contoh hasil programx
G’ MUDENG BLAZZZZZZ…. BU……
MAHASISWAne g’ no sing ngerti bu, mek YOGI thok…
6.
yogi'e bgt'z | June 29, 2009 at 9:13 am
askum, . . ,
saYA Td ud cobA BWt yg paKE MENghitung BNYk LANGKah. . ,
tP STLh q utaK Utek kuQ TRuz. .,
hasiLE Tu bubbLE SORt LBh sediKit LANGkahY DR pd seLECTION,
Tp kL MsLH WKtu seLECTion LBH CPEt,
n dr k-3 Sort aLGORitmAY INSertion adLH YG PaLENG UNgguL, . .
Po hasiLE KYk gto da bnER Bu, . ,?
7.
Tutus Laksono | June 30, 2009 at 12:18 pm
Ok!lah akan Tak coba??? Tar malem Sambil Nunggu Anaku Bobok
,Habis Penasaran . . . . . . . ?
Tapi sebisa Saya ya bu. . . . ??
8.
riza | July 1, 2009 at 2:14 am
@ amburadol
paper ada di link di baris paling atas artikel ini. jangan memfitnah tmn2 yg lain, mereka pasti mudheng tapi diam aja
@ yogi’e bgt’z
secara teori, lama bubble > selection > insertion, namun itu tdk berlaku pada kasus2 tertentu seperti worst case atau yg lain. Makanya dicoba yang banyak, misal memasukkan inputan 100 sebanyak 10 kali. Trus hasilnya dirata2. Atau mungkin cara menghitung langkahnya blum tepat. Kalau jumlah langkah lebih banyak mestinya waktunya juga lebih banyak. Btw kalau hasilnya kyk gitu berarti sdh ada pencerahan, statement di paper sdh hampir terbukti.
@ Tutus Laksono
Ok, selamat mencoba. Moga berhasil.
9.
riza | July 1, 2009 at 2:23 am
O ya, supaya lebih akurat hasilnya bisa coba dikerjakan dgn bahasa lain. Kemarin sy coba dgn delphi, tapi baru bubblesort. Kalau ada yg mau neruskan hubungi saya dengan mereply komen ini. Ntar tak kirimi sourcenya.
10.
yogi'e bgt'z | July 1, 2009 at 6:14 am
Sami MaWon bU,
PUn kuLO CUbi berKaLi2 haSiLe samA Ja kuQ BU.,
Utk perHTungan LGkh seLECTION>BubbLE>insertiON,
Utk yg perhituNgAN wakTU UD MAknyuZ,
Ud sesUAi DGn Yg dipAPER bu, . ,
tLG DiupLOAD DUnk bu sourcE COde seLECTion sort bwt NGitung LANgkah, . ,
puNYAQ KUq kyK Gni. . ,
bwT BHan prBANdingan gtU BU,. .
11.
yogi'e bgt'z | July 1, 2009 at 6:23 am
ATo mgkN Tu keLEBihanE SELECtion SORt bU. ,
WAktuNe Lbh cpet tp LANGKahe bnyAK. . ,
Bu Riza GDa LAptop2 yg NGAngUR Ta bU, . .,
NGerjaKAn gdA KompterE TrnyATA BinuN BGt bU, . ,
HE He hE HE, . ,
12.
alijenggot | July 1, 2009 at 7:37 pm
#include //Diperlukan untuk input / output
#include //Merandom waktu bilangan
#include //Berfungsi merandom
#include
#include //diperlukan dalam penghitungan waktu
#include //diperlukan dalam penghitungan perdetik
void main()
{
srand(time(0)); //Mengambil bilangan perwaktu
int a[50], a1[50], a2[50], a3[50]; //Variable random output/ ke array
int b; //Variable Input
int c;
int i, j;
int temp;
acak: //acak subroutine
cout <> b; //Memasukkan nilai input
cout <<endl;
cout << "Data telah digenerate dengan hasil:\n"; //Prompt
cout <= 1 && b <= 50) //Cek lebih besar dari 1 dan kurang dari 50
{
for(i = 0; i < b; i++) //Output nomor acak sampai jumlah dimasukan oleh pengguna
{
a[i] = (rand() % 50) + 1; //Membuat variabel acak angka, yang membuatnya + 1 sehingga 1 +
a1[i] = a[i], //Menyimpan output random ke array bubble sort
a2[i] = a[i], //Menyimpan output random ke array selection sort
a3[i] = a[i], //Menyimpan output random ke array Insertion sort
cout << a[i] << " "; //hasil output random
}
}
else
{
goto acak; //apabila input salah maka kembali ke acak
}
{
// Penghitungan dengan bubble sort
for(i=0;i<b;i++)
for(j=0; ja1[j+1]) //Proses Pertukaran sorting ascending
{
temp=a1[j];
a1[j]=a1[j+1];
a1[j+1]=temp;
}
cout<<endl<<endl;
cout << "Penghitungan dengan bubble sort :\n";
cout <<endl;
for(i=0; i<b; i++) // pengurutan sorting ascending
cout << a1[i] << " "; // Output bubble sort
cout<<endl<<endl;
}
// Penghitungan dengan Selection sort
for(i=0;i<(b-1);i++)
for(j=i+1;j*(a2+j))
{
temp=*(a2+i);
*(a2+i)=*(a2+j);
*(a2+j)=temp;
}
}
cout << "Penghitungan dengan selection sort:\n";
cout <<endl;
for(i=0;i<(b);i++) // Pengurutan nilai dari yang terkecil
cout<<a2[i]<<" "; // Output selection sort
cout<<endl<<endl;
{
// Penghitungan dengan Insertion sort
for (i = 1; i 0 && a3[j - 1] > c; –j) //Proses Pertukaran
{
a3[j] = a3[j - 1];
}
a3[j] = c;
}
cout << "Penghitungan dengan Insertion sort:\n";
cout <<endl;
for (i=0;i<b;++i) // Pengurutan nilai dari yang terkecil
cout<<ax[i]<<" "; // Output selection sort
cout<<endl<<endl;
}
}
Bu kaya gini ta hasilnya……. q binun buat kecepatan sortnya yang di atas ada yang t sensor
13.
riza | July 2, 2009 at 4:32 am
int SelectionSort(int *T, int Nmax)
{
/*kamus lokal*/
int i, j,step;
int min, temp;
/*algoritma*/
step=0;
for (i = 0; i < Nmax-1; i++)
{
min = i;step++;
for (j = i+1; j < Nmax; j++)
{
step++;
if (*T[j] < *T[min])
{min = j;step++;}
step=step+2;
}
temp = *T[i];step++;
*T[i] = *T[min];step++;
*T[min] = temp;step++;
step=step+2;
}
return step;
}
14.
riza | July 2, 2009 at 11:29 am
gunakan srand ( time(NULL) ) untuk mendapatkan bilangan acak yang selalu berbeda setiap kali program dijalankan.
/* srand example */
#include
#include
#include
int main ()
{
printf (“First number: %d\n”, rand() % 100);
srand ( time(NULL) );
printf (“Random number: %d\n”, rand() % 100);
srand ( 1 );
printf (“Again the first number: %d\n”, rand() %100);
return 0;
}
Output:
First number: 41
Random number: 13
Again the first number: 41
dari http://www.cplusplus.com/reference/clibrary/cstdlib/srand/
15.
yogi'e bgt'z | July 3, 2009 at 9:47 am
matuR SUWUn bU RizA Ud dUPLoad sourcE KodeY . ,
Ud saMA BgT’Z Bu soURCE CodENa. . ,
tP HAsiLE PunYAq TetEP waE Bu. . . ,
hasiLNa puNYA’E SampeAN Gmn bU. .,??
kLW HasiLE BedA. . ,
mhON PEncerAHAnY Bu. . ,
binUN pUNYaQ NecH DA bneR Pa bLUM. . ,??
wassaLAM. ,
16.
javakomp | July 9, 2009 at 2:54 pm
Agak Mudeng tapi. . . . .
banyak langkah itu nilainya di ambil dari mana ya???
repaly:
Hasil:
Banyak langkah bubble sort: 123
. . . . . . . . . . . . . . .. . . .
17.
riza | July 11, 2009 at 5:21 am
lihat di komen 13, ada variabel step. banyak langkah diambil dari variabel step tersebut
18.
rera | October 14, 2009 at 2:27 am
berikan contoh program yang lain, terimakasih..