Why do you hate bubble sort so?
Why is it called bubble sort when it's not able to sort bubbles.
>>53285446
because you play video games instead of learning a useful science that can bring insight into your life, or a trade that can yield monetary gain.
O(n^2) now fuck off
>>53285431
That's not bubble sort.
People hate bubble sort because it's way too slow in the vast majority of cases, and there are many better algorithms for performing the same task.
>>53285476
But it's O(kn) if only k elements are out of place or the elements are at most k away from their correct location.
>>53285500
bidirectional bubble sort
>>53285476
Hows does it feel to know youll never give the big O to a woman?
>>53285510
Write a bubblesort in c++, try and sort an array of 10^6 random integers. Come back tomorrow when it finishes and tell me you love bubblesort.
I just use bogosort with an harry potter luck potion.
>instant sort
>>53285595
The luck potion might just convince you to write a better sort.
>not sleepsort
sasuga anon
>>53285474
>monetary gain.
only purpose is to upgrade bst and buy vidya
>>53285476
so is quicksort
>>53285431
>wanting to swap
Are you actually retarded? All sort algorithms avoid that paradigm under all costs. Merge sort and heapsorts are magnitudes more stable and far faster.
>>53285995
That's a worst case complexity, avg case complexity is O(nlogn) and avoids write overhead on external arrays like merge sort, and is far more conservative on swapping than bubble/insertion/selection.
kill yourself you FUCKING retard
>>53285547#include <algorithm>
#include <iostream>
#include <iterator>
#include <array>
#include <random>
template <typename RandomAccessIterator>
void bubble_sort(RandomAccessIterator begin, RandomAccessIterator end) {
while (begin < end-- ) {
auto new_end=begin;
auto new_begin=end;
for (auto i = begin; i != end; ++i) {
if (*(i + 1) < *i) {
std::iter_swap(i, i + 1);
new_end=i+1;
}
}
end=new_end;
for (auto i = end - 1; i > begin; --i) {
if (*i < *(i - 1)) {
std::iter_swap(i, i - 1);
new_begin=i-1;
}
}
begin=new_begin;
++begin;
}
}
int main() {
std::array<int, 1000000> a;
std::random_device rd;
std::mt19937_64 gen(rd());
std::uniform_int_distribution<int> dis;
for(auto i = std::begin(a); i!=std::end(a); i++) *i=dis(gen);
bubble_sort(std::begin(a), std::end(a));
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nDone!\n";
}
>>53285510
Normal bubble sort:
Best case: O(n^2)
Average case: O(n^2)
Worst case: O(n^2)
Improved bubble sort (Checks if any swaps were made)
Best case: O(n)
Average case: O(n^2)
Worst case: O(n^2)
because magnetic drums for ram are no longer 'cool'
>>53287335
>CS major can only memorize what their textbooks say
This is why cs is a meme, none of you actually learn anything.
>>53287530
I'll O of n square you're mom :)
>>53287530
Oh the irony.
>>53287530
You couldn't crack basic real analysis so you became the fag that shitpost on /sci/.
>>53287530
Projection much? Everything he said was correct.
>>53285431
>>53285644
What is the big O of sleep sort?
>>53288436
O(n*max{array})
>>53288436
Surprisingly enough, sleepsort sports O(n) complexity even in the very worst case! Ordinary sorting algorithms are only concerned with the spatial layout of their sequences, sleep sort disregards the notion of space completely and instead fully utilizes the elusive properties of time, very much like the Fourier transformation. Unfortunately we live in the time domain too, so although noteworthy and novel, it can't be put to practical use unless we figure out how to hoist ourselves onto a hyperplane encompassing spacetime as we understand it today but this is pushing the limits of physics really.
>>53285431
This satisfies my autism so much
>>53285476
This
>>53285431
>Why do you hate bubble sort so?
I don't. I actually think it sounds rather awesome.
https://youtu.be/kPRA0W1kECg
>>53288436
>What is the big O of sleep sort?
Depends on the implicit thread scheduling algorithm.
It terms of computational workload it's probably going to be equivalent to some kind of O(n) integer sort on typical platforms.
>>53288436
this should be the question right after fizzbizz
>>53289924
>bogo sort
clearly the best sounding sorting algorithm
>>53290042
Why?
>>53288436
why not comb sort?
>>53291320
new here?
>>53285446
define a total order on your bubbles and sort them with bubble sort
>>53286206
>the merge sort must use auxiliary storage because my CS101 class didn't teach me how to implement it right meme
>>53291545
Nah, just an excuse to shitpost with my /g/ filenames. I don't get to do it often.
>>53285595
Pleb. I use intelligent design sort. The arrays fed into the algorithm are sorted to begin with.
>>53285431
There are shorter AND faster algorithms. Like, simultaneously. Insertion sort for example. The main issue of bubble sort is huge amount of unnecessary writes.
>>53285431
Botnet
>>53293660
Stop calling it a botnet
>>53285431
I think it could be of use for more synchronizity
>>53293660
No that's quicksort
>>53291590
well, implement it right