Muhammad Fauzan Fikri 1506688802 PAPERDAA A [PDF]

Citation preview

Analisis Perbandingan Algoritma Sorting Introsort dan MyIdeaExperiment sort Muhammad Fauzan Fikri - 1506688802



1. Pendahuluan Hybrid algorithm adalah sebuah algoritma yang menggabungkan dua atau lebih algoritma yang bertujuan untuk meningkatkan performa atau reliability. Hybrid algorithm yang dibahas untuk paper ini berkaitan dengan masalah pengurutan atau sorting. Algoritma sorting tersebut adalah Introsort (Introspective sort), Timsort, dan MyIdeaExperiment sort. MyIdeaExperiment sort adalah algoritma sorting yang diimplementasi dengan mengambil ide dari Introsort. Tujuan dari paper ini adalah mengetahui performa dari Hybrid algorithm baru (MyIdeaExperiment sort) yang juga menggunakan Hybrid algorithm (Timsort) untuk dibandingkan dengan Hybrid algorithm murni yaitu Introsort yang merupakan gabungan dari Insertion sort, Quicksort, Heapsort. Paper ini membahas Introsort, Timsort, dan MyIdeaExperiment sort beserta analisis kompleksitas dan running time terhadap Array Decreasing Order, Array Acak, dan Array dengan nilai tiap elemen sama. Paper ini dibagi menjadi tujuh bagian. Bagian 1 berisi pendahuluan, bagian 2 berisi penjelasan dan cara kerja Introsort, bagian 3 berisi penjelasan dan cara kerja Timsort, bagian 4 berisi penjelasan dan cara kerja MyIdeaExperiment sort, bagian 5 berisi eksperimen, bagian 6 berisi analisis, dan bagian 7 berisi kesimpulan.



2. Penjelasan dan Cara Kerja Introsort Quicksort adalah salah satu algoritma sorting yang cukup baik dengan performa pada kasus rata rata adalah O(n log n). Namun pada kasus terburuk performanya bisa mencapai Θ(n2). Hal tersebut tentunya juga mempengaruhi performa dari program yang dibuat sehingga digunakan alternatif lain yaitu Heapsort. Heapsort memiliki performa Θ(n log n) untuk kasus terbaik, kasus rata – rata, dan kasus terburuk. Selain time complexity, Heapsort juga unggul dari sisi space complexity yaitu hanya membutuhkan O(1) dibandingkan dengan Quicksort yang butuh O(log(n)) dan Mergesort yang butuh O(n). Hal – hal tersebut akhirnya mendorong dibuatnya Introsort yang menggabungkan Quicksort dan Heapsort menjadi sebuah algoritma baru. Selain itu, Introsort juga menggunakan Insertion sort. Introsort sendiri digunakan untuk melakukan pengurutan pada C++ Standard Template Library.



Introsort bekerja seperti Insertion sort jika jumlah input elemen sangat kecil sedemikian hingga ukuran partisi yang dibuat kurang dari 16. Ukuran partisi tersebut berdasarkan penelitian dilakukan oleh pembuat kode Introsort. Ini merupakan kasus pertama. Introsort bekerja seperti Quicksort jika jumlah input elemen cukup besar sedemikian hingga ukuran partisi yang dibuat berada di antara dengan 16 sampai 2*log N (pada kode yang digunakan, sudah ditentukan maksimal ukuran partisi adalah 2*log N). Quicksort menggunakan metode median-of-3 dalam menentukan pivot untuk melakukan partisi dari jumlah input berukuran N menjadi N/2 lalu N/4 dan seterusnya. Ini merupakan kasus kedua. Jika ukuran partisi tersebut berkembang menjadi tree dengan kedalaman lebih dari 2*log N , maka dapat menyebabkan kompleksitas menjadi O(n2). Hal tersebut menjadi indikator yang membuat Introsort beralih menggunakan Heapsort yang mempunyai kompleksitas O(n log n) . Ini merupakan kasus ketiga. Berikut potongan kode Introsort : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42



#include using namespace std; void swapValue(int *a, int *b){ int *temp = a; a = b; b = temp; return; } void InsertionSort(int arr[], int *begin, int *end) { int left = begin - arr; int right = end - arr; for (int i = left+1; i = left && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } return; } int* Partition(int arr[], int low, int high){ int pivot = arr[high]; int i = (low - 1); for (int j = low; j