ABSTRACT
The .NET Framework Class Library provides several classes, called collections, that are used to store groups of related objects. Along with methods for organizing, storing and retrieving data, these classes also provide methods for sorting and searching that require no additional programming and thus can substantially reduce application development time. For example, the List<T> class is a generic class found in the System.Collections.Generic namespace and the ArrayList class is found in the System.Collections namespace. Both of these classes have properties that are very similar to C# arrays and, in addition, also come with their own methods for performing efficient sorting and searching. However, one key advantage of using collection classes over conventional arrays is that collections can dynamically grow and shrink as their number of elements change. Arrays, on the other hand, do not automatically adjust their size at runtime to accommodate changes in their initial number of alloted elements unless the programmer manually codes in a new array or uses the array class’s Resize method. With all these tools at our disposal, one may very well question the wisdom of going through the effort of discussing the various different types of sorting and searching algorithms. First, instead of just randomly choosing any sorting or searching algorithm, it is important to have a basic general understanding of how all these different algorithms actually work in order to make a good decision about which algorithm to use in a particular application. After all, there is no known ideal algorithm for either sorting or searching that meets all the requirements for optimal speed and efficiency. As the size and type of input data changes, different sorting and searching algorithms offer different degrees of strengths and weaknesses. Furthermore, certain applications may require some type of sorting and/or searching as part of their internal structure. As a result, at some point programmers may be required to write their own custom set of sorting and/or searching routines instead of simply relying on an unfamiliar canned version of one or more of these algorithms. Finally, because of their importance, sorting and searching algorithms are also an integral part of the standard curriculum for both elementary and advanced computer
5.2 Sorting Algorithms A sorting algorithm is essentially a recipe containing detailed computer code instructions for organizing the elements of a list into a well-defined numerical or alphabetical order. A list is an abstract concept consisting of a finite collection of fixed-length entities that can be arranged either in random order or in an increasing or decreasing sequential order. In practice, a list is usually expressed in the form of an array or a more advanced data structure such as a linked list. Sorting is often used in conjunction with the processing of either experimentally measured or computer generated data. In addition, sorting is sometimes used by other algorithms, such as search and merge algorithms, whose own optimization require sorted lists to work correctly and efficiently. Because of its frequent use in a wide range of engineering, mathematical and scientific applications, sorting has attracted a lot of research interest going as far back as to the earliest days of computing. Sorting often involves large volumes of data and so research into this topic has primarily focused on developing increasingly fast and efficient algorithms that strive to minimize both the computer processing time involved and the amount of computer memory needed. Although many consider sorting to be a solved problem, new interesting and useful sorting algorithms are still being invented [29, 30] and so it is still very much a vibrant evolving subject matter that is worth covering.
