Tugas Sorting Kel12 Revisi

TUGAS SISTEM BERKAS

MAKALAH ALGORITMA SORT

KELAS H KELOMPOK 12 ANGGOTA : 1. 2. 3. 4. 5.

REZA FAKHRUL ISFAQ SYAMSUL ARIEFIN NUR FAUZY DADANG SETYAHADI KHAIRIYAMIN IMAN

06.2003.1.90039 06.2006.1.03967 06.2001.1.02634 06.2000.1.02222 06.2000.1.02166

TEKNIK INFORMATIKA INSTITUT TEKNOLOGI ADHI TAMA SURABAYA SURABAYA 2007

ALGORITMA SORT Pengurutan data sangat penting untuk data yang bertipe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun) Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu. Contoh: Data Acak : 5 6 8 1 3 25 10 Ascending : 1 3 5 6 8 10 25 Descending : 25 10 8 6 5 3 1

DEKLARASI ARRAY UNTUK SORTING Deklarasikan: int data[100]; int n; //untuk jumlah data

Fungsi untuk Tukar 2 Buah Data: public tukar(int *a,int *b){ int t=*a; *a=*b; *b=t; }

METODE PENGURUTAN DATA Pengurutan berdasarkan perbandingan (comparison-based sorting) o Bubble Sort, Exchange Sort Pengurutan berdasarkan prioritas (priority queue sorting method) o Selection Sort, Heap Sort Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method) o Insertion Sort, Tree Sort Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method) o Quick Sort, Merge Sort Pengurutan berkurang menurun (diminishing increment sort method) o Shell Sort

BUBBLE SORT Metode sorting termudah akan tetapi merupakan metode yang paling lambat. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar. Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar. Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya.

Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

Gb. Proses 1 Metode Buble Sort

Pada gambar diatas, pegecekan dimulai dari data yang paling akhir, kemudian dibandingkan dengan data di depannya, jika data di depannya lebih besar maka akan ditukar.

Gb. Proses 2 Metode Buble Sort

Pada proses kedua, pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasti sudah paling kecil.

Gb. Proses 3 Metode Buble Sort

Gb. Proses 4 Metode Buble Sort

Gb. Proses 5 Metode Buble Sort

Hasil Analisa Empiris Efisiensi Metode Buble Sort

Gb. Grafik Efisiensi metode Buble Sort

Procedure Buble Sort //Versi 1 public bubble_sort(){ for(int i=1;i=i;j--){ if(data[j]data[j+1]) tukar(&data[j],&data[j+1]); //descending } } }

EXCHANGE SORT Sangat mirip dengan Bubble Sort Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort Pebedaan : dalam hal bagaimana membandingkan antar elemen elemennya. 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). Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

Gb. Awal (Penentuan Pivot) metode Excange Sort

Gb. Proses 1 metode Exchange Sort

Gb. Proses 2 metode Exchange Sort

Gb. Proses 3 metode Exchange Sort

Gb. Proses 4 metode Exchange Sort

Gb. Proses 5 metode Exchange Sort

