Comparative Analysis of Sorting Algorithms: TimSort Python and Classical Sorting Methods

Firmansyah Rekso Wibowo, Muhammad Faisal

Abstract


The sorted() function within the Python programming language has emerged as the primary choice among developers for sorting operations. Consequently, this study offers a comparative analysis of various classical sorting algorithms and Python's built-in sorting mechanisms, with the objective of identifying the most time-efficient sorting algorithm. The analysis involves assessing the time complexity of each algorithm while handling data arrays ranging from 10 to 1,000,000 elements using Python. These arrays are populated with randomly generated numeric values falling within the range of 1 to 1000. The benchmark algorithms utilized encompass Heap Sort, Shell Sort, Quick Sort, and Merge Sort. A looping mechanism is applied to each algorithm, and their execution speeds are gauged utilizing the Python 'time.perf_counter()' library. The findings of this study collectively indicate that Python's standard algorithm, surpasses classic sorting algorithms, including Heapsort, Shellsort, Quicksort, and Mergesort, in terms of execution.

Keywords


Quicksort, Mergesort, Timsort, Heapsort, Shellsort

Full Text:

PDF

References


H. Cormen Thomas, E. Leiserson Charles, L. Rivest Ronald, Stein Clifford. Introduction to Algorithms: Third Edition. MIT Press, 2009. Massachusetts Institute-of-Technology-Cambridge. https://dahlan.unimal.ac.id/files/ebooks/2009%20Introduction%20to%20Algorithms%20Third%20Ed.pdf.

Kurnia, Firdilla (2022, December 28). Algoritma: Pengertian, Ciri-ciri, Jenis, Serta Fungsi dan Manfaatnya.Dailysocial. https://dailysocial.id/post/algoritma-adalah.

Laitinen, S. (2010). Better Games Through Usability Evaluation and Testing. http://www.gamasutra.com/view/feature/2333/better_games_through_u...

Anggraini Kusumaningrum, 2020. Perbandingan Kecepatan Antara Selection Sort, Insertion Sort, Dan Bubble Sort. Teknomatika: Jurnal Informatika Dan Komputer, 3(1), 63-70. Retrieved from https://ejournal.unjaya.ac.id/index.php/teknomatika/article/view/363.

Nicolas Auger, Vincent Jugé, Cyril Nicaud, Carine Pivoteau, 2018. On the Worst-Case Complexity of TimSort. France: 26th Annual European Symposium on-Algorithms-(ESA 2018).-

DOI: https://doi.org/10.48550/arXiv.1805.08612.

Canaan, C. et al. “Popular sorting algorithms - TI Journals.” World Applied Programming (2012): n. Pag. https://www.semanticscholar.org/paper/Popular-sorting-algorithms-TI-Journals-Canaan-Garai/432ba0382141cacef751199288147d4daaeb3cd7

Rumapea, Yolanda Y. P. Analisis Perbandingan Metode Algoritma Quick Sort dan Merge Sort dalam Pengurutan Data terhadap Jumlah Langkah dan Waktu. Methodika, vol. 3, no. 2, 2017, pp. 5-9, https://media.neliti.com/media/publications/345425-analisis-perbandingan-metode-algoritma-q-e2e2d79a.pdf.

Oladipupo Esau Taiwo, Abikoye Oluwakemi Christianah, Akande Noah Oluwatobi, Kayode Anthonia Aderonke, Adeniyi Jide kehinde, Comparative Study Of Two Divide And Conquer Sorting Algorithms: Quicksort And Mergesort, Procedia Computer Science, Volume 171, 2020, Pages 2532-2540,-ISSN-1877-0509, https://doi.org/10.1016/j.procs.2020.04.274.

S. Mansoor Sarwar, Mansour H.A. Jaragh, Mike Wind, An empirical study of the run-time behavior of quicksort, Shellsort and mergesort for medium to large size data, Computer Languages, Volume 20, Issue 2, 1994,-Pages-127-134,-ISSN-0096-0551, https://doi.org/10.1016/0096-0551(94)90019-1.

