Bubble Sort Explained — A Data Scientists Algorithm Guide | by Richmond Alake | Jan, 2023


As software engineers and data scientists, we often take sorting functions for granted. These algorithms may not be the most glamorous or heavily discussed aspects of our work, but they play a vital role in the technologies we use every day. For example, imagine trying to organize the contact list on your phone without a way to sort alphabetically or sorting products on an eCommerce website by price and category. It’s easy to overlook the importance of sorting algorithms, but they are integral to our work as programmers.

Even though most programming languages, such as Java, Python, C# etc., come with built-in functions for common sorting algorithms, it’s still important for us to have a basic understanding of how these algorithms work. This knowledge allows us to make informed decisions about which algorithm to use based on its space and time complexities, especially when working with large datasets as data scientists. So don’t underestimate the humble sorting function — they may not be the star of the show, but they are the unsung heroes of the tech industry.

In this article, we’ll dive into the bubble sort algorithm, examining its implementation in Python and JavaScript. We’ll also take a closer look at the intuition behind the algorithm and discuss considerations for time and space complexity. By the end of this article, you’ll have a solid understanding of when it is appropriate to use the bubble sort algorithm in your programs, as well as an overview of its space and time complexities.

Get a detailed overview of how hardware innovations are changing how data teams build analytics and machine learning applications in the free ebook, Hardware > Software > Process.

It is always more helpful to first grasp the concept when attempting to understand and later recall an algorithm. By familiarizing yourself with the idea before jumping into implementation, you will better retain the information for future use. Bubble sort is no exception.

To sort an array [2, 3, 4, 5, 1] in ascending order using the bubble sort algorithm, we start from the first element [2] and compare it with the second element [3]. If the first element is greater than the second, we swap them. We continue this process of comparing pairs of elements until we reach the end of the array. This way, the largest elements will be shifted to the end of the array, and the smallest elements will be shifted to the beginning of the array.

The name “bubble sort” refers to the way in which larger elements “bubble” to the top or the end of the array as they are repeatedly compared and swapped with smaller elements. By the end of the sorting process, the array will be fully sorted in ascending order.

The following is a list of unordered numbers that we will use bubble sort to organize:

Image by Author

The first step is to focus only on the first two numbers, which in this example are 5 and 9. You can visualize considering just the two elemtns 5 and 9 as shown in the image below:

Image by Author

Then, you must determine if the numbers inside the bubble are in order. If they aren’t in proper order, switch them around to make it right. Fortunately for us, they are already arranged in ascending order. 5 is less than 9, so it comes before 9. This means we don’t have anything left to do — we move our bubble one step further like this:

Image by Author

We conduct the same step in the next iteration of the array. However, this time 9 is greater than 1, but it’s also in front of it. So, to rectify that, the position of both elements is swapped. Here’s how the list looks now:

Image by Author

Now that the elements are swapped, the bubble progresses to successive pairs. And the steps repeat until the last pairs in the array have undergone a check to swap. The first run through the array will look like this:

Image by Author

The bubble sort algorithm is a simple yet effective way to sort an array of elements. It works by repeatedly iterating through the array and comparing pairs of elements, swapping their positions if they are out of order. This process is repeated until the entire array is sorted.

One thing to remember is that the number of passes required to sort an array is equal to the number of elements in the array. For example, a 6-element array will need to go through 6 passes in order to be fully sorted in ascending order.

However, it’s possible to make the bubble sort algorithm more efficient by limiting the number of operations or passes conducted on the array. This is because the last element of the array is always the maximum value, so there is no need to continue comparing all elements beyond this point in future passes through the array. We’ll see this optimization in action as we implement the bubble sort algorithm in Python and JavaScript in the sections below.

This section implements the bubble sort algorithm using the Python programming language. We will observe a naive implementation and a more efficient version of the bubble sort algorithm.

Initialize a Python array containing integer elements

unsortedData = [20, 33, 12, 53, 24, 65, 23, 4, 53, 1];

Define a function named ‘bubbleSort’ that accepts an array in its parameter named ‘data’. First, let’s attempt to pass through the array that swaps any elements that satisfy the condition that if the left element at a particular index is greater than an element to the right, we execute a swap operation between those two elements.

