Python Bubble Sort

5 Key excerpts on "Python Bubble Sort"

• 

  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

  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

  Readings from Java Data Structures

  • Joao Azevedo, James Cutajar(Authors)
  • 2020(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Lesson 2.1.1 Understanding Bubble Sorting All sorting algorithms accept a list of elements and return them ordered. The main difference between each algorithm is the manner in which the sorting is done. Bubble sorting works by swapping adjacent elements. This pushes the sorted elements toward the end of the list. Snippet 2.1 shows the pseudocode for bubble sort. The algorithm involves three simple tasks, which involves repeatedly stepping through the list to sort, comparing adjacent elements, and swapping them if the first element is bigger than the second. The swap function in the Snippet 2.1 switches the values of the two array pointers j and j+1 using a temporary variable. NOTE Practice this concept by completing Practice Exercise 2.1.A: Implementing Bubble Sort. Snippet 2.1 Bubble sort pseudocode bubbleSort(array) n = length(array) for (k = 1 until n) . for (j = 0 until -1) if(array[j] > array[j + 1]) swap(array, j, j + 1) How many passes do we need to perform on the array until our list is sorted? It turns out that to guarantee that our list is sorted, we need to do ( n 2 1) passes on the list, n being the length of our array. We will show why ( n 2 1) passes are needed in the next section, but this is the main reason why bubble sort has a runtime complexity of ( ) 2 O n , since we’re processing n elements for n 2 1 times. Although bubble sort is very easy to implement, it’s also one of the slowest sorting methods out there. In the next lesson, we will look at how we can slightly improve the performance of this algorithm. Lesson 2.1.2 Improving Bubble Sorting There are two main techniques we can adopt to improve the performance of bubble sort. It’s important to realize that although both strategies improve the overall performance of bubble sort in the average case; in the worst case, the algorithm still has the same poor runtime complexity of ( ) 2 O n . Copyright 2020 Cengage Learning. All Rights Reserved.

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

  Fundamentals of Python

  Data Structures

  • Kenneth Lambert(Author)
  • 2018(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  66 Searching, Sorting, and Complexity Analysis C H A P T E R 3 then repeats the process from the beginning of the list and goes to the next-to-last item, and so on, until it begins with the last item. At that point, the list is sorted. Figure 3-9 shows a trace of the bubbling process through a list of five items. This process makes four passes through a nested loop to bubble the largest item down to the end of the list. Once again, the items just swapped are marked with asterisks, and the sorted portion is shaded. Figure 3-9 A trace of data during a bubble sort Here is the Python function for a bubble sort: def bubbleSort(lyst): n = len(lyst) while n > 1: # Do n - 1 bubbles i = 1 # Start each bubble while i < n: if lyst[i] < lyst[i - 1]: # Exchange if needed swap(lyst, i, i - 1) i += 1 n -= 1 As with the selection sort, a bubble sort has a nested loop. The sorted portion of the list now grows from the end of the list up to the beginning, but the performance of the bubble sort is quite similar to the behavior of a selection sort: the inner loop executes n n 2 1 2 2 1 2 times for a list of size n. Thus, bubble sort is n O( ) 2 . Like selection sort, bubble sort won’t perform any swaps if the list is already sorted. However, bubble sort’s worst-case behavior for exchanges is greater than linear. The proof of this is left as an exercise for you. You can make a minor adjustment to the bubble sort to improve its best-case performance to linear. If no swaps occur during a pass through the main loop, then the list is sorted. This can happen on any pass and in the best case will happen on the first pass. You can track the presence of swapping with a Boolean flag and return from the function when the inner loop does not set this flag. Here is the modified bubble sort function: def bubbleSortWithTweak(lyst): n = len(lyst) while n > 1: swapped = False i = 1 while i < n: Copyright 2019 Cengage Learning.

  Sign up to read

  Learn more about book