#bubble sort

[notsogreeeen]

Was doing some idle thinking while at work

"wow, this day is pretty good" I thought, enjoying a particularly average day. "This sky... I should try and sort pixels through a shader!"

When I got home, I did exactly that.

It's honestly quite simple, I'll tell you the steps I took:

I made a horizontal Margolus neighborhood, to sample "sets" of two pixels

I then compared the two pixels, and applied basic bubble sort logic to it

I profited (I wish lol)

Here's some pictures of finished sorts!

And as always, the link:

Shadertoy

[chaipluscode]

Bubble Sort

**DISCLAIMER: This code is in C++, but the logic applies to other languages**

1) What is bubble sort?

Bubble sort is a sorting algorithm that checks adjacent numbers and swaps them if the number being checked is larger than the number ahead of it. The numbers are ordered from the bottom (end) of the list to the top (beginning). Kinda reminds me of the way bubbles rise to the surface of water *gasp!*

Visual Example:

2) An example problem:

Sort the numbers in the array [23, 123, 234, 54, 44, 2, 1432, 123, 8, 0].

Create a bubble sorting algorithm to order the numbers from least to greatest.

3) How I attempted to solve it:

I knew I needed to make a for-loop to iterate through the array.

I knew I also needed an if-statement to check if the indexed number was larger than the indexed number adjacent to the right of it.

My code logic* looked like this:

4) What happened?

This is what I got: [23, 123, 54, 44, 2, 234, 123, 8, 0, 1432, ]

So it seems like 1432 is in the correct position (based on the definition of bubble sort), but everything else seems to be off. I couldn’t figure out what was wrong.

5) What I ended up realizing:

After writing and rewriting the list and solving the sorting by hand 100 times, I realized I hadn’t even been following the structure of my own logic.

Once the if statement is complete, the loop iterates to the next index in the array. Therefore the number at index 0 of the array will always stay at the position. Hmm, if only there was a way to reset the loop to index 0 and run it again and again until the list was sorted................

6) THE FIX!!

There is! Another loop! I created an outer for-loop. The code now looks like this:

(I took this screenshot w/ more white space on the right so it looks better. The first screenshot is really in your face. Don’t worry, I know.)

I printed all the numbers returned after every iteration. This is the result:

[23, 123, 54, 44, 2, 234, 123, 8, 0, 1432]

[23, 54, 44, 2, 123, 123, 8, 0, 234, 1432]

[23, 44, 2, 54, 123, 8, 0, 123, 234, 1432]

[23, 2, 44, 54, 8, 0, 123, 123, 234, 1432]

[2, 23, 44, 8, 0, 54, 123, 123, 234, 1432]

[2, 23, 8, 0, 44, 54, 123, 123, 234, 1432]

[2, 8, 0, 23, 44, 54, 123, 123, 234, 1432]

[2, 0, 8, 23, 44, 54, 123, 123, 234, 1432]

[0, 2, 8, 23, 44, 54, 123, 123, 234, 1432]

(I took out the end comma, added brackets, and numerically listed them to make it easy for y’all to read so don’t @ me. :D )

Hope this helped! Thanks for reading :)

7) Summary and run-time:

Iterate through the array (inner for-loop).

Check to see if the current number is greater than the one on its right (if-statement inside inner for-loop).

Restart the for-loop over and over again until the list is sorted (outer for-loop).

Run times:

Worst Case: O(n^2)

Best Case: O(n)

Average Case: O(n^2)

*I wrote this code, but this isn’t the problem I was assigned. I wrote this code replaying my thought process in figuring out the solution. That is why this is an example problem.

*Also, I make lots of mistakes. There may very well be mistakes in my code even though it produces the correct output. Kindly correct me so misinformation isn’t spread. Thanks! :)

------------------------------------ EDIT -------------------------------------------

This optimization for the bubble sort was provided by https://purple-slippers.tumblr.com/

“There are no mistakes in your code that I’ve noticed, but it could be optimized.

Each iteration on the inner loop (the one with the ‘i’ variable) goes through the whole array. The outer loop makes it go through the whole array multiple times. There’s no need to check the whole array every time.

Why? The largest number ALWAYS ends up at the end after first iteration. The second largest ends up before the largest one after the first iteration. It’s how bubble sorting works. The biggest ones rise to the end of the array.

Therefore, it is not necessary to check the whole array 9 times. After ‘x’ iteration you’ll have ‘x’ largest numbers on the end of the array in the correct order. 1st iteration: largest number on end. 2nd iteration: 2 largest numbers on end in correct order. 3rd iteration: 3 largest numbers on end in correct order.

The outer loop could be used to skip these last, sorted out of sure places so it doesn’t make unnecessary comparisons.

Don’t want to take away the pleasure for solving it from you if you want to, but the answer is in the tag. :^)

Source:

chaipluscode

#oops wrong blog

#the answer ->

#for (i=0; i<10-j; i++)

#please dont take it like critique

#i just think its worth knowing

#your code and explanation are very good and understandable”

---------------------------------------------------------------------------------------

[the-maths-blog]

My friend Tom sent me this and I found it very interesting. Lovely explanation of sorting (from Decision maths) like Bubble sort. The final best solution is something I haven't really seen so worth a watch! Enjoy 😊

[magicjudge]

I heard that being able to Scry 1 'infinitely' lets you cut your deck to a position of your choice and Scry 2+ infinitely lets you stack your deck as you please (though, of course, you have to do it in a timely fashion). Is this correct? I saw something online about it but trying to confirm.

Unlimited “scry 1″ effects lets you cut your deck to the card of your choice, but not otherwise reorder it. To do this, you go through your deck fully once to see the order, then go through again enough times to get to where you want it to be cut to.