One thing to note is the assignment of the left element in any iteration to a temporary variable ‘tempValue’ and then assigning the right element to the temporary variable

def bubbleSort(data):

for i in range(0, len(data)):
if i+1 < len(data):
if data[i] > data[i+1]:
tempValue = data[i]
data[i] = data[i+1]
data[i+1] = tempValue

return data

The code snippet above, when called with an unsorted array passed as its arguments, will conduct the bubbleSort function pass once on the array. And in most cases, will not completely sort the array in ascending order.

sortedData = bubbleSort(unsortedData)
print(sortedData)
>>>[20, 12, 33, 24, 53, 23, 4, 53, 1, 65]

To fix this, we have to iterate through the array we want to sort as many times as there are combinations of pairs. Simply kept, the number of iterations to conduct is the length of the unsorted array squared (len(unsortedArrray)²). This is the naive implementation.

def bubbleSort(data):

# Iterate through the array enough times to consider every possible swap pairs
for _ in range(0, len(data)):
for i in range(0, len(data)):
if i+1 < len(data):
if data[i] > data[i+1]:
tempValue = data[i]
data[i] = data[i+1]
data[i+1] = tempValue

return data

Running the bubble sort function again with the unsorted array passed as an argument will result in an array sorted in ascending order provided as an output

sortedData = bubbleSort(unsortedData)
print(sortedData)
>>> [1, 4, 12, 20, 23, 24, 33, 53, 53, 65]

Optimized Version of Bubble Sort

While the naive version of the bubble sort algorithm does work, it has some unnecessary and redundant operations. In particular, it compares elements at the end of the array that are already the maximum values present in the array. This is because on each pass through the array, the bubble sort algorithm moves the maximum element values to the end of the array.

To optimize the bubble sort algorithm, we can reduce the number of swap operations required by keeping track of the portion of the array that we want to consider for comparison. We can do this by starting with the maximum length of the array and decrementing it by 1 after each pass, reducing the area of the array that the swap operation acts upon. This way, we can avoid comparing with the last elements of the array on each pass, which are already in their correct position.

By using this optimization, we can make the bubble sort algorithm more efficient and reduce the number of unnecessary operations it performs.

unsortedData = [20, 33, 12, 53, 24, 65, 23, 4, 53, 1];
end = len(unsortedData)

def bubbleSort(data):
global end
for _ in range(0, end):
for i in range(0, end):
if i+1 < end:
if data[i] > data[i+1]:
tempValue = data[i]
data[i] = data[i+1]
data[i+1] = tempValue
end = end - 1
return data

sortedData = bubbleSort(unsortedData)
print(sortedData)
>>> [1, 4, 12, 20, 23, 24, 33, 53, 53, 65]

Further refactoring could be conducted to ensure the code above is readable and efficient. Below is an implementation of the same algorithm in JavaScript, a programming language popular with data practitioners and software engineers.

const unsortedData = [20, 33, 12, 53, 24, 65, 23, 4, 53, 1];
let end = unsortedData.length - 1

const bubbleSort = (data) => {

for (let i = 0; i < end; i++) {
if (data[i] > data[i + 1]) {
const valueInRight = data[i]
data[i] = data[i+1]
data[i+1] = valueInRight
}
}
end--
}

for (let i = 0; i < unsortedData.length; i++) {
bubbleSort(unsortedData)
}

console.log(unsortedData)

Data scientists must understand the performance of a sorting algorithm and how much time/space it requires. This allows you to select the best sorting algorithm depending on your specific situation, as many options are available.

When bubble sort is used on an array already in ascending order, it requires only one pass through the entire array. This is considered the best-case scenario. In practice, though, this only occurs sometimes, and bubble sort usually necessitates n(n-1)/2 swaps or comparisons to achieve a sorted array.

The bubble sort algorithm’s average/worst time complexity is O(n²), as we have to pass through the array as many times as there are pairs in a provided array. Therefore, when time is a factor, there may be better options.

  • Time complexity Worst Case: O(n²)
  • Time complexity Average Case: O(n²)
  • Time complexity Best Case: O(n), the array is already sorted