Abu Sara, M. R., Klaib, M. F. J., & Hasan, M. (2020). Ems: An Enhanced Merge Sort Algorithm By Early Checking Of Already Sorted Parts. International Journal of Software Engineering and Computer Systems,-5(2),-15–25.-Retrieved-from https://journal.ump.edu.my/ijsecs/article/view/3525.

Alkharabsheh, Khalid & Alturani, Ibrahim & Alturani, Abdallah & Zanoon, Dr.Nabeel. (2013). Review on Sorting Algorithms A Comparative Study. International Journal of Computer Science and Security (IJCSS). 7. https://www.researchgate.net/publication/259911982_Review_on_Sorting_Algorithms_A_Comparative_Study.

Adesina, Opeyemi. (2013). A Comparative Study of Sorting Algorithms. African Journal of Computing & ICT.-6.-199-206. https://www.researchgate.net/publication/288825600_A_Comparative_Study_of_Sorting_Algorithms.

Al Rivan, Muhammad Ezar. "Perbandingan Kecepatan Gabungan Algoritma Quick Sort Dan Merge Sort Dengan Insertion Sort, Bubble Sort Dan Selection Sort." Jurnal Teknik Informatika dan Sistem Informasi, vol. 3, no. 2, 2017, doi: 10.28932/jutisi.v3i2.629.

You Yang, Ping Yu and Yan Gan, "Experimental study on the five sort algorithms" 2011 Second International Conference on Mechanic Automation and Control Engineering, Inner Mongolia, China, 2011, pp. 1314-1317, doi: 10.1109/MACE.2011.5987184.

Krishna, Sai. (2017). Comparative Analysis of Bucket and-Radix-Sorting.

DOI: 10.13140/RG.2.2.13755.00807

Kazim, A. A Comparative Study of Well Known Sorting Algorithms. International Journal of Advanced Research in Computers. Science. 2016; 8(1):277-280. doi : https://doi.org/10.26483/ijarcs.v8i1.2903.

Mitra, Avik & Kothari, Jash & Ganguly, Annesa. (2019). Analysis Of Shellsort Algorithms. 10. 48-51. 10.26483/ijarcs.v10i3.643.

MacIver, David R. (11 January 2010). "Understanding Timsort, Part 1: Adaptive Merge Sort". Retrieved 28 October-2023. https://github.com/python/cpython/blob/main/Objects/listsort.txt.

Peters, Tim. "listsort.txt". CPython git repository. Retrieved-28-October-2023. https://svn.python.org/projects/python/trunk/Objects/listsort.txt.

"listsort.txt". Python source code. 18 May 2022. Archived from the original on 28 January 2016. https://hmn.wiki/id/Timsort.

Tim Peters. Timsort description, accessed 28 October 2023.-URL: http://svn.Python.org/projects/Python/trunk/Objects/listsort.txt.




DOI: https://doi.org/10.31326/jisa.v7i1.1785

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Firmansyah Rekso Wibowo, Muhammad Faisal

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

JOURNAL IDENTITY

Journal Name: JISA (Jurnal Informatika dan Sains)
e-ISSN: 2614-8404, p-ISSN: 2776-3234
Publisher: Program Studi Teknik Informatika Universitas Trilogi
Publication Schedule: June and December 
Language: Indonesia & English
APC: The Journal Charges Fees for Publishing 
Indexing:  EBSCO , DOAJ, Google Scholar, Arsip Relawan Jurnal Indonesia, Directory of Research Journals Indexing, Index Copernicus International, PKP Index, Science and Technology Index (SINTA, S4) , Garuda Index
OAI address: http://trilogi.ac.id/journal/ks/index.php/JISA/oai
Contact: jisa@trilogi.ac.id
Sponsored by: DOI – Digital Object Identifier Crossref, Universitas Trilogi

In Collaboration With: Indonesian Artificial Intelligent Ecosystem(IAIE), Relawan Jurnal Indonesia, Jurnal Teknologi dan Sistem Komputer (JTSiskom)

 

 

JISA (Jurnal Informatika dan Sains) is Published by Program Studi Teknik Informatika, Universitas Trilogi under Creative Commons Attribution-ShareAlike 4.0 International License.