PENJELASAN SORTING
Assalamuallaikum wr.wb
Teman – teman algoritma kali ni kita belajar tentang sorting, saya harap artikel cukup bermanfaat dan menambah pengetahuan kita semua.
S O R T I N G
Pengurutan sorting diartikan sebagai proses penyusunan kembali sekumpulan obyek ke dalam urutan tertentu. Tujuan pengurutan adalah mendapatkan kemudahan dalam pencarian anggota dari suatu himpunan disamping dapat mempercepat mengetahui data terbesar dan data terkecil, misalkan kita ingin mengetahui perolehan nilai tertinggi dan terendah dari hasil ujian. Contoh obyek terurutkan adalah daftar isi, daftar pustaka, dan lain-lain. Proses yang terjadi pada pengurutan adalah sebagai berikut :
- Perbandingan data
- Pertukaran
Terdapat bermacam-macam metode pengurutan, di antaranya adalah :
- Selection Sort
- Bubble Sort
- Insertion Sort
- Merge Sort
Penjelasan :
1. Selection Sort
a. Pengurutan Naik (Ascending)
Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah sebagai berikut :
1) Mencari data terkecil dari data pertama sampai data terakhir, keudian ditukarkan posisinya dengan data pertama.
2) Mencari data terkecil dari data kedua sampai data terakhir, kemudian ditukarkan posisinya dengan data kedua
3) Mencari data terkecil dari data kedua sampai data terakhir, kemudian ditukarkan posisinya dengan data ketiga
4) Dan seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang akan diurutkan, maka membutuhkan (n-1)langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu diurutkan karena hanya tinggal atu-satunya.
Contoh kasus:
Terdapat 8 buah data yang nilainya belum terurut:
44 55 12 42 94 18 6 67
Data tersebut akan diurutkan naik menggunakan metode Silection Sort :
Proses 1:
Index min = 1
Data ke 2:A[indek min]<A[2]
Data ke 3:A[indek min]>A[3]
Indek min = 3
Data ke -4:A[indek min]<A[4]
Data ke -5:A[indek min]<A[5]
Data ke -6:A[indek min]<A[6]
Data ke -7:A[indek min]>A[7]
Indek min = 7
Data ke -8:A[indek min]<A[8]
Karena A[1]<> A[indek min], maka dilakukan pertukara nilai data ke 1 dan daat ke indek min (data ke 7). Akhir dari proses adalah :
6 55 12 42 94 18 44 67
Kondisi pada akhir proses pertama ini digunakan sebagai masukan pada proses kedua.
Proses 2:
Indek min =2
Data ke 3: A[index min]>A[3]
Indexmin=3
Data ke -4:A[indek min]<A[4]
Data ke -5:A[indek min]<A[5]
Data ke -6:A[indek min]<A[6]
Data ke -7:A[indek min]<A[7]
Data ke -8:A[indek min]>A[8]
Karena A[2] <>A[indexmin], maka dilakukan pertukaran nilai data ke 2dan data ke index min(data ke 3). Akhir dari proses 2 dalah :
6 12 55 42 94 18 44 67
Kondisi data pada akhir proses kedua ini digunakab sebagai masukan pada proes ke tiga.
Proses 3:
Index min= 3
Data ke-4 :A[indx min]>A[4]
indexmin=4
Data ke-5 :A[indx min]<A[5]
Data ke-6 :A[indx min]>A[6]
Indexmin=6
Data ke-7 :A[indx min]<A[7]
Data ke-8 :A[indx min]<A[8]
Karena A[3] <> A[indexmin], maka ilakukan perukaran nilai data ke 3 dan data ke index min(data ke 6). Akhir dari proses 3 adalah :
6 12 18 42 94 55 44 67
Kondisi data pada akhir proses ketiga ini digunakan sebagai masukan pada proses ke 4.
Proses 4
Index min = 4
Data ke-5 :A[indx min]>A[5]
Data ke-6 :A[indx min]>A[6]
Data ke-7 :A[indx min]>A[7]
Data ke-8 :A[indx min]>A[8]
Karena A[4] =A[indexmin], maka idak dilakukan pertukaran nilai. Pada awal di tukar dari proses 4 tidak terjadi perubahan yaitu kondisi datanya tetap:
6 12 18 42 94 55 44 67
Kondisi data pada akhir proses keempat ini digunakan sebagai masukan pada proses kelima.
Proses 5:
Index min = 5
Data ke-6 :A[indexmin]> A[6]
Indexmin = 6
Data ke-7 :A[indexmin]>A[7]
Indexmin =7
Data ke-8 :A[indx min]>A[8]
Karena A[5]<>A[indexmin], maka dilakukan pertukaran nilai data ke 5 dan data ke index min (data ke 7). Akhir dari proses ke lima
Proses 6:
Index min = 6
Data ke-7 :A[indx min]>A[7]
Data ke-8 :A[indx min]>A[8]
Karena A[6]= A[indxmin], mkaa tidak dilakukan pertukaran nilai. Pada awal dan akhir dari proses 6 tidak terjadi perubahan yaiu kondisi datanya teteap :
6 12 18 42 44 55 94 67
Kondisi data pada akhir proses keenam ini digunakan sebagai masukan pada proseske tujuh .
Proses 7:
Indexmin = 7
Data ke-8:A[indexmin]>A[8]
Indexmin=8
Karena A[7]<> A[indexin], maka dilakukan pertukaran nilai data ke-7 dan datske indexmin(data ke 8). Akhir dari proses 7 adalah :
6 12 18 42 44 55 67 94
Kondisi data pada akhir proses ke tujuh ini merupakan akhir dar pengurutan secara menaik.
Dengan asumsi sudah terdapat array yang menyimpan n buah elemen, algoritma selection sort disaikan dengan metode psedocode:
For i= 1 t (n-1) do
Indexmin=i
For j=i+1 n d
If A[indexmin] >A[j] then
Indexmin=j
End if
Endfor
If A[i] <>A[indexmin] then
Temp= A[i]
A[i]=A[indxmin]
A[indexmin]= temp
End if
Endfor
Implementasi dalam bahasa C/C++
/*Selection sort menaik */
#include<stdio.h>
Main()
{
Int I,n,temp, indexmin,j;
Int A[n];
Printf(“Selection sort menaik\n”);
Printf(“Banyak data :”);
Scanf(“%d”,&n);
For (i=0;<n;i++){
Indexmin=i
For (j=i+1;j<n;j++)
{
If(A[indexmin]>A[j])
Indexmin=j
If9A[i] !=A[inexmin])
Temp=A[i];
A[i]=A[indexmin];
A[indexmin]=temp;
}
}
Printf(“setelah penurutan \n”);
For(i=0;i<n;i++)
Printf(”%d”, a[i]);
}
Jika ingin melihat hasil pengurtan setiap kali proses, kita lihat program dibawah ini :
#iclue<stdio.h>
Main(){
Int i, n, temp,indexmin,j,k;
intA[n];
printf(”selection sort menaik \n”);
prinf(“banyak data :’);
scanf(“%d”, &n0;
for(i=0, i<n; i++)
printf(“masukan data ke-%d:,i+1);
scanf(”d”,&A[i]);
}
Printf(”\n sebelum diurut \n”);
For(i=0;i<n;i++)
Printf(”%d”,A[i]);
Prntf(”\n”);
For(i=0;i<n-1;i++)
{
Indexmin=i;
For(j=i+1;j<n;j++)
{
If(A[indexmin]>A[j])
Indexmin=j
}
If(A[i] !=A[indexmin])
{
Temp=A[i];
A[i]=A[indexmin];
A[indexmin]=temp;
}
Printf(“proses ke-%d :”,i+1);
For (k=0;k<n;k++)
Printf(”%d”,A[k]);
Printf(”\n”);
}
Printf(“\nSetelah pengurutan \n”);
For (i=0;i<n;i++)
Printf(“%d”,A[i]);
}
2. Bubble Sort
Proses yang terjadi pada pengurutan dengan metode bubble sort dalah selalu membandingkan dua data yang berdekatan.
Pengurutan naik
Apabila data yang berada di sebelah kanannya bernilai lebih kecil, maka dpertukarkan sampai semua dataterurut seingga memunculkan data terbesar diposisi paling terakhir.
Contoh kasus:
Terdapat 6 buah data yang nilainya blum terurut:
7 5 6 3 4 2
Data-data diatas akan ditampilkan secara terurut naik menggunakan metode bublesort. Proses pengurutannya adalah sebagai berikut :
Proses 1
Data 1-2:A[1]>A[2] ditukar
5 7 6 3 4 2
Data 2-3:A[2]>A[3] ditukar
5 6 7 3 4 2
Data 3-4:A[3]>A[4] ditukar
5 6 3 7 4 2
Data 4-5:A[4]>A[5] ditukar
5 6 3 4 7 2
Data 5-6:A[5]>A[6] ditukar
5 6 3 4 2 7
Akhir dari proses pertama dalah menempatkan data terbesarpertama pada posisi ke-n(posisi ke-6).
Proses 2:
Data 1-2:A[1]<A[2]
Data 2-3:A[2]>A[3] ditukar
5 3 6 4 2 7
Data 3-4:A[3]>A[4] ditukar
5 3 4 6 2 7
Data 4-5: A[4]> A[5] ditukar
5 3 4 2 6 7
Akhi dari proses kedua adalah menempatkan data terbesar kedua pada posisi ke-n-1(posisi ke -).
Proses 3
Data 1-2: A[1] >A[2] ditukar
3 5 4 2 6 7
Data 2-3: A[2]>A[3] ditukar
3 4 5 2 6 7
Data 3-4:A[3]>A[4] ditukar
3 4 2 5 6 7
Akhir dari poses ketiga adalah menempatkan data terbesar ketiga pada posisi ke-n-2(posisi ke-4).
Proses 4:
Data 1-2:A[1]<A[2]
Data 2-3:A[2]>A[3] ditukar
3 2 4 5 6 7
Akhir pada proses keempat adalah menempatkan data terbesar keempat pada posisi ke-n-3(posisi ke 3)
Proses 5
Data 1-2:A[1]>A[2]
Data 2-3:A[2]>A[3] ditukar
2 3 4 5 6 7
Akhir dari proses kelima atau teakhir adalah menempatkan data terbesar kelima dan keenam pad posisi ke- dan ke-n-5(posisi ke-2 dan ke-1).
Penyajian pseudecode algoritma bbble sor:
For i=1 to (n-1) do
For j=1 t (n-i) do
If A[] >A[j+1] then
Temp = A[j]
A[j]=A[j+1]
A[j+1]=temp
Endif
Endfor
Endfor
Implementasi :
/*Bubble sort menaik */
#include<studio.h>
Main(){
Int I,n,j,temp;
Int A[100];
Printf(“Bubble sort menaik\ n”);
Printf(“Banyak data :”);
Scantf(”%d”,&n);
For (i=0;i<n;i++)
{
Printf(”Data ke-%d :”,i+1);
Scanf(”%d”,&A[i]);
}
For (i=0;i<n-1;i++)
{
For (j=0;j<(n-i);j++){
If(A[j] >A[j+1])
{
Temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
Printf(“Setelah terurut :\n”);
For(i=0;i<n;i++)
Printf(“%d”,A[i]);
}
3. Insertion Sort
Proses yang terjadi pada pengurutan dengan menggunakan metode insertion sort dimulai dari data ke-2, kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama diandaikan memang sudah pada tempatnya.
Pengurutan Naik
Mulai dari data ke dua , nilainya dibandingkan dengan data-data sebelumnya, kemudian mencari posisi yang tepet untuk menyisipkannya.
Algoritma pedecode:
For i=2 to n do
Temp=A[i]
{ambil elemen A[i] agar nilainya tidak dihilang karena tetimpa penggeseran }
A[0]=temp {sentinel}
J=i-1
{cari posisi yang tepat untuk A[i]di dalam A[1..i-1] sambil menggeser}
While A[j]>temp do
A[j+1]=A[j]{penggeseran}
J=j-1
Endwhile
A[j+1]= temp {menemukan tempat yang tepat }
End for
Implementasi program :
#include<stdio.h>
Main()
{
Int n,I, temp , j, k, m, h;
Int A[100];
Printf(“insertion sort \n);
Printf(“Banyak data:”);
Scanf(“%d”.&n);
For (i=0;i<n;i++)
{
Prinf(“Data ke-%d : “,i+1);
Scanf(”%d”,&A[i]);
}
For (i = 1; i<n; i++)
{
Temp=A[i];
J=i-1
Printf (”\n Proses i=%d \n”, i+1);
Printf(”Sebelum proses = = > ”);
For(h=0; h<n;h++)printf(”%d ”,A[h]);
Printf(“\n”);
Printf(“temp = d \n”,temp);
Printf(“proses \n”);
While(A[j]>temp)
{
A[j+1=A[j];
J=j-1;
For(k=0;k<n;k++)printf(“%d “,A[k])printf(“\n”);
}
A[j+1]=temp;
Printf(”setelah proses i=%d = = > “, i+1);
For(m=0;m<n;m++)printf(“%d “,A[m] );
Printf(“\n”);
}
Printf(“\n Setelah urut \n”);
For(i=0;i<n;i++)
Printf(“%d “,A[i]);
}
4. Merge Sort
Metode merge Sort adalah menggabungkan dua buah array yang sudah terurut. Untuk mengurutkan masing masng array kita bisa menggunakan selection sort, bubble sort, maupun insertion sort.
Pengurutan naik(ascending)
2 buah array yang masing-masing terurut naik kan digabungkan menjadi terurut naik.
Contoh kasus:
Array petama : 5 8 12 15 20 25 29
Array kedua : 4 6 21 22
Proses penggabungan dua buah array diatas menjadisebuah aray yang terurut naik adalah sebagai berikut:
1 2 3 4 5 6 7 a=1s/d m
A = 5 8 12 15 20 25 29
1 2 3 4 b=1s/d n
B = 4 6 21 22
C= c=1s/dm+n
A[1]>B[1]
C[1] B[1]
C=4
B=1+1=2
A[1]<B[2]
C[2] A[1]
C=1+1=2
A[2] > B[2]
C[3] B[6]
C=4 5 6
B= 2+1 = 3
A[3]<B[3]
C[5] A[3]
C=4 5 6 8 12
A= 3 + 1 = 4
A[4] > B[3]
C[6] B[4]
C=4 5 6 8 12 15
B= 4+1 = 5
A[5]<B[3]
C[7] A[5]
C=4 5 6 8 12 15 20
A= 5 + 1 = 6
A[6] > B[3]
C[8] B[3]
C=4 5 6 8 12 15 20 21
B= 3+1 = 4
A[6]<B[4]
C[9] A[4]
C=4 5 6 8 12 15 20 21 22
A= 4 + 1 = 5
Array terdiri dari empat elemen. Padaakhir proses ini, setelah indexpada array kedua dinaikan ternyata indeksnya telah melampui ukuran array kedua yang sesungguhnya. Berarti semua elemen array kedua sudah hais terlebih dahulu dan masuk kedalam array gabungan
b>4 artinyab>n
elemen array pertama yang masih tersisa akan dimasukan ke dalam array gabungan satu persatu.
A=5+1=6
C[10] A[6]
C = 4 5 6 8 12 15 20 21 22 25
A=6+1=7
C[11] A[7]
C= 4 5 6 8 12 15 20 21 22 25 29
Algorima dengan pseudecode
a=0
b=0
c=0
For i=1 to m+n
If a>=m or b>=n then end for
If(A[a]<B[b])
C[c]=A[a]
a++
c++
Else if (A[a]>=B[b])
C[c] =B[b]
b++
c++
end if
end if
end for
if(b<n)
for i=b to n-1
c[c] = b[i]
c++
else if(<m)
foi= a to m-1
C[c]=A[i]
c++
sendif
endif
Implementasi program
#include<studio.h>
Main(){
Int a,m,n,ij,iexmin,temp
Int A[100];
Int B[100];
Int C[200];
Printf(“mege sort menaik\n”);
Printf”banyaknya data array ptama:”);
Scanf(“%d”,&m);
Or(i=0;i<m;i++){
Printf(”Data ke-%d:”+1);
Scanf(“%d”,&A[i]);
}
For (i=0;i<m-1;i++)
{
Indexmin=i;
For(j=i+1;j<m;j++)
{
If(A[indexmin]>A[j])
Indexmin=j;
}
If (A[i] !=A[idexmin])
{
Temp = A[i];
A[i]=A[indxmin];
A[indexmin]=temp;
}
}
Printf(“Banyak data array kedua :”);
Scanf(“%d”,&n);
For(i=0;i<n;i++)
{
Printf(”Data ke-%d:”i+1);
Scanf(”%d”,&B[i]);
}
For(i=0;i<n-1;i++)
{
Indexmin=i;
For(j=i+1;j<n;j++)
{
If(B[indexmin]>B[j])
Indexmin=j;
}
If(B[i] !=B[indexmin])
{
Temp= B[i];
B[i]=B[indexmin];
B[indexmin]=tem;
}
}
Printf(“setelah urut \n”);
a=0;
b=0;
c=0;
for(i=1;i<m+n;i++)
{
If(a>=m||b>=n)break;
If(A[a]<B[b])
{
C[c]=A[a]
a++;
c++;
}
Else if(A[a]>=B[b])
{
C[c]=B[b];
b++;
c++;
}
}
{
For (i=b;i<n;i++)
{
C[c] = B[i];
c++;
}
}
Else if(a<m)
{
For(i=a;i<m;i++)
{
C[c]=A[i];
c++;
}
}
Printf(”array prtama :\n”);
For(a=0;a<m;a++)printf(”%d “,A[a]);
Printf(“\n”);
Printf(”array kedua :\n”);
For(a=0;a<m;a++)printf(”%d “,B[b]);
Printf(“\n”);
Printf(“array gabungan :\n”);
For(i=0;i<m+n;i++)
Printf(“%d “,C[i]);
Printf(”\n”);
}
Oke teman semua, tetap semangat ya,Go Succes..
Wassalamuallaikum wr.wb
From : Jumdapi okta
Prosus Teknik Informatika
Teman – teman algoritma kali ni kita belajar tentang sorting, saya harap artikel cukup bermanfaat dan menambah pengetahuan kita semua.
S O R T I N G
Pengurutan sorting diartikan sebagai proses penyusunan kembali sekumpulan obyek ke dalam urutan tertentu. Tujuan pengurutan adalah mendapatkan kemudahan dalam pencarian anggota dari suatu himpunan disamping dapat mempercepat mengetahui data terbesar dan data terkecil, misalkan kita ingin mengetahui perolehan nilai tertinggi dan terendah dari hasil ujian. Contoh obyek terurutkan adalah daftar isi, daftar pustaka, dan lain-lain. Proses yang terjadi pada pengurutan adalah sebagai berikut :
- Perbandingan data
- Pertukaran
Terdapat bermacam-macam metode pengurutan, di antaranya adalah :
- Selection Sort
- Bubble Sort
- Insertion Sort
- Merge Sort
Penjelasan :
1. Selection Sort
a. Pengurutan Naik (Ascending)
Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah sebagai berikut :
1) Mencari data terkecil dari data pertama sampai data terakhir, keudian ditukarkan posisinya dengan data pertama.
2) Mencari data terkecil dari data kedua sampai data terakhir, kemudian ditukarkan posisinya dengan data kedua
3) Mencari data terkecil dari data kedua sampai data terakhir, kemudian ditukarkan posisinya dengan data ketiga
4) Dan seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang akan diurutkan, maka membutuhkan (n-1)langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu diurutkan karena hanya tinggal atu-satunya.
Contoh kasus:
Terdapat 8 buah data yang nilainya belum terurut:
44 55 12 42 94 18 6 67
Data tersebut akan diurutkan naik menggunakan metode Silection Sort :
Proses 1:
Index min = 1
Data ke 2:A[indek min]<A[2]
Data ke 3:A[indek min]>A[3]
Indek min = 3
Data ke -4:A[indek min]<A[4]
Data ke -5:A[indek min]<A[5]
Data ke -6:A[indek min]<A[6]
Data ke -7:A[indek min]>A[7]
Indek min = 7
Data ke -8:A[indek min]<A[8]
Karena A[1]<> A[indek min], maka dilakukan pertukara nilai data ke 1 dan daat ke indek min (data ke 7). Akhir dari proses adalah :
6 55 12 42 94 18 44 67
Kondisi pada akhir proses pertama ini digunakan sebagai masukan pada proses kedua.
Proses 2:
Indek min =2
Data ke 3: A[index min]>A[3]
Indexmin=3
Data ke -4:A[indek min]<A[4]
Data ke -5:A[indek min]<A[5]
Data ke -6:A[indek min]<A[6]
Data ke -7:A[indek min]<A[7]
Data ke -8:A[indek min]>A[8]
Karena A[2] <>A[indexmin], maka dilakukan pertukaran nilai data ke 2dan data ke index min(data ke 3). Akhir dari proses 2 dalah :
6 12 55 42 94 18 44 67
Kondisi data pada akhir proses kedua ini digunakab sebagai masukan pada proes ke tiga.
Proses 3:
Index min= 3
Data ke-4 :A[indx min]>A[4]
indexmin=4
Data ke-5 :A[indx min]<A[5]
Data ke-6 :A[indx min]>A[6]
Indexmin=6
Data ke-7 :A[indx min]<A[7]
Data ke-8 :A[indx min]<A[8]
Karena A[3] <> A[indexmin], maka ilakukan perukaran nilai data ke 3 dan data ke index min(data ke 6). Akhir dari proses 3 adalah :
6 12 18 42 94 55 44 67
Kondisi data pada akhir proses ketiga ini digunakan sebagai masukan pada proses ke 4.
Proses 4
Index min = 4
Data ke-5 :A[indx min]>A[5]
Data ke-6 :A[indx min]>A[6]
Data ke-7 :A[indx min]>A[7]
Data ke-8 :A[indx min]>A[8]
Karena A[4] =A[indexmin], maka idak dilakukan pertukaran nilai. Pada awal di tukar dari proses 4 tidak terjadi perubahan yaitu kondisi datanya tetap:
6 12 18 42 94 55 44 67
Kondisi data pada akhir proses keempat ini digunakan sebagai masukan pada proses kelima.
Proses 5:
Index min = 5
Data ke-6 :A[indexmin]> A[6]
Indexmin = 6
Data ke-7 :A[indexmin]>A[7]
Indexmin =7
Data ke-8 :A[indx min]>A[8]
Karena A[5]<>A[indexmin], maka dilakukan pertukaran nilai data ke 5 dan data ke index min (data ke 7). Akhir dari proses ke lima
Proses 6:
Index min = 6
Data ke-7 :A[indx min]>A[7]
Data ke-8 :A[indx min]>A[8]
Karena A[6]= A[indxmin], mkaa tidak dilakukan pertukaran nilai. Pada awal dan akhir dari proses 6 tidak terjadi perubahan yaiu kondisi datanya teteap :
6 12 18 42 44 55 94 67
Kondisi data pada akhir proses keenam ini digunakan sebagai masukan pada proseske tujuh .
Proses 7:
Indexmin = 7
Data ke-8:A[indexmin]>A[8]
Indexmin=8
Karena A[7]<> A[indexin], maka dilakukan pertukaran nilai data ke-7 dan datske indexmin(data ke 8). Akhir dari proses 7 adalah :
6 12 18 42 44 55 67 94
Kondisi data pada akhir proses ke tujuh ini merupakan akhir dar pengurutan secara menaik.
Dengan asumsi sudah terdapat array yang menyimpan n buah elemen, algoritma selection sort disaikan dengan metode psedocode:
For i= 1 t (n-1) do
Indexmin=i
For j=i+1 n d
If A[indexmin] >A[j] then
Indexmin=j
End if
Endfor
If A[i] <>A[indexmin] then
Temp= A[i]
A[i]=A[indxmin]
A[indexmin]= temp
End if
Endfor
Implementasi dalam bahasa C/C++
/*Selection sort menaik */
#include<stdio.h>
Main()
{
Int I,n,temp, indexmin,j;
Int A[n];
Printf(“Selection sort menaik\n”);
Printf(“Banyak data :”);
Scanf(“%d”,&n);
For (i=0;<n;i++){
Indexmin=i
For (j=i+1;j<n;j++)
{
If(A[indexmin]>A[j])
Indexmin=j
If9A[i] !=A[inexmin])
Temp=A[i];
A[i]=A[indexmin];
A[indexmin]=temp;
}
}
Printf(“setelah penurutan \n”);
For(i=0;i<n;i++)
Printf(”%d”, a[i]);
}
Jika ingin melihat hasil pengurtan setiap kali proses, kita lihat program dibawah ini :
#iclue<stdio.h>
Main(){
Int i, n, temp,indexmin,j,k;
intA[n];
printf(”selection sort menaik \n”);
prinf(“banyak data :’);
scanf(“%d”, &n0;
for(i=0, i<n; i++)
printf(“masukan data ke-%d:,i+1);
scanf(”d”,&A[i]);
}
Printf(”\n sebelum diurut \n”);
For(i=0;i<n;i++)
Printf(”%d”,A[i]);
Prntf(”\n”);
For(i=0;i<n-1;i++)
{
Indexmin=i;
For(j=i+1;j<n;j++)
{
If(A[indexmin]>A[j])
Indexmin=j
}
If(A[i] !=A[indexmin])
{
Temp=A[i];
A[i]=A[indexmin];
A[indexmin]=temp;
}
Printf(“proses ke-%d :”,i+1);
For (k=0;k<n;k++)
Printf(”%d”,A[k]);
Printf(”\n”);
}
Printf(“\nSetelah pengurutan \n”);
For (i=0;i<n;i++)
Printf(“%d”,A[i]);
}
2. Bubble Sort
Proses yang terjadi pada pengurutan dengan metode bubble sort dalah selalu membandingkan dua data yang berdekatan.
Pengurutan naik
Apabila data yang berada di sebelah kanannya bernilai lebih kecil, maka dpertukarkan sampai semua dataterurut seingga memunculkan data terbesar diposisi paling terakhir.
Contoh kasus:
Terdapat 6 buah data yang nilainya blum terurut:
7 5 6 3 4 2
Data-data diatas akan ditampilkan secara terurut naik menggunakan metode bublesort. Proses pengurutannya adalah sebagai berikut :
Proses 1
Data 1-2:A[1]>A[2] ditukar
5 7 6 3 4 2
Data 2-3:A[2]>A[3] ditukar
5 6 7 3 4 2
Data 3-4:A[3]>A[4] ditukar
5 6 3 7 4 2
Data 4-5:A[4]>A[5] ditukar
5 6 3 4 7 2
Data 5-6:A[5]>A[6] ditukar
5 6 3 4 2 7
Akhir dari proses pertama dalah menempatkan data terbesarpertama pada posisi ke-n(posisi ke-6).
Proses 2:
Data 1-2:A[1]<A[2]
Data 2-3:A[2]>A[3] ditukar
5 3 6 4 2 7
Data 3-4:A[3]>A[4] ditukar
5 3 4 6 2 7
Data 4-5: A[4]> A[5] ditukar
5 3 4 2 6 7
Akhi dari proses kedua adalah menempatkan data terbesar kedua pada posisi ke-n-1(posisi ke -).
Proses 3
Data 1-2: A[1] >A[2] ditukar
3 5 4 2 6 7
Data 2-3: A[2]>A[3] ditukar
3 4 5 2 6 7
Data 3-4:A[3]>A[4] ditukar
3 4 2 5 6 7
Akhir dari poses ketiga adalah menempatkan data terbesar ketiga pada posisi ke-n-2(posisi ke-4).
Proses 4:
Data 1-2:A[1]<A[2]
Data 2-3:A[2]>A[3] ditukar
3 2 4 5 6 7
Akhir pada proses keempat adalah menempatkan data terbesar keempat pada posisi ke-n-3(posisi ke 3)
Proses 5
Data 1-2:A[1]>A[2]
Data 2-3:A[2]>A[3] ditukar
2 3 4 5 6 7
Akhir dari proses kelima atau teakhir adalah menempatkan data terbesar kelima dan keenam pad posisi ke- dan ke-n-5(posisi ke-2 dan ke-1).
Penyajian pseudecode algoritma bbble sor:
For i=1 to (n-1) do
For j=1 t (n-i) do
If A[] >A[j+1] then
Temp = A[j]
A[j]=A[j+1]
A[j+1]=temp
Endif
Endfor
Endfor
Implementasi :
/*Bubble sort menaik */
#include<studio.h>
Main(){
Int I,n,j,temp;
Int A[100];
Printf(“Bubble sort menaik\ n”);
Printf(“Banyak data :”);
Scantf(”%d”,&n);
For (i=0;i<n;i++)
{
Printf(”Data ke-%d :”,i+1);
Scanf(”%d”,&A[i]);
}
For (i=0;i<n-1;i++)
{
For (j=0;j<(n-i);j++){
If(A[j] >A[j+1])
{
Temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
Printf(“Setelah terurut :\n”);
For(i=0;i<n;i++)
Printf(“%d”,A[i]);
}
3. Insertion Sort
Proses yang terjadi pada pengurutan dengan menggunakan metode insertion sort dimulai dari data ke-2, kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama diandaikan memang sudah pada tempatnya.
Pengurutan Naik
Mulai dari data ke dua , nilainya dibandingkan dengan data-data sebelumnya, kemudian mencari posisi yang tepet untuk menyisipkannya.
Algoritma pedecode:
For i=2 to n do
Temp=A[i]
{ambil elemen A[i] agar nilainya tidak dihilang karena tetimpa penggeseran }
A[0]=temp {sentinel}
J=i-1
{cari posisi yang tepat untuk A[i]di dalam A[1..i-1] sambil menggeser}
While A[j]>temp do
A[j+1]=A[j]{penggeseran}
J=j-1
Endwhile
A[j+1]= temp {menemukan tempat yang tepat }
End for
Implementasi program :
#include<stdio.h>
Main()
{
Int n,I, temp , j, k, m, h;
Int A[100];
Printf(“insertion sort \n);
Printf(“Banyak data:”);
Scanf(“%d”.&n);
For (i=0;i<n;i++)
{
Prinf(“Data ke-%d : “,i+1);
Scanf(”%d”,&A[i]);
}
For (i = 1; i<n; i++)
{
Temp=A[i];
J=i-1
Printf (”\n Proses i=%d \n”, i+1);
Printf(”Sebelum proses = = > ”);
For(h=0; h<n;h++)printf(”%d ”,A[h]);
Printf(“\n”);
Printf(“temp = d \n”,temp);
Printf(“proses \n”);
While(A[j]>temp)
{
A[j+1=A[j];
J=j-1;
For(k=0;k<n;k++)printf(“%d “,A[k])printf(“\n”);
}
A[j+1]=temp;
Printf(”setelah proses i=%d = = > “, i+1);
For(m=0;m<n;m++)printf(“%d “,A[m] );
Printf(“\n”);
}
Printf(“\n Setelah urut \n”);
For(i=0;i<n;i++)
Printf(“%d “,A[i]);
}
4. Merge Sort
Metode merge Sort adalah menggabungkan dua buah array yang sudah terurut. Untuk mengurutkan masing masng array kita bisa menggunakan selection sort, bubble sort, maupun insertion sort.
Pengurutan naik(ascending)
2 buah array yang masing-masing terurut naik kan digabungkan menjadi terurut naik.
Contoh kasus:
Array petama : 5 8 12 15 20 25 29
Array kedua : 4 6 21 22
Proses penggabungan dua buah array diatas menjadisebuah aray yang terurut naik adalah sebagai berikut:
1 2 3 4 5 6 7 a=1s/d m
A = 5 8 12 15 20 25 29
1 2 3 4 b=1s/d n
B = 4 6 21 22
C= c=1s/dm+n
A[1]>B[1]
C[1] B[1]
C=4
B=1+1=2
A[1]<B[2]
C[2] A[1]
C=1+1=2
A[2] > B[2]
C[3] B[6]
C=4 5 6
B= 2+1 = 3
A[3]<B[3]
C[5] A[3]
C=4 5 6 8 12
A= 3 + 1 = 4
A[4] > B[3]
C[6] B[4]
C=4 5 6 8 12 15
B= 4+1 = 5
A[5]<B[3]
C[7] A[5]
C=4 5 6 8 12 15 20
A= 5 + 1 = 6
A[6] > B[3]
C[8] B[3]
C=4 5 6 8 12 15 20 21
B= 3+1 = 4
A[6]<B[4]
C[9] A[4]
C=4 5 6 8 12 15 20 21 22
A= 4 + 1 = 5
Array terdiri dari empat elemen. Padaakhir proses ini, setelah indexpada array kedua dinaikan ternyata indeksnya telah melampui ukuran array kedua yang sesungguhnya. Berarti semua elemen array kedua sudah hais terlebih dahulu dan masuk kedalam array gabungan
b>4 artinyab>n
elemen array pertama yang masih tersisa akan dimasukan ke dalam array gabungan satu persatu.
A=5+1=6
C[10] A[6]
C = 4 5 6 8 12 15 20 21 22 25
A=6+1=7
C[11] A[7]
C= 4 5 6 8 12 15 20 21 22 25 29
Algorima dengan pseudecode
a=0
b=0
c=0
For i=1 to m+n
If a>=m or b>=n then end for
If(A[a]<B[b])
C[c]=A[a]
a++
c++
Else if (A[a]>=B[b])
C[c] =B[b]
b++
c++
end if
end if
end for
if(b<n)
for i=b to n-1
c[c] = b[i]
c++
else if(<m)
foi= a to m-1
C[c]=A[i]
c++
sendif
endif
Implementasi program
#include<studio.h>
Main(){
Int a,m,n,ij,iexmin,temp
Int A[100];
Int B[100];
Int C[200];
Printf(“mege sort menaik\n”);
Printf”banyaknya data array ptama:”);
Scanf(“%d”,&m);
Or(i=0;i<m;i++){
Printf(”Data ke-%d:”+1);
Scanf(“%d”,&A[i]);
}
For (i=0;i<m-1;i++)
{
Indexmin=i;
For(j=i+1;j<m;j++)
{
If(A[indexmin]>A[j])
Indexmin=j;
}
If (A[i] !=A[idexmin])
{
Temp = A[i];
A[i]=A[indxmin];
A[indexmin]=temp;
}
}
Printf(“Banyak data array kedua :”);
Scanf(“%d”,&n);
For(i=0;i<n;i++)
{
Printf(”Data ke-%d:”i+1);
Scanf(”%d”,&B[i]);
}
For(i=0;i<n-1;i++)
{
Indexmin=i;
For(j=i+1;j<n;j++)
{
If(B[indexmin]>B[j])
Indexmin=j;
}
If(B[i] !=B[indexmin])
{
Temp= B[i];
B[i]=B[indexmin];
B[indexmin]=tem;
}
}
Printf(“setelah urut \n”);
a=0;
b=0;
c=0;
for(i=1;i<m+n;i++)
{
If(a>=m||b>=n)break;
If(A[a]<B[b])
{
C[c]=A[a]
a++;
c++;
}
Else if(A[a]>=B[b])
{
C[c]=B[b];
b++;
c++;
}
}
{
For (i=b;i<n;i++)
{
C[c] = B[i];
c++;
}
}
Else if(a<m)
{
For(i=a;i<m;i++)
{
C[c]=A[i];
c++;
}
}
Printf(”array prtama :\n”);
For(a=0;a<m;a++)printf(”%d “,A[a]);
Printf(“\n”);
Printf(”array kedua :\n”);
For(a=0;a<m;a++)printf(”%d “,B[b]);
Printf(“\n”);
Printf(“array gabungan :\n”);
For(i=0;i<m+n;i++)
Printf(“%d “,C[i]);
Printf(”\n”);
}
Oke teman semua, tetap semangat ya,Go Succes..
Wassalamuallaikum wr.wb
From : Jumdapi okta
Prosus Teknik Informatika
Teman – teman algoritma kali ni kita belajar tentang sorting, saya harap artikel cukup bermanfaat dan menambah pengetahuan kita semua.
S O R T I N G
Pengurutan sorting diartikan sebagai proses penyusunan kembali sekumpulan obyek ke dalam urutan tertentu. Tujuan pengurutan adalah mendapatkan kemudahan dalam pencarian anggota dari suatu himpunan disamping dapat mempercepat mengetahui data terbesar dan data terkecil, misalkan kita ingin mengetahui perolehan nilai tertinggi dan terendah dari hasil ujian. Contoh obyek terurutkan adalah daftar isi, daftar pustaka, dan lain-lain. Proses yang terjadi pada pengurutan adalah sebagai berikut :
- Perbandingan data
- Pertukaran
Terdapat bermacam-macam metode pengurutan, di antaranya adalah :
- Selection Sort
- Bubble Sort
- Insertion Sort
- Merge Sort
Penjelasan :
1. Selection Sort
a. Pengurutan Naik (Ascending)
Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah sebagai berikut :
1) Mencari data terkecil dari data pertama sampai data terakhir, keudian ditukarkan posisinya dengan data pertama.
2) Mencari data terkecil dari data kedua sampai data terakhir, kemudian ditukarkan posisinya dengan data kedua
3) Mencari data terkecil dari data kedua sampai data terakhir, kemudian ditukarkan posisinya dengan data ketiga
4) Dan seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang akan diurutkan, maka membutuhkan (n-1)langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu diurutkan karena hanya tinggal atu-satunya.
Contoh kasus:
Terdapat 8 buah data yang nilainya belum terurut:
44 55 12 42 94 18 6 67
Data tersebut akan diurutkan naik menggunakan metode Silection Sort :
Proses 1:
Index min = 1
Data ke 2:A[indek min]<A[2]
Data ke 3:A[indek min]>A[3]
Indek min = 3
Data ke -4:A[indek min]<A[4]
Data ke -5:A[indek min]<A[5]
Data ke -6:A[indek min]<A[6]
Data ke -7:A[indek min]>A[7]
Indek min = 7
Data ke -8:A[indek min]<A[8]
Karena A[1]<> A[indek min], maka dilakukan pertukara nilai data ke 1 dan daat ke indek min (data ke 7). Akhir dari proses adalah :
6 55 12 42 94 18 44 67
Kondisi pada akhir proses pertama ini digunakan sebagai masukan pada proses kedua.
Proses 2:
Indek min =2
Data ke 3: A[index min]>A[3]
Indexmin=3
Data ke -4:A[indek min]<A[4]
Data ke -5:A[indek min]<A[5]
Data ke -6:A[indek min]<A[6]
Data ke -7:A[indek min]<A[7]
Data ke -8:A[indek min]>A[8]
Karena A[2] <>A[indexmin], maka dilakukan pertukaran nilai data ke 2dan data ke index min(data ke 3). Akhir dari proses 2 dalah :
6 12 55 42 94 18 44 67
Kondisi data pada akhir proses kedua ini digunakab sebagai masukan pada proes ke tiga.
Proses 3:
Index min= 3
Data ke-4 :A[indx min]>A[4]
indexmin=4
Data ke-5 :A[indx min]<A[5]
Data ke-6 :A[indx min]>A[6]
Indexmin=6
Data ke-7 :A[indx min]<A[7]
Data ke-8 :A[indx min]<A[8]
Karena A[3] <> A[indexmin], maka ilakukan perukaran nilai data ke 3 dan data ke index min(data ke 6). Akhir dari proses 3 adalah :
6 12 18 42 94 55 44 67
Kondisi data pada akhir proses ketiga ini digunakan sebagai masukan pada proses ke 4.
Proses 4
Index min = 4
Data ke-5 :A[indx min]>A[5]
Data ke-6 :A[indx min]>A[6]
Data ke-7 :A[indx min]>A[7]
Data ke-8 :A[indx min]>A[8]
Karena A[4] =A[indexmin], maka idak dilakukan pertukaran nilai. Pada awal di tukar dari proses 4 tidak terjadi perubahan yaitu kondisi datanya tetap:
6 12 18 42 94 55 44 67
Kondisi data pada akhir proses keempat ini digunakan sebagai masukan pada proses kelima.
Proses 5:
Index min = 5
Data ke-6 :A[indexmin]> A[6]
Indexmin = 6
Data ke-7 :A[indexmin]>A[7]
Indexmin =7
Data ke-8 :A[indx min]>A[8]
Karena A[5]<>A[indexmin], maka dilakukan pertukaran nilai data ke 5 dan data ke index min (data ke 7). Akhir dari proses ke lima
Proses 6:
Index min = 6
Data ke-7 :A[indx min]>A[7]
Data ke-8 :A[indx min]>A[8]
Karena A[6]= A[indxmin], mkaa tidak dilakukan pertukaran nilai. Pada awal dan akhir dari proses 6 tidak terjadi perubahan yaiu kondisi datanya teteap :
6 12 18 42 44 55 94 67
Kondisi data pada akhir proses keenam ini digunakan sebagai masukan pada proseske tujuh .
Proses 7:
Indexmin = 7
Data ke-8:A[indexmin]>A[8]
Indexmin=8
Karena A[7]<> A[indexin], maka dilakukan pertukaran nilai data ke-7 dan datske indexmin(data ke 8). Akhir dari proses 7 adalah :
6 12 18 42 44 55 67 94
Kondisi data pada akhir proses ke tujuh ini merupakan akhir dar pengurutan secara menaik.
Dengan asumsi sudah terdapat array yang menyimpan n buah elemen, algoritma selection sort disaikan dengan metode psedocode:
For i= 1 t (n-1) do
Indexmin=i
For j=i+1 n d
If A[indexmin] >A[j] then
Indexmin=j
End if
Endfor
If A[i] <>A[indexmin] then
Temp= A[i]
A[i]=A[indxmin]
A[indexmin]= temp
End if
Endfor
Implementasi dalam bahasa C/C++
/*Selection sort menaik */
#include<stdio.h>
Main()
{
Int I,n,temp, indexmin,j;
Int A[n];
Printf(“Selection sort menaik\n”);
Printf(“Banyak data :”);
Scanf(“%d”,&n);
For (i=0;<n;i++){
Indexmin=i
For (j=i+1;j<n;j++)
{
If(A[indexmin]>A[j])
Indexmin=j
If9A[i] !=A[inexmin])
Temp=A[i];
A[i]=A[indexmin];
A[indexmin]=temp;
}
}
Printf(“setelah penurutan \n”);
For(i=0;i<n;i++)
Printf(”%d”, a[i]);
}
Jika ingin melihat hasil pengurtan setiap kali proses, kita lihat program dibawah ini :
#iclue<stdio.h>
Main(){
Int i, n, temp,indexmin,j,k;
intA[n];
printf(”selection sort menaik \n”);
prinf(“banyak data :’);
scanf(“%d”, &n0;
for(i=0, i<n; i++)
printf(“masukan data ke-%d:,i+1);
scanf(”d”,&A[i]);
}
Printf(”\n sebelum diurut \n”);
For(i=0;i<n;i++)
Printf(”%d”,A[i]);
Prntf(”\n”);
For(i=0;i<n-1;i++)
{
Indexmin=i;
For(j=i+1;j<n;j++)
{
If(A[indexmin]>A[j])
Indexmin=j
}
If(A[i] !=A[indexmin])
{
Temp=A[i];
A[i]=A[indexmin];
A[indexmin]=temp;
}
Printf(“proses ke-%d :”,i+1);
For (k=0;k<n;k++)
Printf(”%d”,A[k]);
Printf(”\n”);
}
Printf(“\nSetelah pengurutan \n”);
For (i=0;i<n;i++)
Printf(“%d”,A[i]);
}
2. Bubble Sort
Proses yang terjadi pada pengurutan dengan metode bubble sort dalah selalu membandingkan dua data yang berdekatan.
Pengurutan naik
Apabila data yang berada di sebelah kanannya bernilai lebih kecil, maka dpertukarkan sampai semua dataterurut seingga memunculkan data terbesar diposisi paling terakhir.
Contoh kasus:
Terdapat 6 buah data yang nilainya blum terurut:
7 5 6 3 4 2
Data-data diatas akan ditampilkan secara terurut naik menggunakan metode bublesort. Proses pengurutannya adalah sebagai berikut :
Proses 1
Data 1-2:A[1]>A[2] ditukar
5 7 6 3 4 2
Data 2-3:A[2]>A[3] ditukar
5 6 7 3 4 2
Data 3-4:A[3]>A[4] ditukar
5 6 3 7 4 2
Data 4-5:A[4]>A[5] ditukar
5 6 3 4 7 2
Data 5-6:A[5]>A[6] ditukar
5 6 3 4 2 7
Akhir dari proses pertama dalah menempatkan data terbesarpertama pada posisi ke-n(posisi ke-6).
Proses 2:
Data 1-2:A[1]<A[2]
Data 2-3:A[2]>A[3] ditukar
5 3 6 4 2 7
Data 3-4:A[3]>A[4] ditukar
5 3 4 6 2 7
Data 4-5: A[4]> A[5] ditukar
5 3 4 2 6 7
Akhi dari proses kedua adalah menempatkan data terbesar kedua pada posisi ke-n-1(posisi ke -).
Proses 3
Data 1-2: A[1] >A[2] ditukar
3 5 4 2 6 7
Data 2-3: A[2]>A[3] ditukar
3 4 5 2 6 7
Data 3-4:A[3]>A[4] ditukar
3 4 2 5 6 7
Akhir dari poses ketiga adalah menempatkan data terbesar ketiga pada posisi ke-n-2(posisi ke-4).
Proses 4:
Data 1-2:A[1]<A[2]
Data 2-3:A[2]>A[3] ditukar
3 2 4 5 6 7
Akhir pada proses keempat adalah menempatkan data terbesar keempat pada posisi ke-n-3(posisi ke 3)
Proses 5
Data 1-2:A[1]>A[2]
Data 2-3:A[2]>A[3] ditukar
2 3 4 5 6 7
Akhir dari proses kelima atau teakhir adalah menempatkan data terbesar kelima dan keenam pad posisi ke- dan ke-n-5(posisi ke-2 dan ke-1).
Penyajian pseudecode algoritma bbble sor:
For i=1 to (n-1) do
For j=1 t (n-i) do
If A[] >A[j+1] then
Temp = A[j]
A[j]=A[j+1]
A[j+1]=temp
Endif
Endfor
Endfor
Implementasi :
/*Bubble sort menaik */
#include<studio.h>
Main(){
Int I,n,j,temp;
Int A[100];
Printf(“Bubble sort menaik\ n”);
Printf(“Banyak data :”);
Scantf(”%d”,&n);
For (i=0;i<n;i++)
{
Printf(”Data ke-%d :”,i+1);
Scanf(”%d”,&A[i]);
}
For (i=0;i<n-1;i++)
{
For (j=0;j<(n-i);j++){
If(A[j] >A[j+1])
{
Temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
Printf(“Setelah terurut :\n”);
For(i=0;i<n;i++)
Printf(“%d”,A[i]);
}
3. Insertion Sort
Proses yang terjadi pada pengurutan dengan menggunakan metode insertion sort dimulai dari data ke-2, kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama diandaikan memang sudah pada tempatnya.
Pengurutan Naik
Mulai dari data ke dua , nilainya dibandingkan dengan data-data sebelumnya, kemudian mencari posisi yang tepet untuk menyisipkannya.
Algoritma pedecode:
For i=2 to n do
Temp=A[i]
{ambil elemen A[i] agar nilainya tidak dihilang karena tetimpa penggeseran }
A[0]=temp {sentinel}
J=i-1
{cari posisi yang tepat untuk A[i]di dalam A[1..i-1] sambil menggeser}
While A[j]>temp do
A[j+1]=A[j]{penggeseran}
J=j-1
Endwhile
A[j+1]= temp {menemukan tempat yang tepat }
End for
Implementasi program :
#include<stdio.h>
Main()
{
Int n,I, temp , j, k, m, h;
Int A[100];
Printf(“insertion sort \n);
Printf(“Banyak data:”);
Scanf(“%d”.&n);
For (i=0;i<n;i++)
{
Prinf(“Data ke-%d : “,i+1);
Scanf(”%d”,&A[i]);
}
For (i = 1; i<n; i++)
{
Temp=A[i];
J=i-1
Printf (”\n Proses i=%d \n”, i+1);
Printf(”Sebelum proses = = > ”);
For(h=0; h<n;h++)printf(”%d ”,A[h]);
Printf(“\n”);
Printf(“temp = d \n”,temp);
Printf(“proses \n”);
While(A[j]>temp)
{
A[j+1=A[j];
J=j-1;
For(k=0;k<n;k++)printf(“%d “,A[k])printf(“\n”);
}
A[j+1]=temp;
Printf(”setelah proses i=%d = = > “, i+1);
For(m=0;m<n;m++)printf(“%d “,A[m] );
Printf(“\n”);
}
Printf(“\n Setelah urut \n”);
For(i=0;i<n;i++)
Printf(“%d “,A[i]);
}
4. Merge Sort
Metode merge Sort adalah menggabungkan dua buah array yang sudah terurut. Untuk mengurutkan masing masng array kita bisa menggunakan selection sort, bubble sort, maupun insertion sort.
Pengurutan naik(ascending)
2 buah array yang masing-masing terurut naik kan digabungkan menjadi terurut naik.
Contoh kasus:
Array petama : 5 8 12 15 20 25 29
Array kedua : 4 6 21 22
Proses penggabungan dua buah array diatas menjadisebuah aray yang terurut naik adalah sebagai berikut:
1 2 3 4 5 6 7 a=1s/d m
A = 5 8 12 15 20 25 29
1 2 3 4 b=1s/d n
B = 4 6 21 22
C= c=1s/dm+n
A[1]>B[1]
C[1] B[1]
C=4
B=1+1=2
A[1]<B[2]
C[2] A[1]
C=1+1=2
A[2] > B[2]
C[3] B[6]
C=4 5 6
B= 2+1 = 3
A[3]<B[3]
C[5] A[3]
C=4 5 6 8 12
A= 3 + 1 = 4
A[4] > B[3]
C[6] B[4]
C=4 5 6 8 12 15
B= 4+1 = 5
A[5]<B[3]
C[7] A[5]
C=4 5 6 8 12 15 20
A= 5 + 1 = 6
A[6] > B[3]
C[8] B[3]
C=4 5 6 8 12 15 20 21
B= 3+1 = 4
A[6]<B[4]
C[9] A[4]
C=4 5 6 8 12 15 20 21 22
A= 4 + 1 = 5
Array terdiri dari empat elemen. Padaakhir proses ini, setelah indexpada array kedua dinaikan ternyata indeksnya telah melampui ukuran array kedua yang sesungguhnya. Berarti semua elemen array kedua sudah hais terlebih dahulu dan masuk kedalam array gabungan
b>4 artinyab>n
elemen array pertama yang masih tersisa akan dimasukan ke dalam array gabungan satu persatu.
A=5+1=6
C[10] A[6]
C = 4 5 6 8 12 15 20 21 22 25
A=6+1=7
C[11] A[7]
C= 4 5 6 8 12 15 20 21 22 25 29
Algorima dengan pseudecode
a=0
b=0
c=0
For i=1 to m+n
If a>=m or b>=n then end for
If(A[a]<B[b])
C[c]=A[a]
a++
c++
Else if (A[a]>=B[b])
C[c] =B[b]
b++
c++
end if
end if
end for
if(b<n)
for i=b to n-1
c[c] = b[i]
c++
else if(<m)
foi= a to m-1
C[c]=A[i]
c++
sendif
endif
Implementasi program
#include<studio.h>
Main(){
Int a,m,n,ij,iexmin,temp
Int A[100];
Int B[100];
Int C[200];
Printf(“mege sort menaik\n”);
Printf”banyaknya data array ptama:”);
Scanf(“%d”,&m);
Or(i=0;i<m;i++){
Printf(”Data ke-%d:”+1);
Scanf(“%d”,&A[i]);
}
For (i=0;i<m-1;i++)
{
Indexmin=i;
For(j=i+1;j<m;j++)
{
If(A[indexmin]>A[j])
Indexmin=j;
}
If (A[i] !=A[idexmin])
{
Temp = A[i];
A[i]=A[indxmin];
A[indexmin]=temp;
}
}
Printf(“Banyak data array kedua :”);
Scanf(“%d”,&n);
For(i=0;i<n;i++)
{
Printf(”Data ke-%d:”i+1);
Scanf(”%d”,&B[i]);
}
For(i=0;i<n-1;i++)
{
Indexmin=i;
For(j=i+1;j<n;j++)
{
If(B[indexmin]>B[j])
Indexmin=j;
}
If(B[i] !=B[indexmin])
{
Temp= B[i];
B[i]=B[indexmin];
B[indexmin]=tem;
}
}
Printf(“setelah urut \n”);
a=0;
b=0;
c=0;
for(i=1;i<m+n;i++)
{
If(a>=m||b>=n)break;
If(A[a]<B[b])
{
C[c]=A[a]
a++;
c++;
}
Else if(A[a]>=B[b])
{
C[c]=B[b];
b++;
c++;
}
}
{
For (i=b;i<n;i++)
{
C[c] = B[i];
c++;
}
}
Else if(a<m)
{
For(i=a;i<m;i++)
{
C[c]=A[i];
c++;
}
}
Printf(”array prtama :\n”);
For(a=0;a<m;a++)printf(”%d “,A[a]);
Printf(“\n”);
Printf(”array kedua :\n”);
For(a=0;a<m;a++)printf(”%d “,B[b]);
Printf(“\n”);
Printf(“array gabungan :\n”);
For(i=0;i<m+n;i++)
Printf(“%d “,C[i]);
Printf(”\n”);
}
Oke teman semua, tetap semangat ya,Go Succes..
Wassalamuallaikum wr.wb
From : Jumdapi okta
Prosus Teknik Informatika
0 komentar:
Posting Komentar