In terms of space complexity, since we only swapped the elements with one another and never stored anything, we don’t need any extra space to run the algorithm. This is amazing because it means the space complexity comes out as constant, or O(1). This makes it an in-place algorithm that works by modifying the input directly.

The bubble sort algorithm may not be the most well-known or highly-regarded sorting algorithm, but as we’ve seen, it’s not a terrible option either. With a time complexity of O(n²) and a space complexity of O(1), it’s a simple algorithm that is easy for beginners to understand. However, its slow speed may make it less practical for certain applications.

Despite its limitations, the bubble sort algorithm can be a useful starting point for learning about sorting algorithms and data structures. It’s a good way to get a basic understanding of how these algorithms work, and can help you build a foundation for learning more complex algorithms later on.

That being said, the bubble sort algorithm may not be the best choice for time-sensitive material, as its slow speed can be prohibitive. However, if you’re willing to sacrifice some space for time, it may work well for you. Ultimately, the choice of sorting algorithm will depend on your specific needs and goals. By learning about the bubble sort algorithm, you can make more informed decisions about which algorithm is best for your needs.

Bubble sort is a sorting algorithm that uses comparison methods to sort an array. The algorithm compares pairs of elements in an array and swaps them if the left pair(position) is greater than the right pair(position+1). This process is repeated until the entire array is sorted.

  • How many passes does Bubble Sort require?

Bubble Sort requires n(n-1)/2 passes through all elements in order for the final array sorted in ascending order.

  • What is the worst time complexity of Bubble Sort?

The worst time complexity of Bubble Sort is O(n2).

  • What is the worst time complexity of Bubble Sort?

The best time complexity of Bubble Sort is O(n), and this occurs when the array is already sorted.

  • What is the space complexity of Bubble Sort?

Bubble sort has an O(1) space complexity, as it works in-place by modifying the input directly.


As software engineers and data scientists, we often take sorting functions for granted. These algorithms may not be the most glamorous or heavily discussed aspects of our work, but they play a vital role in the technologies we use every day. For example, imagine trying to organize the contact list on your phone without a way to sort alphabetically or sorting products on an eCommerce website by price and category. It’s easy to overlook the importance of sorting algorithms, but they are integral to our work as programmers.

Even though most programming languages, such as Java, Python, C# etc., come with built-in functions for common sorting algorithms, it’s still important for us to have a basic understanding of how these algorithms work. This knowledge allows us to make informed decisions about which algorithm to use based on its space and time complexities, especially when working with large datasets as data scientists. So don’t underestimate the humble sorting function — they may not be the star of the show, but they are the unsung heroes of the tech industry.

In this article, we’ll dive into the bubble sort algorithm, examining its implementation in Python and JavaScript. We’ll also take a closer look at the intuition behind the algorithm and discuss considerations for time and space complexity. By the end of this article, you’ll have a solid understanding of when it is appropriate to use the bubble sort algorithm in your programs, as well as an overview of its space and time complexities.

Get a detailed overview of how hardware innovations are changing how data teams build analytics and machine learning applications in the free ebook, Hardware > Software > Process.

It is always more helpful to first grasp the concept when attempting to understand and later recall an algorithm. By familiarizing yourself with the idea before jumping into implementation, you will better retain the information for future use. Bubble sort is no exception.

To sort an array [2, 3, 4, 5, 1] in ascending order using the bubble sort algorithm, we start from the first element [2] and compare it with the second element [3]. If the first element is greater than the second, we swap them. We continue this process of comparing pairs of elements until we reach the end of the array. This way, the largest elements will be shifted to the end of the array, and the smallest elements will be shifted to the beginning of the array.

The name “bubble sort” refers to the way in which larger elements “bubble” to the top or the end of the array as they are repeatedly compared and swapped with smaller elements. By the end of the sorting process, the array will be fully sorted in ascending order.

The following is a list of unordered numbers that we will use bubble sort to organize:

Image by Author

