The Folklore of Sorting Algorithms



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



More intriguing information

1. Tourism in Rural Areas and Regional Development Planning
2. The name is absent
3. The name is absent
4. CONSIDERATIONS CONCERNING THE ROLE OF ACCOUNTING AS INFORMATIONAL SYSTEM AND ASSISTANCE OF DECISION
5. The name is absent
6. A Rational Analysis of Alternating Search and Reflection Strategies in Problem Solving
7. On the origin of the cumulative semantic inhibition effect
8. ISO 9000 -- A MARKETING TOOL FOR U.S. AGRIBUSINESS
9. The name is absent
10. The name is absent
11. Fiscal Insurance and Debt Management in OECD Economies
12. A Critical Examination of the Beliefs about Learning a Foreign Language at Primary School
13. The name is absent
14. The name is absent
15. The name is absent
16. Governance Control Mechanisms in Portuguese Agricultural Credit Cooperatives
17. Opciones de política económica en el Perú 2011-2015
18. The name is absent
19. Initial Public Offerings and Venture Capital in Germany
20. The name is absent