METHODOLOGY FOR TEACHING THE QUICKSORT ALGORITHM FOR ARRAYS IN THE PYTHON PROGRAMMING LANGUAGE
Keywords:
Python, array, list, quicksort, recursion, divide and conquer, partitioning, algorithm complexity, PRIMM, programming teaching methodology.Abstract
The article proposes a methodology for teaching the quicksort algorithm for arrays (lists) in the course “Fundamentals of the Python Programming Language”. Quicksort combines three ideas that are difficult for novices – recursion, the divide-and-conquer strategy and in-place partitioning – so the methodology introduces them gradually. It is based on the PRIMM approach (Predict – Run – Investigate – Modify – Make) and consists of five stages: modelling recursion by hand with number cards, completing a partition trace table and a recursion tree, coding in two steps (first a short list-based version, then an in-place version with Lomuto partitioning), visualising the call stack and testing automatically, and analysing the average and worst-case complexity of the algorithm experimentally. The article presents reference Python implementations, an execution trace, the results of a computational experiment on the number of comparisons, typical student errors, a comparison with other sorting methods and a plan for a pedagogical experiment.
References
1. Decree of the President of the Republic of Uzbekistan No. PF-6079 of 5 October 2020 “On approval of the Digital Uzbekistan – 2030 strategy and measures for its effective implementation”.
2. Hoare C.A.R. Quicksort // The Computer Journal. – 1962. – Vol. 5, No. 1. – P. 10–16.
3. Knuth D.E. The Art of Computer Programming. Vol. 3: Sorting and Searching. 2nd ed. – Reading, MA: Addison-Wesley, 1998. – 780 p.
4. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 4th ed. – Cambridge, MA: MIT Press, 2022. – 1312 p.
5. Sedgewick R. Implementing Quicksort programs // Communications of the ACM. – 1978. – Vol. 21, No. 10. – P. 847–857.
6. Bentley J.L., McIlroy M.D. Engineering a sort function // Software: Practice and Experience. – 1993. – Vol. 23, No. 11. – P. 1249–1265.
7. Wing J.M. Computational thinking // Communications of the ACM. – 2006. – Vol. 49, No. 3. – P. 33–35.
8. Kahney H. What do novice programmers know about recursion? // Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI ’83). – 1983. – P. 235–239.
9. Sentance S., Waite J., Kallia M. Teaching computer programming with PRIMM: a sociocultural perspective // Computer Science Education. – 2019. – Vol. 29, No. 2–3. – P. 136–176.
10. Bell T., Witten I.H., Fellows M. CS Unplugged: An enrichment and extension programme for primary-aged students. – Christchurch: University of Canterbury, 2015.
11. Parsons D., Haden P. Parson’s programming puzzles: a fun and effective learning tool for first programming courses // Proceedings of the 8th Australasian Conference on Computing Education. – 2006. – Vol. 52. – P. 157–163.
12. Guo P.J. Online Python Tutor: embeddable web-based program visualization for CS education // Proceedings of the 44th ACM Technical Symposium on Computer Science Education (SIGCSE ’13). – 2013. – P. 579–584.
13. Sorva J. Notional machines and introductory programming education // ACM Transactions on Computing Education. – 2013. – Vol. 13, No. 2. – Article 8.
14. Lister R., Adams E.S., Fitzgerald S., et al. A multi-national study of reading and tracing skills in novice programmers // ACM SIGCSE Bulletin. – 2004. – Vol. 36, No. 4. – P. 119–150.
15. Hake R.R. Interactive-engagement versus traditional methods: A six-thousand-student survey of mechanics test data for introductory physics courses // American Journal of Physics. – 1998. – Vol. 66, No. 1. – P. 64–74.