The first step is to focus only on the first two numbers, which in this example are 5 and 9. You can visualize considering just the two elemtns 5 and 9 as shown in the image below:

Image by Author

Then, you must determine if the numbers inside the bubble are in order. If they aren’t in proper order, switch them around to make it right. Fortunately for us, they are already arranged in ascending order. 5 is less than 9, so it comes before 9. This means we don’t have anything left to do — we move our bubble one step further like this:

Image by Author

We conduct the same step in the next iteration of the array. However, this time 9 is greater than 1, but it’s also in front of it. So, to rectify that, the position of both elements is swapped. Here’s how the list looks now:

Image by Author

Now that the elements are swapped, the bubble progresses to successive pairs. And the steps repeat until the last pairs in the array have undergone a check to swap. The first run through the array will look like this:

Image by Author

The bubble sort algorithm is a simple yet effective way to sort an array of elements. It works by repeatedly iterating through the array and comparing pairs of elements, swapping their positions if they are out of order. This process is repeated until the entire array is sorted.

One thing to remember is that the number of passes required to sort an array is equal to the number of elements in the array. For example, a 6-element array will need to go through 6 passes in order to be fully sorted in ascending order.

However, it’s possible to make the bubble sort algorithm more efficient by limiting the number of operations or passes conducted on the array. This is because the last element of the array is always the maximum value, so there is no need to continue comparing all elements beyond this point in future passes through the array. We’ll see this optimization in action as we implement the bubble sort algorithm in Python and JavaScript in the sections below.

This section implements the bubble sort algorithm using the Python programming language. We will observe a naive implementation and a more efficient version of the bubble sort algorithm.

Initialize a Python array containing integer elements

unsortedData = [20, 33, 12, 53, 24, 65, 23, 4, 53, 1];

Define a function named ‘bubbleSort’ that accepts an array in its parameter named ‘data’. First, let’s attempt to pass through the array that swaps any elements that satisfy the condition that if the left element at a particular index is greater than an element to the right, we execute a swap operation between those two elements.

One thing to note is the assignment of the left element in any iteration to a temporary variable ‘tempValue’ and then assigning the right element to the temporary variable

def bubbleSort(data):

for i in range(0, len(data)):
if i+1 < len(data):
if data[i] > data[i+1]:
tempValue = data[i]
data[i] = data[i+1]
data[i+1] = tempValue

return data

The code snippet above, when called with an unsorted array passed as its arguments, will conduct the bubbleSort function pass once on the array. And in most cases, will not completely sort the array in ascending order.

sortedData = bubbleSort(unsortedData)
print(sortedData)
>>>[20, 12, 33, 24, 53, 23, 4, 53, 1, 65]

To fix this, we have to iterate through the array we want to sort as many times as there are combinations of pairs. Simply kept, the number of iterations to conduct is the length of the unsorted array squared (len(unsortedArrray)²). This is the naive implementation.

def bubbleSort(data):

# Iterate through the array enough times to consider every possible swap pairs
for _ in range(0, len(data)):
for i in range(0, len(data)):
if i+1 < len(data):
if data[i] > data[i+1]:
tempValue = data[i]
data[i] = data[i+1]
data[i+1] = tempValue

return data

Running the bubble sort function again with the unsorted array passed as an argument will result in an array sorted in ascending order provided as an output

sortedData = bubbleSort(unsortedData)
print(sortedData)
>>> [1, 4, 12, 20, 23, 24, 33, 53, 53, 65]

Optimized Version of Bubble Sort

While the naive version of the bubble sort algorithm does work, it has some unnecessary and redundant operations. In particular, it compares elements at the end of the array that are already the maximum values present in the array. This is because on each pass through the array, the bubble sort algorithm moves the maximum element values to the end of the array.

To optimize the bubble sort algorithm, we can reduce the number of swap operations required by keeping track of the portion of the array that we want to consider for comparison. We can do this by starting with the maximum length of the array and decrementing it by 1 after each pass, reducing the area of the array that the swap operation acts upon. This way, we can avoid comparing with the last elements of the array on each pass, which are already in their correct position.

