Root to Fruit (1): An Evolutionary Study of Sorting Problem

Pramod Kadam, Sachin Kadam

1Bharati Vidyapeeth University, Institute of Management and Entrepreneurship Development, More Vidyalaya Campus, Puad Road, Pune 

2BVDU, IMED, Pune

ABSTRACT:

This paper provides initial thought for why should do evolutionary study in computer science (in general) and in sorting algorithmic domain (in particular)?Primaryevaluation ofevolutionary study of sorting algorithms and list of literatures which can help during this evolutionary study of sorting algorithms.

KEYWORDS: Evolutionary study; Sorting algorithms; History of sorting algorithm; Literature of sorting algorithms

Copy the following to cite this article: Kadam P, Kadam S. Root to Fruit (1): An Evolutionary Study of Sorting Problem. Orient. J. Comp. Sci. and Technol;7(1)

Copy the following to cite this URL: Kadam P, Kadam S. Root to Fruit (1): An Evolutionary Study of Sorting Problem. Orient. J. Comp. Sci. and Technol;7(1). Available from: http://computerscijournal.org/?p=739

Why should do evolutionary study?

Computer science is the science of people ideology. Invention of computers has changed the life of human being alike the invention of wheel. The birth, evolution and development of computer science theories condense the scientists’ method of thinking and research, which is more valuable than the any specific knowledge. Indeed, Philosopher George Santanya stated that “Those who cannot remember the past are condemned to repeat it” .following are some reasons for why should do evolutionary study

Computer industry is immense to starve these needs along with contemporary technologies, its essential to understand trend of future

• Evolutionary study allows us to recognize trend of future
• Evolutionary study can help to discover parallel technology and analogies to modern
• It helps  for  developing standards to judge viability and potential for current  technology
• It preserves the achievements of the our forebears [1]
• Evolutionary study gives opportunity to study effects ofone invention in the various fields [2]
• Evolutionary study  adds a sociological dimension to the subject and has the potential of engaging students attention
• Evolutionary study makes learning process alive so that it is said to be efficient pedagogical tool[2]
• Evolutionary study encourages students to  think beyond the immediate technical topic and machines
• Scientist of  the old generation worked hard to archive success .Evolutionary study give justice to all their efforts and salute to their hard work

Why should  choose Sorting Algorithms for Evolutionary study

