IJCSI International Journal of Computer Science Issues, Vol. 4, No. 2, 2009
30
size of the list is doubled, the amount of time needed is
increased by a factor of four. The folklore deduced is
“Algorithms like Selection sort are quadratic in
nature.”
6. Conclusion
In this paper we have shown that the research on sorting
algorithm has produced abundant results and can be
thought as Folklore knowledge - momentarily belief
among people. We proved that these results are not
absolute as they are specific to some factors like person
working, configuration of hardware, programming styles,
whether parallelism is opted or not? Etc. Even with these
uncertainties, we have analyzed sorting algorithms and
presented strong evidence to the effect that a particular
folk can be converged in to theorem and vice versa so as
to show that folklore and converged theorems are
interchangeable.
References
[1] Oxford Dictionary
[2]Horowitz, E.,Sahni. S, Fundamentals of Computer
Algorithms, Computer Science Press, Rockville. Md.
[3] Dr. D. E. Knuth, The Art of Computer Programming, 3rd
volume, "Sorting and Searching”, second edition.
[4] Liu C. L., “Analysis of sorting algorithms”, Proceedings of
Switching and Automata Theory, 12th Annual
Symposium, 1971, East Lansing, MI, USA, pp 207-215.
[5] Darlington. J, A synthesis of several sorting algorithms, Acta
Inf. II, 1978, pp 1-30.
[6] John Darlington, Remarks on “A Synthesis of Several Sorting
Algorithms”, Springer Berlin / Heidelberg, pp 225-227,
Volume 13, Number 3 / March, 1980.
[7] Talk presented by Dr. Sedgewick ,” Open problems in the
analysis of sorting and searching algorithms”, at the
Workshop on the probabilistic analysis of algorithms,
Princeton, May, 1997.
[8] A. Andersson & T. Hagerup, S. Nilsson, and R. Raman,
“Sorting In Linear Time?” Proceedings of the 27th Annual
ACM Symposium on the Theory of Computing, 1995.
[9] Parag Bhalchandra, “Proliferation of Analysis of
Algorithms with application to Sorting Algorithms”,
M.Phil Dissertation, VMRF, India, July 2009
[10] Paul Vitanyi , “Analysis of Sorting Algorithms by
Kolmogorov Complexity (A Survey) “, appeared in
Entropy, Search, Complexity, Bolyai Society
Mathematical Studies, pp 209—232 , Springer-Verlag,
2007
[11] Richard Harter, Inefficient sort algorithms - “A Computer
Environment for Beginners' Learning of Sorting Algorithms:
Design and Pilot Evaluation”, ERIC, Journal Number
795978, Computers & Education, v51 n2, pp708-723, Sep
2008
[12] S Nilsson, “the Fastest Sorting Algorithm?” Doctor Dobbs
Journal, 2000.
Dr. S. D. Khamitkar, M.Sc. PhD
He is Associate Professor and has more than 14 years of teaching
and research experience. He has published near abut 6+ papers in
international journals. He is research guide and currently ten
students are working with him His interest area includes Network
Security, Scientific computing, etc. He is life member of Indian
Science Congress Association, ISTE.
Parag Bhalchandra, Sakharam Lokhande, Nilesh Deshmukh,
M.Sc., SET-NET, M.Phil
All of them are Assistant Professors and have registered for PhD
research work. They have 8+ years teaching experience and have
2+ papers in international conferences. They are life members of
ISCA, ISTE. Their interest lies in Algorithm Analysis, soft
computing and web based developments.
IJCSI