ANALISIS KEBUTUHAN WAKTU ALGORITMA INSERTION SORT, MERGE SORT, DAN QUICK SORT DENGAN KOMPLEKSITAS WAKTU

albar Pratama, Anita Desiani, Irmeilyana Irmeilyana

Abstract

Sorting is a crucial problem in data processing or database. Data  processing will be more simple if the data has been sorted. Sorting problem requires special  techniques to make the process of sorting faster. The techniques are named as sorting algorithms. The reliability of an algorithm can be measured by its time complexities. The time complexity T(n) is the number of operations performed in an algorithm for N data input. One of time complexities is Big-O or worst case. The Worst case (Big-O) is a time complexities for the worst condition of an algorithm.   This study will analyze the time complexity of the algorithms Insertion Sort, Merge Sort and Insertion Sort based on their Big-O (worst case). Each algorithm will be calculated its complexity time in two ways. The first is calculated based on their steps in

sorting process and the second is calculated based on their coding and running program using C++. The time complexity of Merge Sort is O(n log n) and time complexity of Quick Sort and Insertion Sort is O(n2), it means the time complexity of Merge Sort is less and faster for large N data input than Quick Sort and Insertion Sort. Otherwise Insertion Sort is faster for small N data input than Merge Sort and Quick Sort. Quick sort needs much time to sort data not only for small N data input but also for large N data input. It means Quick Sort doesn’t work well in worst case.

Keywords

Sorting, Insertion Sort, Quick Sort, Merge Sort, Time Complexity, Worst Case, Big-O

PDF

References

R. Munir, Algoritma & Pemrograman Dalam Bahasa Pascal dan C. Bandung: Informatika, 2011.

S. Palui, S., Gupta, “Unique Sorting Algorithm with Linear Time & Space Complexity,” Int. J. Res. Eng. Technol., vol. 3, No. 11, pp. 264–268, 2014.

D. Aho. Alfred, V. Sethi. Ravi. Ullman. Jeffrey, Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.

H. A. Fatta, Dasar Pemrograman C++ Disertai dengan Pengenalan Pemrograman Berorientasi Objek. Yogyakarta: Andi, 2006.

B. Raharjo, Teknik Pemprograman Pascal. Bandung: Informatika, 2005.

M. Canaan, C. Garai, M. S., Daya, “Popular Sorting Algorithms,” World Appl. Program., vol. 1, pp. 62–71, 2011.

S. Mehta, D. P., Sahni, Handbook of Data Structures and Applications. USA: Chapman & Hall/CRC Computer and Information Science Series, 2005.

A. Levitin, Introduction to The Design and Analysis of Algorithms. Addison-Wesley, 2007.

U. . Azizah, “Perbandingan Detektor Tepi Prewit dan Detektor Tepi Laplacian Berdasarkan Kompleksitas Waktu dan Citra Hasil,” J. UPI., vol. 5, 2013.

M. Azmoodeh, Abstract Data Types and Algorithms. Macmillan Education, 1988.

D. W. Nugraha, “Penerapan Kompleksitas Waktu Algoritma Prim untuk Menghitung Kemampuan Komputer Dalam Melaksanakan Perintah,” J. Ilm. Foristek, vol. 2, No. 2, pp. 195–202, 2012.

R. Munir, Matematika Diskrit. Bandung: Informatika, 2005.

A. . Estrada S., “Telaah Waktu Eksekusi Program Terhadap Kompleksitas Waktu Algoritma Brute Force dan Divide and Conquer dalam Penyelesaian Operasi List,” J. Ilmu Komput. dan Teknol. Inf., vol. 3 No. 2, 2003.

F. Sonita, A., Nurtaneo, “Analisis Perbandingan Algoritma Bubble Sort, Merge Sort, dan Quick Sort dalam Proses Pengurutan Kombinasi dan Huruf,” J. Pseudocode, vol. 2, no. 2, pp. 75–80, 2015.

R. Sedgewick, Algorithms in C++. Addison-Wesley, 1992.

Y. D. Astuti, Logika dan Algoritma. Bandung: Universitas Gunadarma, 2005.

Refbacks

• There are currently no refbacks.