Views 
   PDF Download PDF Downloads: 1526

 Open Access -   Download full article: 

Root to Fruit (2): An Evolutionary Approach for Sorting Algorithms 

Pramod Kadam1, Sachin Kadam

BVDU, IMED, Pune (India)     

Article Publishing History
Article Received on :
Article Accepted on :
Article Published : 26 Dec 2014
Article Metrics
ABSTRACT:

This paper continues the earlier thought of evolutionary study of sorting problem and sorting algorithms (Root to Fruit (1): An Evolutionary Study of Sorting Problem) [1]and concluded with the chronological list of early pioneers of sorting problem or algorithms. Latter in the study graphical method has been used to present an evolution of sorting problem and sorting algorithm on the time line.

KEYWORDS: Evolutionary study of sorting; History of sorting Early Sorting algorithms; list of inventors for sorting

Copy the following to cite this article:

Kadam P, Kadam S. Root to Fruit (2): An Evolutionary Approach for Sorting Algorithms. Orient.J. Comp. Sci. and Technol;7(3)


Copy the following to cite this URL:

Kadam P, Kadam S. Root to Fruit (2): An Evolutionary Approach for Sorting Algorithms. Available from: http://www.computerscijournal.org/?p=1510


Introduction

In spite of plentiful literature and research in sorting algorithmic domain there is mess found in documentation as far as credential concern [2]. Perhaps this problem found due to lack of coordination and unavailability of common platform or knowledge base in the same domain. Evolutionary study of sorting algorithm or sorting problem is foundation of futuristic knowledge base for sorting problem domain [1]. Since sorting activity is known as pre-requisition or supportive activity (searching, Matching etc.) for the various other computer related activities [3]. This activity (sorting) has a distinct place in the computing and programming domain.

It could possible and quit obvious that some of the important contributors or pioneers name and their contribution may skipped from the study. Therefore readers have all the rights to extent this study with the valid proofs. Ultimately our objective behind this research is very much clear, that to provide strength to the evolutionary study of sorting algorithms and shift towards a good knowledge base to preserve work of our forebear for upcoming generation. Otherwise coming generation could receive hardly information about sorting problems and syllabi may restrict with some major/fundamental algorithms only [4]. Evolutionary approach of sorting can make learning process alive and gives one more dimension to student for thinking [4]. Whereas, this thinking become a mark of respect to all our ancestors[5].

Origin of sorting problem

The sorting problem asks us to rearrange the items of the given list in the proper order [6] to other side according to mathematician, for sorting there should be exist of the relationship of the total then only sorting is possible .Computing domain basically invented to deal  with data or information storing where need of the sorting is like anything for the organizing and managing data .Sorting activity plays vital role in computing context  it makes many questions about the easier to answers [6].

In this domain, voluminous material is available however still sorting is called as unsolved problem [7], which leads the evolutionary study of sorting. While looking back in the history of sorting there were absence of evidences which can tell us about exact nativity of sorting problem or sorting algorithm.

However, in the computing context from the dawn of the computer and computing programming there is involvement of the sorting has been found. First program on the sorting problem was recorded in 1945 by John Van neuman and it was histories first sorting algorithm and it was Merge sort[3]. Even before merge sort in 1880, Holirith sorting machine sorting problem was solved by using radix sort  therefore in the timeline study of sorting algorithms radix sort comes first[3]

Origin of sorting algorithms

The story of sorting algorithms starts from the radix sort .Sorting algorithm is the ultimate solution of the sorting problem. search of sorting algorithm or sorting techniques takes us back in the era when development of electronics were in the phase of paradigm shift in data storage and that to ample data comes in the mess due to heavy volume, found  efficient technique for handle this data, result in to sorting and searching problem. Further more in this context of the sorting problem a strong evidences found in the mid of ninetieth century .whereas in 1880 for the processing of the large census data of United state, a machine invented by Herman Hollerith, He was an American statistician did work with census department of United state and 100 of his invented machines were used to process on the 1890 census. Hollerith machine includes punch, tabulator and sorters .this machine based on the radix sort and A key idea was that data could be encoded by the locations of holes in a card. Hollerith determined that data punched in specified locations on a card, in the now-familiar rows and columns, could be counted or sorted mechanically [3].