Unlimited “scry 2″ (or scry N, where N>1) effects allow you to order your deck in the order of your choice. To do this, you’re doing a bubble sort of your deck, scrying until you get to the desired top card, then keeping it on top and cutting to the desired next card as in Scry 1. Then you put those two cards on the bottom of your deck and find the card you want 3rd, and keep it on top of the deck until it’s under card #2, etc.

You can shortcut this so that it doesn’t take thousands of iterations, of course. If you’re going to do this at a tournament, explain it to the judge before the event so that they’ll be aware of what you’re doing.

[coding-quark]

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the array is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list (front/end, depending on direction) with each iteration. (In each iteration, the largest element goes to the last position).

Steps of Bubble Sort:

Start at the beginning of the list.

Compare the first two elements.

If the first is greater than the second, swap them.

Move to the next pair (second and third), and repeat the comparison and swap if needed.

Continue this way through to the end of the list. This completes one pass; after each pass, the largest element is placed at the end.

Repeat the process for the rest of the list, now ignoring the last sorted elements.

Continue until no swaps are needed (the list is sorted).

Example

Unsorted List: [5, 3, 8, 4, 2]

Let's sort in ascending order:

First Pass:

Compare 5 and 3 → swap → [3, 5, 8, 4, 2]

Compare 5 and 8 → no swap

Compare 8 and 4 → swap → [3, 5, 4, 8, 2]

Compare 8 and 2 → swap → [3, 5, 4, 2, 8]

Now, 8 moved to the end.

Second Pass:

Compare 3 and 5 → no swap

Compare 5 and 4 → swap → [3, 4, 5, 2, 8]

Compare 5 and 2 → swap → [3, 4, 2, 5, 8]

(Last element already sorted.)

Third Pass:

Compare 3 and 4 → no swap

Compare 4 and 2 → swap → [3, 2, 4, 5, 8]

Compare 4 and 5 → no swap

Fourth Pass:

Compare 3 and 2 → swap → [2, 3, 4, 5, 8]

Compare 3 and 4 → no swap

Now the list is sorted!

Key Points:

Time Complexity: O(n²) in worst/average case.

Simple, but inefficient for large datasets.

Stable sort (does not change the order of equal elements).

Works in-place (does not require extra memory).

Summary: Bubble Sort keeps comparing and swapping adjacent elements until the whole list is sorted, making it easy to implement but not very efficient.

[faysalahmed]

Bubble Sort In Java

Note that, Bubble Sort is not considered an efficient sorting algorithm in terms of performance, especially for large datasets. Its performance characteristics make it one of the least efficient sorting algorithms when compared to other commonly used sorting algorithms like Quick Sort, Merge Sort, and Heap Sort.

The key performance characteristics of Bubble Sort are as follows:

Time Complexity: The worst-case time complexity of Bubble Sort is O(n^2), where "n" is the number of elements in the list. This means that as the size of the input list grows, the number of comparisons and swaps increases quadratically. In the worst case, Bubble Sort needs to perform (n-1) passes, each requiring (n-1) comparisons, making it highly inefficient for large datasets.

Best-Case Time Complexity: The best-case time complexity occurs when the input list is already sorted. In this scenario, Bubble Sort still needs to pass through the list to determine that no swaps are needed, resulting in a best-case time complexity of O(n).

Average-Case Time Complexity: The average-case time complexity of Bubble Sort is also O(n^2). This is because it makes roughly the same number of comparisons and swaps as in the worst-case scenario for random or partially sorted data.

Space Complexity: Bubble Sort is an in-place sorting algorithm, meaning it doesn't require additional memory allocation for sorting. Its space complexity is O(1), indicating that it uses a constant amount of memory regardless of the input size.

[varunrajkalse]

6 Algorithms Every Developer Should Know

6 Algorithms Every Developer Should Know As a developer, it is essential to understand algorithms to create efficient and scalable software applications. Algorithms are sets of instructions that perform a specific task, such as sorting data or searching for information. By learning about these six essential algorithms, you can improve your coding skills and create better applications. By…

View On WordPress

[bellpolh]

Bubble sort

#Bubble sort code#

#Bubble sort code#

Currently, our code iterates through the entire array each time. If you look back at our array visualization, the blue values in the array do not need to be iterated through because we have already sorted them. That’s it! We have built our bubble sort function! But…we can make it slightly better. Our function then returns the sorted array. If we have performed a swap, we know that our array was not sorted so we set our sorted flag to False: def bubbleSort(array): sorted = False while not sorted: sorted = True for i in range(len(array) - 1): if array > array: array, array = array, array sorted = False return arrayįinally, once our array is completely sorted, our flag will be true and we exit the while loop. Remember, we were checking if our current value is greater than the value to its right and swapping if that is the case. The reason is that we can’t look to the right of the last value in the array (there’s nothing there). Note that we are iterating until len(array) - 1. We then start our for loop to iterate through our array: def bubbleSort(array): sorted = False while not sorted: sorted = True for i in range(len(array) - 1): We are going to start our while loop and tentatively set our sorted flag to True. So while our array is not sorted, we need to sort it. Initially, we assume our input array is not sorted so we have a flag sorted set to False. We define our bubbleSort function and it takes in an array of integers. We are not allocating any extra memory to perform our sort so our space complexity is O(1). We still need to iterate through that array once to check that its sorted, our best case time complexity is O(n).Īs mentioned earlier, bubble sort performs its swaps in-place. In the best case, we’re given a sorted array to sort. More specifically, Bubble sort has a time complexity of O(n²) in the worst case. You might be thinking - that was extremely tedious. This means we are done! Time and Space Complexity 2 cannot be swapped with anything so our swaps are zero for this round.