Sorting is identified as vital activity from computer context. Which can demonstrate a great diversity of algorithms and programming” [3] (p.n.56). It is estimated that most of the time of computer is spent to sort alone [4]p.n. 3” [5]Page No.181.Sorting has traditionally been used mostly for business data processing [6, 7.Whereas Efficient Sorting is the one of  the unsolved problem so far and from the dawn of computing  it has attracted a great attention of researchers{E.Knuth, 2006 #9]. There is no any method is available in this context which is best in all the situation .i.e. Sorting methods are varies according  to the nature of problem and situation[8].To the other hand Many more sorting algorithms are available in this domain and chunk of researchers considered sorting as a solved problem[9]. While explaining sorting problem, Yingxu Wang stated that “it is such a challenging problem …..Where always scope of improvement…” [10].Even on this significant activity of computer, each researcher has their own opinion.

Need of Evolutionary Study in  Sorting Algorithmic domain

It is found by the history of sorting algorithms; most of the sorting algorithms are either invented in between 1950-1980 or late in 1990.These all algorithms has some relation with each other and due to the necessity of situation they came in existence [11].However, if there is change in situation, automatically it affects the nature of sorting algorithm i.e. There is no one sorting method is available which fits best for every situation [8]. On the other side sorting algorithmic domain is unknown about how many sorting algorithms are in existence in this domain? Owen Astrachan in his introductory note said “What do students remember from their first programming courses after one, five, and ten years? Most students will take only a few memories of what they have studied. As teachers of these students we should ensure that what they remember will serve them well. More specifically, if students take only a few memories about sorting from a first course what do we want these memories to be?……”[12]

Information which we have in this domain is inadequate .Perhaps , somewhere the historical information available today is  insufficient about sorting algorithms and related problems were present in the history.

John Backus, in his acceptance speech on receiving the 1994 Charles Stark Draper Award, said “ In science and all creative work we fail-again and again. For each successful idea, we usually have dozens of others that don’t work, no matter how hard we straggle. But in failing we learn a lot…” [1].

An evolutionary study of sorting algorithms is a study of our success as well as study of failure too. and we shy away from learning about the failures[1]and “Learning from our mistakes can lead to subsequent success” ;( p.n.7) [2] An evolutionary study is a well established term, and this type of study is already in exist but in other domain expect than the sorting algorithmic domain

Table no.1   Evolutionary study in other domain Click here to View table

 

Importance of evolutionary study for sorting algorithms

1. In the field software development
2. In the field of research and development
3. In the field of Academia

An Evolutionary Evaluation of sorting algorithms

5.1  Evolution of sorting algorithms

Sorting Problem and its origin

The problem of sorting can be perceived from two perspectives:

• grouping similar items (e.g. sorting laundry into piles of shirts and pants)
• ordering items according to some rules (e.g. organizing names alphabetically in a phone book)[7, 13]
• Sorting algorithms provide solution to sorting problems in computing domain. They arrange items in a set according to a predefined ordering relation. The two most common types of data involving sorting are string information and numerical information. The ordering relation for numeric data involves arranging items in sequence from smallest to largest (or vice versa) such that each item is less than or equal to its immediate successor. This ordering is referred to as ascending order. The greater than or equal to relation gives the descending order. Stored string information is generally arranged in standard lexicographical or dictionary order)[4, 7].

There are numerous algorithms available for sorting information. Sorting algorithms usually fall into one of two classes:

• Internal sorting: Internal sorting is the process which sorts the data which resides primary storage and  further divided in to two subtypes

o  Comparative Sorting: In which the ordering Keys of the elements rely on comparison magnitude.

o  Distributive Sorting algorithms: These algorithms, order the list by testing a key or a digit of a key against a standard and collecting all members of a group together.

Insertion sort, Selection sort, Quick sort, radix sort, shell sort etc. are built on the principle  of internal sorting[4]

• External sorting: If data is too large to be represent primary storages are then whole data divided in to the partitions externally, to make sort separately and finally all are merged together. These type of sorting algorithms are also further divided in to Comparative and distributive sorting algorithms[13]

Polyphase Merge sort, cascade merge sort, Oscillating sort, External radix sort etc. are some examples of external sorting [4].

 Primary concern and Years

Root of sorting algorithms and sorting machines take us back in 1880, when The United state’s 20 year old scientist Herman Hollerith invented ingenious tabulated machine to pursue Census of 1880.Population continued its inexorable growth and originally developed machine was not able to process for 1900 population so the new machine devised by Hollerith in 1900 to stave off the count of population .Hollerith machine was based on radix sorting which now used in digital computers.

Table 2: Sorting Activity in early days Click here to View table

 

Contribution of persons and organization

Roots of today’s failure and/or success always presents in the past. Evolutionary study always resist us from what not to do .i.e. Evolutionary study is the only way which can keeps you (study) on right path otherwise possibly, we might repeat same mistake [2].Todays rich set of sorting algorithms is the result of pioneers hard work and building on the success of others is useful in a modern age (result in save in time ,to avoid repetition ,same efforts one can put to inculcate something extra and innovative)[1].It  is found by this evolutionary study, there is injustice with either with concept or pioneers.

In 1945 K.Zuse(German Scientist) constructed a program for straight insertion sorting independently but unfortunately this work remained unpublished for next 30 years .[4]p.n.386.From the Evolutionary study of bubble sorting, it is learnt that it was Knuth comment due to which bubble sort lost his longevity. Sentiments for exclusion supported by knuth “In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.”[12]

5.2   Evolutionary literature on sorting algorithms

There is Extensive information is available in this domain. To maintain an evolutionary literature is not just a cognitive challenge but its management challenge {Ellis, 2006 #10}.Early history of sorting problem is present in the inaccessible reports and hardly people were involved with computer at that time so there is absence of well managed literature data [4]p.n.388.

Table3: Evolutionary literature on sorting algorithms Click here to View table

 

Readers can extend this list further

Conclusion

Sorting problem is known as unsolved problem so far whereas sorting plays vital role in computing science. In spite of rich literature and plentiful work;Current scientific understanding about the sorting or computing is incomplete {LEE, 1996 #36} .So there is require to do evolutionary study in this field.

Best efforts of scientist has been involved in the history of sorting out of some of them not received credential of their contribution perhaps lack of evolutionary study of sorting problem. Now it’s demand of time, to preserve work of our forebear otherwise coming generation could receive hardly information about sorting problems and algorithms. Evolutionary study of sorting algorithm are require for/because of

1. Evolutionary study of sorting can makes learning process alive
2. To gives justice to the all effort of our ancestors
3. To recognize future trend of sorting and its solution
4. To do help  for  developing standards of sorting algorithms to judge viability and potential for current  technology

References

1. 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.
2. Impagliazzo, J., Using History in Computing Courses, in 35th ASEE/IEEE Frontiers in Education Conference. 2005, IEEE: Indianapolis, IN.
3. Wirth, N., Algorithms+Data Structures=Programs. Eastern Economy Edition ed. Automatic computation. 2002, New Delhi: Prentice Hall.
4. 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.
5. R.G.Dromy, How to solve it by computer. 8 ed. 2009, New Delhi: Pearson Education. 442.
6. R. Angrish, D.G., Efficient String Sorting Algorithms: Cache-aware and Cache-Oblivious. International Journal of Soft Computing and Engineering (IJSCE), May 2011. 1(2): p. 5.
7. Levintin, A., Introduction to Design and analysis of Algorithms. Second Edition ed. 2013, New Delhi: Pearson.
8. Dwivedi, D.K., Comparison Analysis of Best Sorting Algorithms VSRD International Journal of CS & IT, 2011. 1(4): p. 7.
9. Mansi, J.A.a.R., An Enhancement of Major Sorting Algorithms. The International Arab Journal of Information Technology, 2010. 7(1): p. 8.
10. Wang, Y., A New Sort Algorithm: Self-Indexed Sort, in comunication with ACM. March 1996, Communications of ACM SIGPALN. p. 9.
11. Tim Bell, B.A., Sorting Algorithms as Special Cases of a Priority Queue Sort, in SIGCSE11. 2011, ACM: Dallas, Texas, USA. p. 6.
12. Astrachan, O., Bubble Sort: An Archaeological Algorithmic Analysis. 2003.
13. H.Lorin, A guided bibliography to sorting. IBM Sys J, 1971. 3: p. 11.

---

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