Python Sorting

4 Key excerpts on "Python Sorting"

• 

  eBook - PDF

  Data Structures and Algorithms in Python

  • Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
  • 2013(Publication Date)
  • Wiley

    (Publisher)

  Given a collection, the goal is to rearrange the elements so that they are ordered from smallest to largest (or to produce a new copy of the sequence with such an order). As we did when studying priority queues (see Section 9.4), we assume that such a consistent order exists. In Python, the natural order of objects is typically 1 defined using the < operator having following properties: • Irreflexive property: k < k. • Transitive property: if k 1 < k 2 and k 2 < k 3 , then k 1 < k 3 . The transitive property is important as it allows us to infer the outcome of certain comparisons without taking the time to perform those comparisons, thereby leading to more efficient algorithms. Sorting is among the most important, and well studied, of computing problems. Data sets are often stored in sorted order, for example, to allow for efficient searches with the binary search algorithm (see Section 4.1.3). Many advanced algorithms for a variety of problems rely on sorting as a subroutine. Python has built-in support for sorting data, in the form of the sort method of the list class that rearranges the contents of a list, and the built-in sorted function that produces a new list containing the elements of an arbitrary collection in sorted order. Those built-in functions use advanced algorithms (some of which we will describe in this chapter), and they are highly optimized. A programmer should typically rely on calls to the built-in sorting functions, as it is rare to have a special enough circumstance to warrant implementing a sorting algorithm from scratch. With that said, it remains important to have a deep understanding of sorting algorithms. Most immediately, when calling the built-in function, it is good to know what to expect in terms of efficiency and how that may depend upon the initial order of elements or the type of objects that are being sorted.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Hands-On Data Structures and Algorithms with Python

  • Dr. Basant Agarwal(Author)
  • 2022(Publication Date)
  • Packt Publishing

    (Publisher)

  11

  Sorting

  Sorting means reorganizing data in such a way that it is in ascending or descending order. Sorting is one of the most important algorithms in computer science and is widely used in database-related algorithms. For several applications, if the data is sorted, it can efficiently be retrieved, for example, if it is a collection of names, telephone numbers, or items on a simple to-do list.

  In this chapter, we’ll study some of the most important and popular sorting techniques, including the following:

  • Bubble sort
  • Insertion sort
  • Selection sort
  • Quicksort
  • Timsort

  Technical requirements

  All source code used to explain the concepts of this chapter is provided in the GitHub repository at the following link: https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Third-Edition/tree/main/Chapter11

  Sorting algorithms

  Sorting means arranging all the items in a list in ascending or descending order. We can compare different sorting algorithms by how much time and memory space is required to use them.

  The time taken by an algorithm changes depending on the input size. Moreover, some algorithms are relatively easy to implement, but may perform poorly with respect to time and space complexity, whereas other algorithms are slightly more complex to implement, but can perform well when sorting longer lists of data. One of the sorting algorithm, merge sort, we have already discussed in Chapter 3 , Algorithm Design Techniques and Strategies . We will discuss several more sorting algorithms one by one in detail along with their implementation details, starting with the bubble sort algorithm.

  Bubble sort algorithms

  The idea behind the bubble sort algorithm is very simple. Given an unordered list, we compare adjacent elements in the list, and after each comparison, we place them in the right order according to their values. So, we swap the adjacent items if they are not in the correct order. This process is repeated n-1 times for a list of n

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  50 Algorithms Every Programmer Should Know

  An unbeatable arsenal of algorithmic solutions for real-world problems

  • Imran Ahmad(Author)
  • 2023(Publication Date)
  • Packt Publishing

    (Publisher)

  The ability to efficiently sort and search items in a complex data structure is important as it is needed by many modern algorithms. The right strategy to sort and search data will depend on the size and type of the data, as discussed in this chapter. While the end result is exactly the same, the right sorting and searching algorithm will be needed for an efficient solution to a real-world problem. Thus, carefully analyzing the performance of these algorithms is important.

  Sorting algorithms are used extensively in distributed data storage systems such as modern NoSQL databases that enable cluster and cloud computing architectures. In such data storage systems, data elements need to be regularly sorted and stored so that they can be retrieved efficiently.

  The following sorting algorithms are presented in this chapter:

  • Bubble sort
  • Merge sort
  • Insertion sort
  • Shell sort
  • Selection sort

  But before we look into these algorithms, let us first discuss the variable-swapping technique in Python that we will be using in the code presented in this chapter.

  Swapping variables in Python

  When implementing sorting and searching algorithms, we need to swap the values of two variables. In Python, there is a standard way to swap two variables, which is as follows:

  var_1 = 1 var_2 = 2 var_1, var_2 = var_2, var_1 print (var_1,var_2)

  2, 1 This simple way of swapping values is used throughout the sorting and searching algorithms in this chapter. Let’s start by looking at the bubble sort algorithm in the next section.

  Bubble sort

  Bubble sort is one of the simplest and slowest algorithms used for sorting. It is designed in such a way that the highest value in a list of data bubbles makes its way to the top as the algorithm loops through iterations. Bubble sort requires little runtime memory to run because all the ordering occurs within the original data structure. No new data structures are needed as temporary buffers. But its worst-case performance is O(N2) , which is quadratic time complexity (where N is the number of elements being sorted). As discussed in the following section, it is recommended to be used only for smaller datasets. Actual recommended limits for the size of the data for the use of bubble sort for sorting will depend on the memory and the processing resources available but keeping the number of elements (N

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Algorithms 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.

  Sign up to read

  Learn more about book