Bubble Sort

12 Key excerpts on "Bubble Sort"

• 

  eBook - PDF

  Programming Logic & Design, Comprehensive

  • Joyce Farrell(Author)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  WCN 02-300 Using the Bubble Sort Algorithm When you learn a method such as sorting, programmers say you are learning an algorithm. An algorithm is a list of instructions that accomplish a task. In this section, you will learn about the Bubble Sort algorithm for sorting a list of simple values; later in this chapter, you will learn more about how multifield records are sorted. One of the simplest sorting techniques to understand is a Bubble Sort , in which items in a list are compared with each other in pairs. You can use a Bubble Sort to arrange data items in either ascending or descending order. A Bubble Sort examines items in a list, and when an item is out of order, it trades places, or is swapped, with the item below it. With an ascending Bubble Sort, after each adjacent pair of items in a list has been compared once, the largest item in the list will have “sunk” to the bottom. After many passes through the list, the smallest items rise to the top like bubbles in a carbonated drink. A Bubble Sort is sometimes called a sinking sort . To understand the Bubble Sort algorithm, you first must learn about swapping values. Understanding Swapping Values A concept central to many sorting algorithms, including the Bubble Sort, is the idea of swapping values. When you swap values stored in two variables, you exchange their values; you set the first variable equal to the value of the second, and the second variable equal to the value of the first. However, there is a trick to swapping any two values. Assume that you have declared two variables as follows: num score1 = 90 num score2 = 85 You want to swap the values so that score1 is 85 and score2 is 90. If you first assign score1 to score2 using a statement such as score2 = score1 , both score1 and score2 hold 90, and the value 85 is lost. Similarly, if you first assign score2 to score1 using a statement such as score1 = score2 , both variables hold 85, and the value 90 is lost.

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

  No longer available |Learn more

  Beginning Java Data Structures and Algorithms

  Sharpen your problem solving skills by learning core computer science concepts in a pain-free manner

  • James Cutajar(Author)
  • 2018(Publication Date)
  • Packt Publishing

    (Publisher)

  Sorting Algorithms and Fundamental Data Structures

  In the previous chapter, we saw how the intersection problem can be improved by using a sorting algorithm. This is common with many problems. If the data is organized in an ordered manner, a more efficient algorithm can be developed. In this chapter, we will start by exploring three types of sorting techniques, which are bubble, quick, and merge sorting. Later, we will learn different ways to organize data using fundamental data structures.

  By the end of this chapter, you will be able to:

  • Describe how Bubble Sorting works
  • Implement faster sorting with quick sort
  • Characterize merge sorting
  • Build a linked list data structure
  • Implement queues
  • Describe the stack data structure

  Passage contains an image

  Introducing Bubble Sorting

  Bubble Sorting is the simplest sorting algorithm out there. The technique involves making multiple passes over the input array and swapping unordered elements close to one another. The technique is called Bubble Sort, as the sorted list "bubbles" up from the tail end of the list.

  Passage contains an image

  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 around if the first element is bigger than the second.

  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 - 1) passes on the list, n being the length of our array. We will show why (n - 1) passes are needed in the next section, but this is the main reason why Bubble Sort has a runtime complexity of

  O(n2 )

  , since we're processing n elements for n - 1

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  A Practical Approach to Data Structure and Algorithm with Programming in C

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

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  PHP 7 Data Structures and Algorithms

  • Mizanur Rahman(Author)
  • 2017(Publication Date)
  • Packt Publishing

    (Publisher)

  Sorting can be classified into different types based on the type of data set, direction, computational complexities, memory usage, space usage, and so on. Here are few of the sorting algorithms we will explore in this chapter:

  • Bubble Sort
  • Insertion sort
  • Selection sort
  • Quick sort
  • Merge sort
  • Bucket sort

  We will keep our discussion limited to the preceding list, as they are the most commonly used sorting algorithms and can be grouped and classified under different criteria such as simple sorting, efficient sorting, distribution sorting, and so on. We will now explore each of the sorting functionalities, their implementations, and complexity analysis, along with their pros and cons. Let's get started with the most commonly used sorting algorithm - Bubble Sort.

  Passage contains an image

  Understanding Bubble Sort

  Bubble Sort is the most commonly used sorting algorithm in the programming world. Most of the programmers start learning about sorting with this algorithm. It is a comparison-based sorting algorithm, which is always referred to as one of the most inefficient sorting algorithms. It requires maximum number of comparisons, and the average, and worst case complexity are the same.

  In Bubble Sort, each item of the list is compared with the rest of the items and swapped if required. This continues for each item in the list. We can sort either in ascending or descending order. Here is the pseudo algorithm for Bubble Sort:

  procedure bubbleSort( A : list of sortable items ) n = length(A) for i = 0 to n inclusive do for j = 0 to n-1 inclusive do if A[j] > A[j+1] then swap( A[j], A[j+1] ) end if end for end for end procedure

  As we can see from the preceding pseudocode, we are running one loop to ensure that we iterate each item of the list. The inner loop ensures that, once we point to an item, we are comparing the item with other items in the list. Based on our preference, we can swap the two items. The following image shows a single iteration to sort one item of the list. Let's assume our list has the following items: 20 , 45 , 93 , 67 , 10 , 97 , 52 , 88 , 33 , 92

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  A Textbook of Data Structures and Algorithms, Volume 3

  Mastering Advanced Data Structures and Algorithm Design Strategies

  • G. A. Vijayalakshmi Pai(Author)
  • 2022(Publication Date)
  • Wiley-ISTE

    (Publisher)

  132 A Textbook of Data Structures and Algorithms 3 as sorting by exchange, sorting by insertion, sorting by distribution, sorting by selection and so on. However, in many cases, it is difficult to classify the algorithms as belonging to a specific family only. A sorting technique is said to be stable if keys that are equal retain their relative orders of occurrence, even after sorting. In other words, if K 1 and K 2 are two keys such that K 1 = K 2 , and p(K 1 ) < p(K 2 ) where p(K i ) is the position index of the keys in the unsorted list, then after sorting, p’(K 1 ) < p’(K 2 ), where p’(K i ) is the position index of the keys in the sorted list. If the list of data or records to be sorted are small enough to be accommodated in the internal memory of the computer, then it is referred to as internal sorting. On the other hand, if the data list or records to be sorted are voluminous and are accommodated in external storage devices such as tapes, disks and drums, then the sorting undertaken is referred to as external sorting. External sorting methods are quite different from internal sorting methods and are discussed in Chapter 18. In this chapter, we discuss the internal sorting techniques of Bubble Sort, insertion sort, selection sort, merge sort, shell sort, quick sort, heap sort, radix sort, counting sort and bucket sort. 17.2. Bubble Sort Bubble Sort belongs to the family of sorting by exchange or transposition, where during the sorting process, pairs of elements that are out of order are interchanged until the whole list is ordered. Given an unordered list 𝐿 = {𝐾 ଵ , 𝐾 ଶ , 𝐾 ଷ , . . . 𝐾 ௡ }, Bubble Sort orders the elements in ascending order (i.e.), 𝐿 = {𝐾 ଵ , 𝐾 ଶ , 𝐾 ଷ , . . . 𝐾 ௡ }, 𝐾 ଵ ≤ 𝐾 ଶ ≤. . . 𝐾 ௡ . Given the unordered list 𝐿 = {𝐾 ଵ , 𝐾 ଶ , 𝐾 ଷ , . . . 𝐾 ௡ } of keys, Bubble Sort compares pairs of elements 𝐾 ௜ and 𝐾 ௝ , swapping them if 𝐾 ௜ > 𝐾 ௝ .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structure and Algorithm

  • Nikhat Raza Khan, Manmohan Singh, Piyush Kumar Shukla(Authors)
  • 2023(Publication Date)
  • Arcler Press

    (Publisher)

  To do this, it is necessary to think about what it means for an array to be sorted. It is easy to see that the list 1, 5, 6, 19, 23, 45, 67, 98, 124, 401 is sorted, whereas the list 4, 1, 90, 34, 100, 45, 23, 82, 11, 0, 600, 345 is not. The property that makes the second one “not sorted” is that, there are adjacent elements that are out of order. The first item is greater than the second instead of less, and likewise the third is greater than the fourth and so on. Once this observation is made, it is not very hard to devise a sort that precedes by examining adjacent elements to see if they are in order, and swapping them if they are not. The following are the methods, which can be used for performing sorting: • Bubble Sort; • Selection sort; • Insertion sort; • Quick sort; • Merge sort; Sorting Algorithms 159 • Address calculation sort; • Heap sort. 4.2.1. Bubble Sort In this sorting algorithm, multiple swapping takes place in one pass. Smaller elements move or ‘bubble’ up to the top of the list, hence the name bubble is given to the algorithm. This most elementary sorting method proceeds by scanning through the elements one pair at a time, and swapping any adjacent pairs it finds to be out of order. Thus, for the list in the example given below, the first two items are swapped, then the (new) second item is compared to the third (and not swapped,) the third is compared to the fourth, and so on to the end.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Learning JavaScript Data Structures and Algorithms

  • Loiane Groner(Author)
  • 2018(Publication Date)
  • Packt Publishing

    (Publisher)

  When developers start learning sorting algorithms, they usually learn the Bubble Sort algorithm first, because it is the simplest of all the sorting algorithms. However, it is one of the worst-case sorting algorithms with respect to runtime, and you will see why.

  The Bubble Sort algorithm compares every two adjacent values and swaps them if the first one is bigger than the second one. It has this name because the values tend to move up into the correct order, like bubbles rising to the surface.

  Let's implement the Bubble Sort algorithm, as follows:

  function bubbleSort(array, compareFn = defaultCompare) { const { length } = array; // {1} for (let i = 0; i < length; i++) { // {2} for (let j = 0; j < length - 1; j++) { // {3} if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { // {4} swap(array, j, j + 1); // {5} } } } return array;}

  Each non-distribution sort algorithm we will create in this chapter will receive the array to be sorted  as a parameter and a comparison function. To make testing easier to understand, we will work with arrays of numbers in our examples. But in case we need to sort an array of complex objects (array of people objects sorted by age property), our algorithm will be ready as well. The compareFn function to be used as default is the defaultCompare function we have used in previous chapters (return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN).

  First, let's declare a variable called length, which will store the size of the array ({1}). This step will help us to get the size of the array on lines {2} and {3}, and this step is optional. Next, we will have an outer loop ({2}) that will iterate the array from its first position to the last one, controlling how many passes are done in the array (which should be one pass per item of the array as the number of passes is equal to the size of the array). Then, we have an inner loop ({3}) that will iterate the array, starting from its first position to the penultimate value that will actually do the comparison between the current value and the next one ({4}). If the values are out of order (that is, the current value is bigger than the next one), then we will swap them ({5}), meaning that the value of the j+1 position will be transferred to the j position and vice versa.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Programming with C++

  • Kyla McMullen, Elizabeth Matthews, June Jamrich Parsons, , Kyla McMullen, Kyla McMullen, Elizabeth Matthews, June Jamrich Parsons(Authors)
  • 2021(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. PROGRAMMING WITH C++ 438 early after one, two, or three passes, each equally likely assuming a random shuffle of the numbers. To find an average runtime, you can add the runtimes of all possible stopping-early situations, and then divide by n, as in the following: 1 1 1 1 1 2 3 … pass passes passes n passes n The summation pattern of 1 + 2 + 3 up to some n is the following known summation: 1 1 1 1 5 1 n n n 1 2 3 ( 1) 2 … Apply this formula into the original summation and simplify the fractional on the right as follows: 1 5 1 ( 1) 2 1 2 n n n n passes Each pass takes n work, so you rewrite the equation as follows: 1 5 1       1 2 2 2 n n n n work Remember that in Big-O notation, you can retain only the largest part of the polynomial and drop constant multipliers or divisors. As a result, even on average, Bubble Sort is still O(n 2 ) work. Bubble Sort swaps items many times to order them, so it does not need additional memory to store items. Therefore, Bubble Sort is an in-place sort. Bubble Sort swaps items only when they are strictly out of order. Because it does not swap identical items, Bubble Sort is also a stable algorithm. Bubble Sort is not the best option for most data sets. Instead, it is a simple and easy-to-program approach to sorting and provides a good introduction to how computers can sort items. If the data set is small enough that the runtime does not matter, then you could use Bubble Sort, though it is not the best sorting algorithm. If your data set is already mostly sorted, Bubble Sort has the best-case runtime of O(n) because it can stop early. Otherwise, use a different sort. 24.3 QUICKSORT Defining the Quicksort Algorithm (24.3.1, 24.3.2, 24.3.4) Quicksort approximates an efficient sort.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures with C Programming

  • Anil Kumar Yadav, Vinod Kumar Yadav(Authors)
  • 2019(Publication Date)
  • Arcler Press

    (Publisher)

  This approach of sorting requires “n – 1” passes, to sort the given list of data in some proper order. Assume that if “n” number of elements present in an array “A.” The first pass starts with the comparison of the value of n th and (n – 1) th position element. If the “n th ” position element is smaller than the (n – 1) th position element then these two elements are interchanged. The smaller value is compared with the value of the (n – 2) th position element. And required, the element is interchanged to place the smaller among the two in the (n – 2) th position. Elements which have a small value that move or “bubble up.” The entire process is to continue in this manner and the first pass ends with the comparison and possible exchange of elements A[1] and A[0]. The whole sorting method terminated with “(n – 1) ” passes, thereby resulting into a sorted list. The algorithm of Bubble Sort: Step 1: Read the total number of elements say n. Step 2: Store the elements in an array. Step 3: Set the initial element i = 0. Step 4: Compare the adjacent elements. 4 (a). For ascending order, if the first element is smaller than the second element then no interchange of this element. Otherwise, interchange the element position. 4 (b). For descending order, if the first element is smaller than the second element then interchange of this element. Otherwise no interchange the element position. Step 5: Repeat step 4 for all n elements. Step 6: Increment the value of i by 1 and repeat step 4, 5 for i < n. Step 7: Print the sorted list of elements. Step 8: Stop. Example: Consider 6 unsorted elements are given that elements are sort in ascending order 415, 515, 315, 910, 710, 310. Suppose an array “A” consists of 6 elements as:

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  C++ Programming

  Program Design Including Data Structures

  • D. Malik(Author)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Suppose list[0...n -1] is a list of n elements, indexed 0 to n - 1 . We want to rear-range, that is, sort, the elements of list in increasing order. The Bubble Sort algo-rithm works as follows: n = O ( n ) 1 2 n + = O ( n ) 1 2 n + 1 2 = Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-300 1298 | Chapter 18: Searching and Sorting Algorithms In a series of n -1 iterations, the successive elements list[index] and list[index + 1] of the list are compared. If list[index] is greater than list[index + 1] , then the elements list[index] and list[index + 1] are swapped. It follows that the smaller elements move toward the top, and the larger elements move toward the bottom. In the first iteration, we consider the list[0...n – 1] . As you will see after the first iteration, the largest element of the list is moved to the last position, which is position n – 1 , in the list. In the second iteration, we consider the list[0...n – 2] . After the second iteration, the second largest element in the list is moved to the position n – 2 , wh i ch is second to the last position in the list. In the third iteration, we consider the list[0...n – 3] , and so on. As you will see, after each iteration, the size of the unsorted portion of the list shrinks. Consider the list[0...4] of five elements, as shown in Figure 18-6. list[0] list list[1] list[2] list[3] list[4] 10 7 19 5 16 FIGURE 18-6 List of five elements Iteration 1: Sort list[0...4] . Figure 18-7 shows how the elements of list get rearranged in the first iteration. compare and swap compare unsorted list 10 7 19 5 16 7 10 19 5 16 7 10 19 5 16 7 10 5 19 16 7 10 5 16 19 compare and swap compare and swap FIGURE 18-7 Elements of list during the first iteration Notice that in the first diagram of Figure 18-7, list[0] > list[1] . Therefore, list[0] and list[1] are swapped. In the second diagram, list[1] and list[2] are compared.

  Sign up to read

  Learn more about book