Computer Science
Sorting Algorithms
Sorting algorithms are a set of procedures used to arrange data in a specific order. They are used to sort data in ascending or descending order, and are essential in computer science for efficient data processing and retrieval. There are various types of sorting algorithms, including bubble sort, insertion sort, and quicksort.
Written by Perlego with AI-assistance
Related key terms
1 of 5
9 Key excerpts on "Sorting Algorithms"
eBook - PDF- Wallace Wang(Author)
- 2022(Publication Date)
- For Dummies(Publisher)
4 Algorithms Contents at a Glance CHAPTER 1: Sorting Algorithms 399 CHAPTER 2: Searching Algorithms 415 CHAPTER 3: String Searching 429 CHAPTER 4: Data Compression Algorithms 441 CHAPTER 5: Encryption Algorithms 451 CHAPTER 1 Sorting Algorithms 399 Sorting Algorithms E very program handles data (numeric or text). Besides saving data, most programs also need to organize that data in some way, which involves sorting that data in a specific order, such as alphabetically or numerically. A database needs to sort names alphabetically by last name or by sales region, whereas a video game needs to sort the top-ten highest scores. Despite the simple idea behind sorting a list of names or numbers, sorting is practically a field of computer science in itself. Computer scientists constantly study different ways to sort through data to find the fastest, most efficient method possible. Each of these different sorting methods is a sorting algorithm. Algorithm is a fancy term for a method of doing something, so a sorting algorithm is a specific method for telling the computer how to sort data. The reason computer scien- tists keep creating and studying Sorting Algorithms is because no single sorting algorithm is best for all purposes. Some Sorting Algorithms are easy to create but work slowly. Other sorting algo- rithms are much harder to create but work much faster. Ironically, some Sorting Algorithms work horribly when sorting a small number of items, such as a dozen numbers, but work quickly when sorting thousands of items. Chapter 1 IN THIS CHAPTER » Using bubble, selection, and insertion sorts » Using shell, heap, merge, and quick sorts » Comparing different Sorting Algorithms 400 BOOK 4 Algorithms Four factors for considering Sorting Algorithms include » Ease of implementation: Defines how complicated the sorting algorithm is to implement in any programming language. Some Sorting Algorithms are easy to write but slow in actual use.
eBook - PDFAlgorithms and Theory of Computation Handbook, Volume 1
General Concepts and Techniques
- Mikhail J. Atallah, Marina Blanton(Authors)
- 2009(Publication Date)
- Chapman and Hall/CRC(Publisher)
3 Sorting and Order Statistics Vladimir Estivill-Castro Griffith University 3.1 Introduction ..................................................... 3 -1 3.2 Underlying Principles ......................................... 3 -3 3.3 State-of-the-Art and Best Practices ......................... 3 -6 Comparison-Based Internal Sorting • Restricted Universe Sorts • Order Statistics • External Sorting 3.4 Research Issues and Summary ............................... 3 -23 3.5 Further Information ........................................... 3 -25 Defining Terms ......................................................... 3 -26 References ................................................................ 3 -26 3.1 Introduction Sorting is the computational process of rearranging a given sequence of items from some total order into ascending or descending order. Because sorting is a task in the very core of Computer Science, efficient algorithms were developed early. The first practical and industrial application of computers had many uses for sorting. It is still a very frequently occurring problem, often appearing as a preliminary step to some other computational task. A related application to sorting is computing order statistics, for example, finding the median, the smallest or the largest of a set of items. Although finding order statistics is immediate, once the items are sorted, sorting can be avoided and faster algorithms have been designed for the k th largest element, the most practical of which is derived from the structure of a sorting method. Repeated queries for order statistics may be better served by sorting and using an efficient data structure that implements the abstract data type dictionary, with the ranking as the key. Sorting usually involves data consisting of records in one or several files. One or several fields of the records are used as the criteria for sorting (often a small part of the record) and are called the keys.
eBook - PDF- Rex Porbasas Flejoles(Author)
- 2019(Publication Date)
- Arcler Press(Publisher)
For instance, suppose that we want to sort a sequence of numbers into an increasing order. This problem arises quite often in practice and makes available a fertile ground for presenting numerous standard design practices as well as analysis tools (Adel’son-Vel’skii & Landis, 1962; Abramowitz & Stegun, 1965). Given below is the way we formally define any sorting problem (Figure 1.1): Input: An arrangement of n numbers (a 1 , a 2 , …, a n ). Output: A rearrangement (permutation) ' ' ' 1 2 , ,..., n a a a < > of the input se-quence in such a manner that ' ' ' 1 2 n a a a ≤ ≤ ≤ . As an example, consider an input sequence (30, 35, 59, 26, 35, 57). The output obtained from a sorting algorithm will return (26, 30, 35, 35, 57, 59) sequence. This type of input sequence is known as an instance of the sorting problem. Generally, an instance of a problem contains an input (satisfying whatsoever constraints are enforced in the problem statement), which is required to compute a solution of the encountered problem (Aho & Hopcroft, 1974; Aho et al., 1983). Sorting is regarded as a fundamental step in computer science as numerous programs makes it useful as an intermediate step. Resultantly, we have a large number of excellent Sorting Algorithms at our disposal (Ahuja & Orlin, 1989; Ahuja et al., 1990; 1993). The choice of a best algorithm for any given application depends mainly on several factors such as the number of items which need to be sorted, the degree to which the items have already been slightly sorted, the architecture of the computer, potential limitations on the item values, as well as the type of storage devices to be employed: main memory, tapes or disks. Fundamentals of Algorithms 3 An algorithm is considered as correct given that it halts with the correct out-put for each of the input instance. We say that an algorithm which is correct solves the specified computational problem .
eBook - PDF- Anil Kumar Yadav, Vinod Kumar Yadav(Authors)
- 2019(Publication Date)
- Arcler Press(Publisher)
Secondly, the main memory is a volatile device so it will lose the data when the power is shut down. To overcome these problems the data is sorted on the secondary storage devices. The internal sorting can be performed on a small amount of data. The technique which is used to sort the data that resides in secondary storage (auxiliary storage) devices; this sorting method are called external sorting. This sorting can be performed on a large amount of data. 9.3. BASIC TERMS OF SORTING Order: The sorting is a technique in which we expect the list of data to be arranged as we expect. Sorting order is nothing but the arrangement of the data in some specific style. Generally sorting order is of two types: 1. Descending Order: it is the sorting order in which the data or elements are arranged in form of greater to a smaller value. In other words, elements are in decreasing order. Example: 115, 315, 415, 215, 515, 110 Sorting 247 Above example is arranged in descending order after applying some sorting methods 515, 415, 315, 215, 115, 110 2. Ascending Order: It is the sorting order in which the data or elements are arranged in form of smaller to a greater value. In other words, elements are in increasing order. Example: 115, 315, 415, 215, 515, 110 Above example is arranged in ascending order after applying some sort-ing methods 110, 115, 215, 315, 415, 515 Efficiency : In sorting technique one of the most important issues analyses the efficiency of the sorting algorithm. We generally denote the efficiency of sorting algorithm in terms of time complexity. The time complexities are given in terms of big-O notations. Generally, time complexities for various Sorting Algorithms are O(n 2 ) and O(nlogn). The sorting techniques such as bubble sort, insertion sort, selection sort, shell sort has the time complexity O(n 2 ) and the sorting techniques such as merge sort, quick sort, heap sort has time complexities as O(nlogn).
eBook - PDFLimits of Computation
An Introduction to the Undecidable and the Intractable
- Edna E. Reiter, Clayton Matthew Johnson(Authors)
- 2012(Publication Date)
- Chapman and Hall/CRC(Publisher)
See the Exercises. This relationship between search (find smallest/largest n such that …) and decision (does n satisfy…?) holds for many problems. But neither the search nor the decision problem has an easy transformation to find what-ever makes the question into a yes instance—in this case, the actual short-est TSP path through the graph. 3.4 ALGORITHMS: A FIRST LOOK One of the main goals of computer science theory is the statement of a good definition of an algorithm. Almost any computer scientist has an intuitive feel for what is meant by the word algorithm , but formalizing the definition is not easy. None of the definitions below are really adequate, but they will be good enough for a discussion of the number of steps in a computational process. Trial Definition I An algorithm is a solution to a computational problem. Thus, BubbleSort, HeapSort, MergeSort, and so on, are all solutions to the Sorting Problem. 40 ◾ Limits of Computation Each of these is a finite sequence of steps that provides a solution to every instance of the computational problem, that is, it is a mapping from the set of all inputs to the set of correct solutions (outputs). The above definition is quite helpful: it tells us what an algorithm is in functional terms. It does not, however, tell us how we arrive at this mapping between input and output. As programmers, we realize that there are many issues surrounding the design, implementation, and execution of a computer algorithm. What logic do we use? What data structures do we need? How do we show that our algorithm is working correctly? There is clearly more attached to the notion of algorithm than this abstract statement. The word algorithm itself is fairly recent in the English language; older dictionaries do not contain it, though they do contain the related word algorism .
eBook - PDF- Sourabh Pal(Author)
- 2023(Publication Date)
- Arcler Press(Publisher)
This issue occurred often in practice, providing fertile ground for the presentation of a wide range of conventional design approaches and analytical tools (Hall et al., 1962; Abramowitz and Stegun, 1965). The following is how we formalize any ordering problem: • Input: A sequence of numbers (a 1 , a 2 , …, a n ). • Output: A permutation (rearrangement) ü 1 2 , ,..., n ± < > of the input arrangement in a way that ü 1 2 . n ± ≤ ≤ ≤ Consider the following input arrangement as an instance (30, 35, 59, 26, 35, 57). The (26, 30, 35, 35, 57, 59) sequence would be returned as the result of a sorting algorithm. An example of the sorting problem is this kind of input arrangement. Generally, a problem example has an input (that satisfies any restrictions imposed by the statement of the problem) that is necessary to compute a solution to the encountered problem. Sorting is considered a basic step in computer science since it is helpful as an intermediary step in many applications. As a result, we now have access to a huge variety of effective Sorting Algorithms (Ahuja and Orlin, 1989; Ahuja et al., 1989). The best algorithm for any specific application is determined by various factors, including the different items to be organized, the degree whereby the items are slightly organized, the computer architecture, potential item value limitations, and the kind of storage devices to be utilized: disks, main memory, or tapes. When an algorithm halts with the appropriate output for each input example, it is thought to be appropriate. A proper algorithm solves the stated computing issue. An erroneous algorithm, on either side, cannot halt at all on certain input examples, or it can halt with an inaccurate response (Ahuja et al., 1989; Courcoubetis et al., 1992). In contrast to our assumptions, erroneous algorithms may occasionally be advantageous if the rate of mistake may be
- Akhilesh Kumar Srivastava(Author)
- 2019(Publication Date)
- Arcler Press(Publisher)
Sorting Algorithms 6 CONTENTS 6.1. Bubble Sort ....................................................................................... 58 6.2. Insertion Sort .................................................................................... 60 6.3. Selection Sort .................................................................................... 64 6.4. Quick Sort ........................................................................................ 67 6.5. Merge Sort ........................................................................................ 74 6.6. Set Operations Using Array ............................................................... 80 6.7. Counting Sort .................................................................................... 91 6.8. Radix Sort ......................................................................................... 94 Exercises .................................................................................................. 95 A Practical Approach to Data Structure and Algorithm with Programming in C 58 Sorting is a method of arranging the elements in the desired sequence. This sequence is expected to be either ascending or descending. In the current chapter, elements are organized in ascending sequence. 6.1. BUBBLE SORT If some detergent is mixed in the bucket of water, the bubbles are created. Larger volume bubble has the tendency of reaching on the surface faster than smaller volume bubbles. In Bubble Sort Algorithm largest element is fixed in the first iteration, followed by the second largest element and so on so forth. In the process, the 1 st element is compared with 2 nd , and if the previous element is larger than the next one, elements are exchanged with each other. Then 2 nd and 3 rd elements are compared, and if second is larger than the 3 rd , they are exchanged.
eBook - PDF- Cay S. Horstmann, Rance D. Necaise(Authors)
- 2020(Publication Date)
- Wiley(Publisher)
525 C H A P T E R 12 SORTING AND SEARCHING C H A P T E R G O A L S To study several sorting and searching algorithms To appreciate that algorithms for the same task can differ widely in performance To understand big-Oh notation To estimate and compare the performance of algorithms To write code to measure the running time of a program C H A P T E R C O N T E N T S © Volkan Ersoy/iStockphoto. 12.1 SELECTION SORT 526 12.2 PROFILING THE SELECTION SORT ALGORITHM 528 12.3 ANALYZING THE PERFORMANCE OF THE SELECTION SORT ALGORITHM 530 ST 1 Oh, Omega, and Theta 531 ST 2 Insertion Sort 532 12.4 MERGE SORT 534 12.5 ANALYZING THE MERGE SORT ALGORITHM 536 ST 3 The Quicksort Algorithm 538 C&S The First Programmer 540 12.6 SEARCHING 541 12.7 PROBLEM SOLVING: ESTIMATING THE RUNNING TIME OF AN ALGORITHM 544 PT 1 Searching and Sorting 549 ST 4 Comparing Objects 549 WE1 Enhancing the Insertion Sort Algorithm 549 526 One of the most common tasks in data processing is sorting. For example, a list of employees often needs to be displayed in alphabetical order or sorted by salary. In this chapter, you will learn several sorting methods as well as techniques for comparing their performance. These techniques are useful not just for Sorting Algorithms, but also for analyzing other algorithms. Once a list of elements is sorted, one can rapidly locate individual elements. You will study the binary search algorithm that carries out this fast lookup. 12.1 Selection Sort In this section, we show you the first of several Sorting Algorithms. A sorting algo- rithm rearranges the elements of a collection so that they are stored in sorted order. To keep the examples simple, we will discuss how to sort a list of integers before going on to sorting strings or more complex data. Consider the following list values: 11 9 17 5 12 [0] [1] [2] [3] [4] An obvious first step is to find the smallest element. In this case the smallest element is 5, stored in values[3].
393 C H A P T E R 12 SORTING AND SEARCHING C H A P T E R G O A L S To compare the selection sort and merge sort algorithms To study the linear search and binary search algorithms To appreciate that algorithms for the same task can differ widely in performance To understand the big-Oh notation To be able to estimate and compare the performance of algorithms To write code to measure the running time of a program C H A P T E R C O N T E N T S © Volkan Ersoy/iStockphoto. 12.1 SELECTION SORT 394 12.2 PROFILING THE SELECTION SORT ALGORITHM 397 12.3 ANALYZING THE PERFORMANCE OF THE SELECTION SORT ALGORITHM 398 ST 1 Oh, Omega, and Theta 399 ST 2 Insertion Sort 400 12.4 MERGE SORT 402 12.5 ANALYZING THE MERGE SORT ALGORITHM 405 ST 3 The Quicksort Algorithm 407 12.6 SEARCHING 408 PT 1 Library Functions for Sorting and Binary Search 412 ST 4 Defining an Ordering for Sorting Objects 413 12.7 PROBLEM SOLVING: ESTIMATING THE RUNNING TIME OF AN ALGORITHM 413 WE1 Enhancing the Insertion Sort Algorithm 418 C&S The First Programmer 418 394 One of the most common tasks in data processing is sorting. For example, an array of employees often needs to be displayed in alphabetical order or sorted by salary. In this chapter, you will learn several sorting methods and techniques for comparing their performance. These tech- niques are useful not only for Sorting Algorithms, but also for analyzing other algorithms. Once an array of elements is sorted, one can rapidly locate individual elements. You will study the binary search algorithm that carries out this fast lookup. 12.1 Selection Sort A sorting algorithm rearranges the elements of an array so that they are stored in sorted order. In this section, we show you the first of several Sorting Algorithms, called selection sort. Consider the following array a: 11 9 17 5 12 An obvious first step is to find the smallest element. In this case the smallest element is 5, stored in a[3]. You should move the 5 to the beginning of the array.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