Contribution of Donald Knuth ,Robert Fiendler,L.j.Comrie’s  and NIST website in the Computing history and sorting context is really unbeatable .Their Pedagogy, used literature and comments helps us a lot while digging the roots of the sorting algorithms.

In 1938, The idea of merging sort invented by Jame W.Bryce. A machine known as collator use to merge cards from two different stations in the one sorting operation[3, 8].

Mean time computer were arrived in picture and designer and programmers of computing machines feel the need of powerful search method and sorting was intimately involved in this development .The first sorting technique was used in “EDVAC” Computer and credit of this invention goes to John Von Neuman

Germany 1945: Scientist K Zuse works independently for the computer z4 which was used for the commercial purpose .He constructed a program s seems Insertion sort.Z4 is also known as world’s first commercial computer.

To -other side a word “Algorithm” joined with the sorting technique after the mid of nineteenth. Even history of the word algorithm is equally interesting. A word algorithm first time traced  in 9th century. This terminology invented by Muhammad Bin Musa al-Khwarizmi (Persian scientist and mathematician)[9]

Primary concern for sorting algorithms

By now plenty number of the sorting algorithms and their variants makes domain become rich some of them are better than other .However there is absence of the generalized sorting algorithm which can suits best in the entire or all available situation.[6]

Below is the list of inventors of sorting and their sorting invention along with invention year (Chronological order)

Table 1

Table 1 



Click here to View table

 

Evolutionary graphs 

Figure 1: Evolutionary Graph for Sorting Algorithms

Figure1: Evolutionary Graph for Sorting Algorithms



Click here to View figure

 

Figure 2:  Sorting Algorithms (1880-1962)

Figure2:  Sorting Algorithms (1880-1962)

 

 
Click here to View figure

 

Figure 3: Sorting Algorithms (1962-1994)

Figure3: Sorting Algorithms (1962-1994)

 

Click here to View figure

 

Figure 4:Sorting Algorithms (1996-2013)

Figure4: Sorting Algorithms (1996-2013)

 


Click here to View figure

 

Conclusion

Most of the sorting algorithms were invented in the period of 1954 to 1985 and radix sort is first sorting algorithm which was used commercially in 1980 census machine which was invented by Herman Hollirith . Whereas, the search of efficient sorting algorithm is alive so far. There is voluminous sorting algorithms are available but generalization of sorting algorithm is not possible; Due to, distinct nature of individual sorting problems. To store, manage and update this ample information about sorting algorithms there is need of knowledge base.