Procedur e Exchange Sort public exchange_sort() { for (int i=0; i
HEAP SORT Merupakan salah metode terbaik untuk data dengan jumlah besar, tetapi paling lambat dari O(n log n) algoritma sorting, dibandingkan metode Merge Sorting dan Quick Sorting. Pengurutan dimulai dengan data yang bernilai paling besar ditempatkan di posisi paling akhir, dan data yang terkecil di posisi paling awal. Membutuhkan 2 array untuk proses pengurutan, array pertama untuk data sebelum diurutkan, dan arry ke-2 untuk penempatan hasil pengurutan.

contoh Di posisi Top, setelah 9 diposisikan di posisi terakhir, 9 diganti 4 4 di ganti dengan 7 (7 lebih besar dr 3), membuat 4 sebagai top dr subtree, dibawahnya ada 5 yang masih aktif, maka nanti keduanya dipindah 4 diganti posisi oleh 5

7 diganti posisi oleh 4

4 diganti posisi oleh 5

Gb Metode Heap Sort

5 diganti posisi oleh 2

2 diganti posisi oleh 4

4 diganti posisi oleh 1

1 diganti posisi oleh 3

3 diganti posisi oleh 2

2 diganti posisi oleh 1, sekarang proses sudah selesai Gb Metode Heap Sort

Hasil Analisa Empiris Efisiensi Metode Heap Sort

Gb. Grafik Efisiensi metode Heap Sort

Procedure Heap Sort class Heap { public heapSort(int numbers[], int array_size) { int i, temp; for (i = (array_size / 2)-1; i >= 0; i--) siftDown(numbers, i, array_size); for (i = array_size-1; i >= 1; i--) { temp = numbers[0]; numbers[0] = numbers[i];

numbers[i] = temp; new siftDown(numbers, 0, i-1); } } private siftDown(int numbers[], int root, int bottom) { int done, maxChild, temp; done = 0; while ((root*2 <= bottom) && (!done)) { if (root*2 == bottom) maxChild = root * 2; else if (numbers[root * 2] > numbers[root * 2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1; if (numbers[root] < numbers[maxChild]) { temp = numbers[root]; numbers[root] = numbers[maxChild]; numbers[maxChild] = temp; root = maxChild; } else done = 1; } } }

SELECTION SORT Merupakan kombinasi antara sorting dan searching Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Gb. Proses 1 Metode Selection Sort

Gb. Proses 2 Metode Selection Sort

Gb. Proses 3 Metode Selection Sort

Gb. Proses 4 Metode Selection Sort

Gb. Proses 5 Metode Selection Sort

Hasil Analisa Empiris Efisiensi Metode Selection Sort

Gb. Grafik Efisiensi metode Selection Sort

Procedure Selection Sort public selection_sort(){ for(int i=0;i
INSERTION SORT Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

Gb. Proses 1 Metode Insertion Sort

Gb. Proses 2 Metode Insertion Sort

Gb. Proses 3 Metode Insertion Sort

Gb. Proses 4 Metode Insertion Sort

Gb. Proses 5 Metode Insertion Sort

Hasil Analisa Empiris Efisiensi Metode Insertion Sort

Gb. Grafik Efisiensi metode Insertion Sort

Procedure Insertion Sort public insertion_sort(){ int temp; for(int i=1;itemp && j>=0){ data[j+1] = data[j]; j--; } data[j+1] = temp; } }

MERGE SORT Data yang akan diurutkan dibagi menjadi 2 bagian, dan di tempatkan di 2 array yang berbeda. Merge Sort membutuhkan 3 array, 1 array untuk menempatkan hasilnya, dan sisanya merupakan data yang akan di urutkan. Ke-2 array tersebut di urutkan kemudian disimpan pada masing-masing array, lalu digabungkan pada array yang pertama. Misal : Data a, dipecah dalam array ke-2 dan array ke-3, kemudian array ke-2 dan array ke-3 melakukan proses pengurutan. Setelah mendapatkan hasil, hasil pengurutan dari array ke-2 dan ke-3digabungkan dalam array ke-1.

Gb. Proses 1 Metode Merge Sort

Gb. Proses 2 metode Merge Sort

Gb. Proses 3 Metode Merge Sort

Gb. Proses 4 Metode Merge Sort

Gb. Proses 5 dan 6 Metode Merge Sort

Gb. Proses 7 Metode Merge Sort

Hasil Analisa Empiris Efisiensi Metode Merge Sort

Gb. Grafik Efisiensi metode Merge Sort

Procedure Merge Sort class Merge { public mergeSort(int numbers[], int temp[], int array_size) { new m_sort(numbers, temp, 0, array_size - 1); } private m_sort(int numbers[], int temp[], int left, int right) { int mid; if (right > left) { mid = (right + left) / 2; new m_sort(numbers, temp, left, mid); new m_sort(numbers, temp, mid+1, right); new merge(numbers, temp, left, mid+1, right); } } private merge(int numbers[], int temp[], int left, int mid, int right) { int i, left_end, num_elements, tmp_pos; left_end = mid - 1; tmp_pos = left; num_elements = right - left + 1; while ((left <= left_end) && (mid <= right)) { if (numbers[left] <= numbers[mid]) { temp[tmp_pos] = numbers[left]; tmp_pos = tmp_pos + 1; left = left +1; } else { temp[tmp_pos] = numbers[mid]; tmp_pos = tmp_pos + 1; mid = mid + 1; } } while (left <= left_end) { temp[tmp_pos] = numbers[left]; left = left + 1; tmp_pos = tmp_pos + 1; } while (mid <= right) { temp[tmp_pos] = numbers[mid]; mid = mid + 1; tmp_pos = tmp_pos + 1; } for (i=0; i <= num_elements; i++) { numbers[right] = temp[right];

right = right - 1; } } }

QUICK SORT Merupakan metode yang sangat cepat dengan teori algoritma yang mudah, tetapi dalam penulisan programnya sangat sulit. Merupakan kombinasi antara metode Exchange Sort dan metode Merge Sort. Ada empat langkah dalam melakukan metode ini, yaitu: o If (n<=1), maka kembali ke awal atau mengehentikan proses. o Ambil satu elemen dari array sebagai Pusat (Pivot) seperti halnya di metode Exchange Sort. o Array dipecah menjadi dua bagian, pecahan array pertama terdiri dari elemen yang lebih besar dari Pivot, sedangkan pecahan array ke-2 memiliki elemen yang lebih kecil dari Pivot. o Kemudian, kedua pecahan tersebut melakukan proses pengurutan.

Gb Proses 1 Metode Quick Sort

Gb. Proses 2 Metode Quick Sort

Gb. Proses 3 Metode Quick Sort

Gb. Proses 4 Metode Quick Sort

Gb. Proses 5 Metode Quick Sort

Gb. Proses 6 Metode Quick Sort

Gb. Proses 7 Metode Quick Sort

Hasil Analisa Empiris Efisiensi Metode Quick Sort

Gb. Grafik Efisiensi metode Quick Sort

Procedure Quick Sort Class Quick { public quickSort(int numbers[], int array_size) { new q_sort(numbers, 0, array_size - 1); } private q_sort(int numbers[], int left, int right) { int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = numbers[left]; while (left < right) { while ((numbers[right] >= pivot) && (left < right)) right--; if (left != right) { numbers[left] = numbers[right];

left++; } while ((numbers[left] <= pivot) && (left < right)) left++; if (left != right) { numbers[right] = numbers[left]; right--; } } numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot) new q_sort(numbers, left, pivot-1); if (right > pivot) new q_sort(numbers, pivot+1, right); } }

SHELL SORT Merupakan metode O(n2) yang sangat efisien dan komplek. Diciptakan oleh Donald Shell tahun 1959. Merupakan metode berupa Increment Sort, dan lebih dikenal dengan “comb sort” dalam dunia pemrograman yang belum sempurna. Konsepnya hampir sama dengan metode Insertion Sort. Rangkaian data :

3

9

8

4

7

Membagi rangkaian menjadi 3 bagian Left Arr Mid Arr

3

4

9

Right Arr

7

8

Gb Proses 1 Motode Shell Sort Pindahkan elemen, jika elemen kiri lebih besar dari elemen kanan

3

4

7

9

8

Gb Proses 2 Motode Shell Sort Gabungkan ketiga bagian, dalam satu rangkaian, dengan disusun satu per satu elemen dari angka terkecil.

3

4

7

8

9

Gb Proses 3 Motode Shell Sort

Hasil Analisa Empiris Efisiensi Metode Shell Sort

Gb. Grafik Efisiensi metode Selection Sort

Procedure Shell Sort class Shell_Sort { public shellSort(int numbers[], int array_size) { int i, j, increment, temp; increment = 3; while (increment > 0) { for (i=0; i < array_size; i++) { j = i; temp = numbers[i]; while ((j >= increment) && (numbers[j-increment] > temp)) { numbers[j] = numbers[j - increment]; j = j - increment; } numbers[j] = temp; } if (increment/2 != 0) increment = increment/2; else if (increment == 1) increment = 0; else increment = 1; } } }

DAFTAR PUSTAKA http://linux.wku.edu http://lecturer.ukdw.ac.id http://selikoer.files.wordpress.com