Insertion Sort Python

5 Key excerpts on "Insertion Sort Python"

• 

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

  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 - ePub

  The Self-Taught Computer Scientist

  The Beginner's Guide to Data Structures & Algorithms

  • Cory Althoff(Author)
  • 2021(Publication Date)
  • Wiley

    (Publisher)

  Here is how an insertion sort algorithm works on a list with four elements: 6, 5, 8, and 2. Your algorithm starts with the second item in your list, which is 5:

  [6, 5, 8, 2]

  Next, you compare the current item to the previous item in your list. Six is greater than 5, so you swap them:

  [5, 6, 8, 2]

  Now the left half of your list is sorted, but the right half is not:

  [5, 6, 8, 2]

  Then, you move to the third item in your list. Six is not greater than 8, so you don't swap 8 and 6:

  [5, 6, 8, 2]

  Because the left half of your list is sorted, you do not have to compare 8 and 5:

  [5, 6, 8, 2]

  Next, you compare 8 and 2:

  [5, 6, 8, 2]

  Because 8 is greater than 2, you go one by one through the sorted left half of the list, comparing 2 to each number until it arrives at the front and the entire list is sorted:

  [2, 5, 6, 8]

  Here is how to code an insertion sort in Python:

  def insertion_sort(a_list): for i in range(1, len(a_list)): value = a_list[i] while i > 0 and a_list[i - 1] > value: a_list[i] = a_list[i - 1] i = i - 1 a_list[i] = value return a_list

  You start by defining an insertion_sort function that takes a list of numbers as input:

  def insertion_sort(a_list):

  Your function uses a for loop to iterate through each item in the list. Then it uses a while loop for the comparisons your algorithm makes when adding a new number to the sorted left side of your list:

  for i in range(1, len(a_list)): … while i > 0 and a_list[i - 1] > value: …

  Your for loop begins with the second item in your list (index 1). Inside your loop, you keep track of the current number in the variable value :

  for i in range(1, len(a_list)): value = a_list[i]

  Your while loop moves items from the unsorted right half of your list to the sorted left half. It continues as long as two things are true: i must be greater than 0, and the previous item in the list must be greater than the item that comes after it. The variable i must be greater than 0 because your while loop compares two numbers, and if i

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Explorations in Computing

  An Introduction to Computer Science and Python Programming

  • John S. Conery(Author)
  • 2014(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  For searching and sorting, the individual steps of an algorithm compare objects in a list or move objects around in a list. What we learned is that repeated execution of these simple steps will eventually find an item in a list or rearrange the order of the items. The two algorithms we looked at were linear search and insertion sort. As its name implies, a program doing a linear search simply looks at each object in order, from front to back, in effect “walking through” the list. The insertion sort algorithm has the same basic structure, iterating over each position in a list, but on each iteration the program removes an item and reinserts it someplace closer to the beginning of the list. The main thing to understand about insertion sort is that at the start of each iteration an index variable points to the location of the element that will be moved. The region to the left of this location is already sorted, and the algorithm just has to find the correct location for the item somewhere in this sorted region. Our experiments with these algorithms introduced several new constructs in Python. The previous chapter introduced for statements to control iteration, and here we learned about a new statement called a while statement. Either of these statements can be used to control the repetition of a set of statements in the loop body. We also saw how to combine Boolean expressions into more complex expressions through the use of Boolean operators ( and , or , and not ) and how to use the special object called None as a signal that no value was found during a search. Finally, an important idea in computing introduced in this chapter is the concept of scal-ability. Linear search and insertion sort are easy to understand and easy to implement, so they are widely used for small data sets. However, as the lengths of the input lists grow longer the algorithms become less and less efficient.

  Sign up to read

  Learn more about book