Application Of Sorting

Applications

There are many types of application in Computer sciences and also in our real life. Some of this application is given below.

Application in CS:-

Sorting algorithms and priority queues are widely used in a broad variety of applications. Our purpose in this section is to briefly survey some of these applications. Our implementations sort arrays of Comparable objects. This Java convention allows us to use Java's call back mechanism to sort arrays of objects of any type that implements the Comparable interface.

• Transaction example. Program Transaction.java implements the Comparable interface for a transaction data type based on when the transaction occurred.
• Pointer sorting. The approach we are using is known in the classical literature as pointer sorting, so called because we process references to keys and do not move the data itself.
• Keys are immutable. It stands to reason that an array might not remain sorted if a client is allowed to change the values of keys after the sort. In Java, it is wise to ensure that key values do not change by using immutable keys.
• Exchanges are inexpensive. Another advantage of using references is that we avoid the cost of moving full items. The reference approach makes the cost of an exchange roughly equal to the cost of a compare for general situations.
• Priority queues with comparators. The same flexibility to use comparators is also useful for priority queues. MaxPQ.java and MinPQ.java include a constructor that takes a Comparator as an argument.
• Search for information. Keeping data in sorted order makes it possible to efficiently search through it using the classic binary search algorithm.
• Combinatorial search. A classic paradigm in artificial intelligence is to define a set of configurations with well-defined moves from one configuration to the next and a priority associated with each move. Also defined is a start configuration and a goal configuration (which corresponds to having solved the problem. The A* algorithm is a problem-solving process where we put the start configuration on the priority queue, then do the following until reaching the goal: remove the highest-priority configuration and add to the queue all configurations that can be reached from that with one move (excluding the one just removed).
• Prim's algorithm and Dijkstra's algorithm are classical algorithms that process graphs. Priority queues play a fundamental role in organizing graph searches, enabling efficient algorithms.
• Kruskal's algorithm is another classic algorithm for graphs whose edges have weights that depends upon processing the edges in order of their weight. Its running time is dominated by the cost of the sort.
• Huffman compression is a classic data compression algorithm that depends upon processing a set of items with integer weights by combining the two smallest to produce a new one whose weight is the sum of its two constituents. Implementing this operation is immediate, using a priority queue.
• String processing algorithms are often based on sorting. For example, we will discuss algorithms for finding the longest common prefix among a set of strings and the longest repeated substring in a given string that are based on first sorting suffixes the strings.

Real life Applications:-

• These are some of the applications in real-world instruction scheduling, ordering of formula cell evaluation when recomposing formula values in spread sheets, logic synthesis, determining the order of compilation tasks to perform in make files, data serialization, and resolving symbol dependencies in linkers. It is also used to decide in which order to load tables with foreign keys in databases.
• In spring applicationContext.xml, the bean creation order is determined from the topological sorted order.