By using this optimization, we can make the bubble sort algorithm more efficient and reduce the number of unnecessary operations it performs.

unsortedData = [20, 33, 12, 53, 24, 65, 23, 4, 53, 1];
end = len(unsortedData)

def bubbleSort(data):
global end
for _ in range(0, end):
for i in range(0, end):
if i+1 < end:
if data[i] > data[i+1]:
tempValue = data[i]
data[i] = data[i+1]
data[i+1] = tempValue
end = end - 1
return data

sortedData = bubbleSort(unsortedData)
print(sortedData)
>>> [1, 4, 12, 20, 23, 24, 33, 53, 53, 65]

Further refactoring could be conducted to ensure the code above is readable and efficient. Below is an implementation of the same algorithm in JavaScript, a programming language popular with data practitioners and software engineers.

const unsortedData = [20, 33, 12, 53, 24, 65, 23, 4, 53, 1];
let end = unsortedData.length - 1

const bubbleSort = (data) => {

for (let i = 0; i < end; i++) {
if (data[i] > data[i + 1]) {
const valueInRight = data[i]
data[i] = data[i+1]
data[i+1] = valueInRight
}
}
end--
}

for (let i = 0; i < unsortedData.length; i++) {
bubbleSort(unsortedData)
}

console.log(unsortedData)

Data scientists must understand the performance of a sorting algorithm and how much time/space it requires. This allows you to select the best sorting algorithm depending on your specific situation, as many options are available.

When bubble sort is used on an array already in ascending order, it requires only one pass through the entire array. This is considered the best-case scenario. In practice, though, this only occurs sometimes, and bubble sort usually necessitates n(n-1)/2 swaps or comparisons to achieve a sorted array.

The bubble sort algorithm’s average/worst time complexity is O(n²), as we have to pass through the array as many times as there are pairs in a provided array. Therefore, when time is a factor, there may be better options.

  • Time complexity Worst Case: O(n²)
  • Time complexity Average Case: O(n²)
  • Time complexity Best Case: O(n), the array is already sorted

In terms of space complexity, since we only swapped the elements with one another and never stored anything, we don’t need any extra space to run the algorithm. This is amazing because it means the space complexity comes out as constant, or O(1). This makes it an in-place algorithm that works by modifying the input directly.

The bubble sort algorithm may not be the most well-known or highly-regarded sorting algorithm, but as we’ve seen, it’s not a terrible option either. With a time complexity of O(n²) and a space complexity of O(1), it’s a simple algorithm that is easy for beginners to understand. However, its slow speed may make it less practical for certain applications.

Despite its limitations, the bubble sort algorithm can be a useful starting point for learning about sorting algorithms and data structures. It’s a good way to get a basic understanding of how these algorithms work, and can help you build a foundation for learning more complex algorithms later on.

That being said, the bubble sort algorithm may not be the best choice for time-sensitive material, as its slow speed can be prohibitive. However, if you’re willing to sacrifice some space for time, it may work well for you. Ultimately, the choice of sorting algorithm will depend on your specific needs and goals. By learning about the bubble sort algorithm, you can make more informed decisions about which algorithm is best for your needs.

Bubble sort is a sorting algorithm that uses comparison methods to sort an array. The algorithm compares pairs of elements in an array and swaps them if the left pair(position) is greater than the right pair(position+1). This process is repeated until the entire array is sorted.

  • How many passes does Bubble Sort require?

Bubble Sort requires n(n-1)/2 passes through all elements in order for the final array sorted in ascending order.

  • What is the worst time complexity of Bubble Sort?

The worst time complexity of Bubble Sort is O(n2).

  • What is the worst time complexity of Bubble Sort?

The best time complexity of Bubble Sort is O(n), and this occurs when the array is already sorted.

  • What is the space complexity of Bubble Sort?

Bubble sort has an O(1) space complexity, as it works in-place by modifying the input directly.

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – admin@technoblender.com. The content will be deleted within 24 hours.
AlakeAlgorithmbubbleDataexplainedGuideJanlatest newsRichmondScientistsSortTech NewsTechnology
Comments (0)
Add Comment