SORTING

SOAL

1, Diketahui nilai data 5, 80, 13, 26, 78, 52, 66, 10, 18, 99. Hituhg ke dalam model buble sort(ascending) dan exchange sort (descanding)

2. Jelaskan mamfaat penggunaan model sorting denganmenggunakan bentuk algoritma

JAWABAN

1. Diketahui nilai data 5, 80, 13, 26, 78, 52, 66, 10, 18, 99. Hituhg ke dalam model buble sort(ascending) dan exchange sort (descanding)

a. Buble Sort

Memindahkan element sekarang dengan elemen berikutnya , jika elemen sekarang itu lebih besar / lebih kecil dari elemen berikutnya maka di tukar (berpindah posisi).

Proses Bubble Sort

1.  Ascending

- Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih besar maka tukar.

- Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih kecil maka tukar.

2.       Descending

- Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih kecil maka tukar.

- Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih besar maka tukar.

 

 

 

b. Exchange sort

Exchange sort itu sangat mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama dengan buble sort. Bedanya jika bubble sort proses pertukarannya harus sistematis, dari awal atau dari belakang. Sedangkan exchange sort proses pertukaran hanya akan dilakukan jika diperlukan saja.

Proses Exchange Sort

1.       Ascending

v  Jika terdapat elemen sebelumnya lebih besar dari elemen berikutnya maka tukar.

v  Jika terdapat elemen sesudahnya lebih kecil dari elemen sebelumnya maka tukar.

2.       Descending

v  Jika terdapat elemen sebelumnya lebih kecil dari elemen berikutnya maka tukar.

v  Jika terdapat elemen sesudahnya lebih besar dari elemen sebelumnya maka tukar.

 

 

 

2.    Jelaskan mamfaat penggunaan model sorting dengan      menggunakan bentuk algoritma

1. Buble Sort

            Bubble Sort adalah salah satu algoritma untuk sorting data, atau kata lainnya mengurutkan data dari yang terbesar ke yang terkecil atau sebaliknya (Ascending atau Descending).

Algoritma Buble Sort

o   Bandingkan posisi data i = 0 dan j = 1.

o   Jika data diposisi i lebih besar daripada data diposisi j, maka data diposisi i ditukar
dengan data diposisi j (swap). Jika tidak penukaran posisi tidak dilakukan.

o   Kemudian, lakukan perbandingan data diposisi i = 1 dan data diposisi j = 2.
Lakukan langkah 2, begitu juga untuk data berikutnya hingga i = N-2 dan j = N-1.

o   Ulangi langkah 1, 2 dan 3 untuk data diposisi 0 sampai dengan data diposisi N-2,
karena data di posisi N-1 adalah data dengan nilai terbesar.

o   Untuk tahapselanjutnya data yang dibandingkan akan semakin berkurang sebab data dengan nilai yang lebih besar akan terposisi dibagian sebelah kanan data.

2. Exchange Sort

            Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot).

           

Algoritma Buble Sort

Prosedur/Algoritma/Syntax Exchange Sort ASSCENDING
for (int i=0; i< 6-1; i++)
{
for (int j = (i+1); j data[j])
{
t = data [j];
data [j] = data [i] ;
data [i] = t;
}

3.  Heap Sort
Heapsort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima O(n log(n)) yang menggunakan struktur data heap. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap. Heap merupakan sebuah pohon biner hampir lengkap dimana isi dari simpul ayah selalu lebih besar dari isi simpul anak-anaknya sehingga simpul akar selalu merupakan elemen terbesar.

Prosedur/Algoritma/Syntax Heapsort;
function heapSort(a, count) is
input: sebuah larik tidak terurut a dengan panjang length
(pertama letakkan a dalam max-heap) heapify(a, count)
end := count -1
while end > 0 do
remove ( )
reheapify ( )
end := end – 1

4.  Insertion sort
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

Prosedur/Algoritma/Syntax Insertion sort
void insertion_sort(){
int temp;
for(int i=1;i<n;i++) {
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0)
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp; }

5.  Quick Sort
Metode ini dikembangkan oleh CAR Hoare. Secara garis besar metode ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A yang membunyai N elemen. Kita pilih sembarang elemen dari data tersebut, biasanya elemen pertama, misalnya X. Kemudain semua elemen tersebut disusun dengan menempatkan X pada posisi J sedemikian rupa shingga elemen ke 1 sampai ke J-1 mempuyai nilai lebih besar dari X. Sampai berikutnya diulang untuk  setiap sub data .

Prosedur/Algoritma/Syntax Quick Sort
void quicksort (int *arr, int kr, int kn)
{
int i, j, k;
if (kr<kn)
{
j=kr;
k=kn+;
do
{
do j++; while (j <= kn && arr[j] < arr[kr]);
do k–; while (arr[k] > arr[kr]);
if (j<k) tukar (&arr[j], &arr[k]);
}
while (j <= k);
tukar (&arr[kr], &arr[k]);
quicksort (arr, kr, k-1);
quicksort (arr, k+1, kn);
} }

6. Merge sort
 Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari
metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang
sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table
sehingga dalam keadaan urut.

Prosedur/Algoritma/Syntax Quick Sort Merge sort
void mergesort (int *x, int n)
{
int *r, i, j, k, l1, l2, u1, u2, size;
r = (int *) malloc (n * sizeof (int));
size = 1;
while (size < n)
{
l1 = 0; k = 0;
while (l1+size < n)
{
l2 = l1+size;
u1 = l2 – 1;
u2 = (l2 + size – 1 < n) ? l2 + size – 1 : n-1;
for (i=l1; j=l2; i<=u1 && j<=u2; k++)
r[k] = (x[i] <= x[j]) ? x[i++] : x[j++];
while (i<=u1) r[k++] = x[i++];
while (j<=u2) r[k++] = x[j++];
l1 = u2+1;
}
for(i=l1; k<n; i++) r[k++] = x[i];
for(i=0; i<n; i++) x[i] = r[i];
size *= 2;
}
free(r); }

7.  Shell Sort
Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu. Insertion sort membandingkan elemen–elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak menulangi atau merusak hasil sorting sebelumnya.

Prosedur/Algoritma/Syntax Shell Sort
void shellsort (int *r, int lo, int hi)
{
int d, i, j, temp;
for (d = hi – lo + 1; d>1; )
{
if (d>5) d = 1;else d=(5*d – 1)/11;
for (i=hi – d; i>=lo; i–)
{
temp = r[i];
for (j=i+d; (j<=hi) && (temp>r[j]); j+=d)
r[j-d] = r[j];
r[j-d] = temp;
}
}
}

8. Selection sort

Memindahkan elemen dengan cara membandingkan elemen sekarang dengan elemen yang berikutnya sampai dengan elemen terakhir . Jika ditemukan elemen lain yang lebih kecil / lebih besar dari elemen sekarang maka dicatat posisinya dan kemudian ditukar dan begitu seterusnya.                

Proses Selection Sort

1.       Ascending

v  Elemen yang paling besar diletakkan di akhir.

v  Elemen yang paling kecil diletakkan di awal.

2.       Descending

v  Elemen yang paling kecil diletakkan di akhir.

v  Elemen yang paling besar diletakkan di awal.