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

  Machine Learning for Decision Sciences with Case Studies in Python

  • S. Sumathi, Suresh Rajappa, L Ashok Kumar, Surekha Paneerselvam(Authors)
  • 2022(Publication Date)
  • CRC Press

    (Publisher)

  Consider an array arr[] with n elements. Let i be the index pointing to the elements in the array. For each element in the array, a comparison is made between arr[ i ] and arr[ i +1]. If arr[ i ] is greater than arr[ i +1], then the elements are swapped, else kept in place. The process is repeated, and each pair of the array arr is compared until the whole array is completely sorted. FIGURE 2.16 Bubble sort. 2.4.5.11 Implementation of Bubble Sort in Python defbubbleSort(mylist): forpassnum in range(len(mylist)-1,0,-1): for i in range(passnum): ifmylist[i]>mylist[i+1]: temp = mylist[i] mylist[i] = mylist[i+1] mylist[i+1] = temp mylist = [1, 2, 3, 5, 47, 31, 13, 17, 19, 23, 29, 11, 37, 31, 47] # sameple list to get it bubble sorted print('the original list:', mylist) # Before sort bubbleSort(mylist) print('the sorted list:', mylist) # After sort Testing the results the original list: [1, 2, 3, 5, 47, 31, 13, 17, 19, 23, 29, 11, 37, 31, 47] the sorted list: [1, 2, 3, 5, 11, 13, 17, 19, 23, 29, 31, 31, 37, 47, 47] 2.4.5.12 Insertion Sort The insertion sort algorithm is a type of in-place sorting algorithm, which in turn is based on the comparison. In this algorithm, a sub-array is maintained, and this sub-array is sorted continuously. Successive elements of the array are added or inserted into this sub-array and sorted within the sub-array. Hence, the name insertion sort. Sometimes, the algorithm is referred to as an online algorithm since the values are sorted and added into the sub-array. The insertion sort algorithm is simple to implement, and it is efficient on small datasets. This comparison sort builds a sorted array by adding one element at a time. The algorithms are explained with a flowchart, as shown in Figure 2.17. Consider an array arr[] whose length is n. The first element of the array is used to form the sub-array, and its position is noted. The next element is chosen for comparison with the first element

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  An Introduction to Python Programming: A Practical Approach

  step-by-step approach to Python programming with machine learning fundamental and theoretical principles.

  • Dr. Krishna Kumar Mohbey; Dr. Brijesh Bakariya(Author)
  • 2021(Publication Date)
  • BPB Publications

    (Publisher)

  Sorting means arranging the data in either ascending or descending order. The primary task of sorting algorithms is to organize data elements in a particular order. If our data is properly sorted in order, then it would search the element fast. Moreover, sorting maintains the data structure. Sorting may also be used to display data in a more readable format. Sorting can be used in a variety of contexts, including the dictionary, telephone directory, and so on.

  Python uses the sort() method for sorting elements of a given list in a specific ascending or descending order. The syntax of the sort() method is:

  Syntax: list.sort(key=…, reverse=…) sorted(list, key=…, reverse=…)

  An important point which we have to remember is the basic difference between sort() and sorted() is that the sort() method changes the list directly and doesn't return any value, while sorted() doesn't change the list and returns the sorted list.

  In the sort() and sorted() methods, there are two parameters: reverse and key . The sorted list is reversed if the reverse parameter is true. A key parameter is used as a sort comparison key.

  Let us take an example to understand this concept. Example 6.43: vowels_var = ['i', 'a', 'u', 'o', 'e'] # vowels list vowels_var.sort() # sort the vowels print ('Sorted list:', vowels_var) # print vowels vowels_var = ['i', 'a', 'u', 'o', 'e'] # vowels list vowels_var.sort(reverse=True) #Sort the list in Descending order print ('Sorted list:', vowels_var) # print vowels #Custom Sorting With key list1 = ['ppp', 'aaaa', 'd', 'bb'] print (sorted(list1, key=len)) #Sort the list by the length of the values: def my_sort_fun(n): return len(n) faculty = ['Brijesh', 'Krishna', 'Amit', 'Zubin'] faculty.sort(key=my_sort_fun) Output: Sorted list: ['a', 'e', 'i', 'o', 'u'] Sorted list: ['u', 'o', 'i', 'e', 'a'] ['d', 'bb', 'ppp', 'aaaa']

  Types of sorting

  The following are the various types of sorting:

  • In-place sorting

  Sign up to read

  Learn more about book