The week's pick
Random Articles
Reseach Article
AdaSort: Adaptive Sorting using Machine Learning
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 145 - Number 12 |
| Year of Publication: 2016 |
| Authors: Somshubra Majumdar, Ishaan Jain, Kunal Kukreja |
10.5120/ijca2016910726
|
Somshubra Majumdar, Ishaan Jain, Kunal Kukreja . AdaSort: Adaptive Sorting using Machine Learning. International Journal of Computer Applications. 145, 12 ( Jul 2016), 12-17. DOI=10.5120/ijca2016910726
Abstract
Sorting algorithms and their implementations in modern computing requires improvements in sorting large data sets effectively, both with respect to time and memory consumed. This paper is aimed at reviewing multiple adaptive sorting algorithms, on the basis of selection of an algorithm based on the characteristics of the data set. Machine Learning allows us to construct an adaptive algorithm based on the analysis of the experimental data. A review of algorithms designed using Systems of Algorithmic Algebra and Genetic Algorithms was performed. Both methods are designed to target different use cases. Systems of Algorithmic Algebra is a representation of pseudo code that can be converted to high level code using Integrated toolkit for Design and Synthesis of programs, while the Genetic Algorithm attempts to optimize its fitness function and generate the most successful algorithm.
References
- M.J. Quinn, “Parallel Programming in C with MPand OpenMP” Tata McGraw Hill Publications, 2003, p. 338.
- Guo, H.: “Algorithm selection for sorting and probabilistic inference: A machine learning-based approach”. Ph.D. dissertation, Kansas State University (2003)
- Ron Kohavi; Foster Provost (1998). "Glossary of terms". Machine Learning 271–274.
- C. M. Bishop (2006). Pattern Recognition and Machine Learning. Springer.ISBN 0-387-31073-8.
- Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press. ISBN 9780585030944.
- Doroshenko, A., Tseytlin, G., Yatsenko, O., Zachariya, L.: Intensional Aspects of Algebra of Algorithmics. Proceedings of International Workshop “Concurrency, Specification and Programming” (CS&P’2007), 27–29 September 2007, Lagow (Poland) (2007).
- Li, Xiaoming, Maria Jesus Garzaran, and David Padua. “Optimizing Sorting With Machine Learning Algorithms.” 2007 IEEE International Parallel and Distributed Processing Symposium (2007): n. pag. Web.
- Whitley, Darrell (1994). "A genetic algorithm tutorial". Statistics and Computing 4 (2): 65–85. doi:10.1007/BF00175354.
- "The Analysis of Heapsort". Journal of Algorithms 15: 76–100.doi:10.1006/jagm.1993.1031.
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0.
- Olena Yatsenko. (2011). On Application of Machine Learning for Development of Adaptive Sorting Programs in Algebra of Algorithms, Concurrency, Specification and Programming, September 28-30, Pułtusk, Poland, pp. 577-588.
- Majumdar, Somshubra, Ishaan Jain, and Aruna Gawade. "Parallel Quick Sort Using Thread Pool Pattern." International Journal of Computer Applications IJCA 136.7 (2016): 36-41. Print
- R. Sedgewick. Implementing Quicksort Programs. Communications of the ACM, 21(10):847–857, October 1978.
Index Terms
Keywords