References

  1. KADAM, P.K.a.S., Root to Fruit (1): An Evolutionary Study of Sorting Problem. ORIENTAL JOURNAL OF COMPUTER SCIENCE & TECHNOLOGY, April 2014. 7(1): p. 111-116.
  2. Astrachan, O., Bubble Sort: An Archaeological Algorithmic Analysis. 2003.
  3. E.Knuth, D., The art of Computer programming Vol.3 Sorting and Searching 2ed. The art of computer programming. Vol. 3. 2006, New Delhi: Pearson Education 780.
  4. Impagliazzo, J., Using History in Computing Courses, in 35th ASEE/IEEE Frontiers in Education Conference. 2005, IEEE: Indianapolis, IN.
  5. LEE, J.A.N., Those Who Forget The Lessons of History, or Why I Study the History of Computing. IEEEAnnals ojthe History of Computing, 1996. 18(2): p. 9.
  6. Levintin, A., Introduction to Design and analysis of Algorithms. Second Edition ed. 2013, New Delhi: Pearson.
  7. R.G.Dromy, How to solve it by computer. 8 ed. 2009, New Delhi: Pearson Education. 442.
  8. H.Lorin, A guided bibliography to sorting. IBM Sys J, 1971. 3: p. 11.
  9. Wikipedia.2014
  10. SEWARD, H.H., INFORMATION SORTING IN THE APPLICATION OF ELECTRONIC DIGITAL COMPUTERS TO BUSINESS OPERATIONS, in DIGITAL COMPUTER LABORATORY  1954, MASSACHUSETTS INSTITUTE OF TECHNOLOGYCambridge 39,: Massachusetts. p. 68.
  11. T.Heineman, G., Sorting Algorithms, in Algorithms in a Nutshell. 2007, O Reilly.
  12. C.Singleton, R., ALGORITHM 347:AN EFFICIENT ALGORITHM FOR SORTING WITH MINIMAL STORAGE [M1]. Communication of the ACM, March ,1969. 12(3): p. 3.
  13. Hermann Gruber, M.H.a.O.R., Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms.
  14. Knuth, D.E., The art of computer programming:Fundamental Algorithms. Third Edition ed. Vol. 1. 2002, New Delhi: Pearson Education.
  15. Peter M. McIlroy , K.B., M. Douglas McIlroy, Engineering Radix Sort. Computer Science Research Group,University of California at Berkeley and AT&T Bell Laboratories: p. 15.
  16. Khreisat, L., QuickSort A Historical Perspective and Empirical Study. IJCSNS International Journal of Computer Science and Network Security, Dec.2007. 7(12): p. 12.
  17. Nilson, A.A.a.S. A new efficient Radix sort. in 35th ANNUAL IEEE SYMPOSIUM ON FOUNDATION OF COMPUTER SCINCE. 1994. Sweden.
  18. C.Carter, B.K.B.a.W., New Merge Sorting Techniques. 14th national meeting for ACM, 1959: p. 4.
  19. Goodrich, M.T., Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm. ACM, 2011. 58(6): p. 26.
  20. R.L.Gilstad, POLYPHASE MERGE SORTING — AN ADVANCED TECHNIQUE. Computer History Museum (www.computerhistory.org), NA: p. 6.
  21. Hoare, C.A.R., Algorithm 64:Quicksort. Communication of the ACM, 1961: p. 2.
  22. B.G.T.Lowden, Discussion and correspondence a note on the oscillating sort. The computer Journal. 20(1): p. 5.
  23. Lankham, A.B.a.I., Restricted Patience Sorting and Barred Pattern Avoidance. Formal Power Series and Algebraic Combinatorics S´eries Formelles et Combinatoire Alg´ebrique San Diego, California, 2006: p. 12.
  24. Mishra, A.D., Selection of Best Sorting Algorithm for a Particular Problem, in Computer science and Engineering Department. June 2009, Thapar University: Patiala. p. 60.
  25. Pieterse, P.E.B.a.V. Dictionary of algorithms and data structures. 2014  [cited 2014 15 dec 2014]; Available from: http://www.nist.gov/dads/HTML/sort.html.
  26. Hoare, C.A.R., Proof of a program:Find. Communication of the ACM, 1971. 14(1): p. 7.
    CrossRef
  27. Tim Bell, B.A., Sorting Algorithms as Special Cases of a Priority Queue Sort, in SIGCSE11. 2011, ACM: Dallas, Texas, USA. p. 6.
  28. Wang, Y., A New Sort Algorithm: Self-Indexed Sort, in comunication with ACM. March 1996, Communications of ACM SIGPALN. p. 9.
  29. peters, T., Tim sorting. 2002.
  30. Joshua J. Arulanandham, C.S.C., Michael J. Dinneen, Bead–Sort: A Natural Sorting Algorithm. In The Bulletin of the European Association for Theoretical Computer Science 76, 2002: p. 10.
  31. Steffen Heinz, J.Z.H.E.W., Burst Tries: A Fast, Effcient Data Structure for String Keys. ACM: p. 31.
  32. Mansi, J.A.a.R., An Enhancement of Major Sorting Algorithms. The International Arab Journal of Information Technology, 2010. 7(1): p. 8.
  33. B.K.Haddon, Cycle sort:A linear sorting method. The computer Journal, 1990. 33(4): p. 3.
  34. Upendra Singh Aswal, K.C.P., SUJATA NEGI THAKUR, A NEW SORTING ALGORITHM(NAMED ‘U’ SORT). International Journal of Engineering Science and Technology (IJEST) Sept 2011. 3(9): p. 5.
  35. NitinArora, V. Kumar, and S. Kumar, A Novel Sorting Algorithm and Comparison with Bubble sort and Insertion sort. International Journal of Computer Applications, May 2012. 45(1): p. 2.
  36. R.Srinivas and A.R. Deepthi, Novel Sorting Algorithm. International Journal on Computer Science and Engineering (IJCSE), Jan 2013. 5(1): p. 4.

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