[Ex094]

The title of the thread is a bit misleading. According to the present title a user will guess and it will appear to him that He is gonna get a theoretical explanation of sorting and various sort algorithms and general techniques whereas this thread mainly focuses on Bubble sort. So the title imho should be "Introduction to Sorting : Bubble Sort" as this will tell the user that he is going to get details on bubble sort and general sorting theory. I hope I made myself clear.

Will be adding more details to this article as I said previously

[Ex094]

@Deque If I improve my code then how would I figure out whether it's optimized or not, I'm guessing the time complexity or something, Please do tell me about this

[Ex094]

@Deque If I improve my code then how would I figure out whether it's optimized or not, I'm guessing the time complexity or something, Please do tell me about this

[lady_godiva]

I don't think the time complexity is that important. Most people don't understand how to use it correctly and think they should always take the algorithm with the best time complexity. So it doesn't matter to me if you add that.

That is true, but i also believe that this forum and this post should be an occasion to learn about it and understand it better as understanding how things work and reasons behind them should be one of the main purpose here.

[lady_godiva]

I don't think the time complexity is that important. Most people don't understand how to use it correctly and think they should always take the algorithm with the best time complexity. So it doesn't matter to me if you add that.

That is true, but i also believe that this forum and this post should be an occasion to learn about it and understand it better as understanding how things work and reasons behind them should be one of the main purpose here.

[Psycho_Coder]

@Deque If I improve my code then how would I figure out whether it's optimized or not, I'm guessing the time complexity or something, Please do tell me about this

I think I have explained the time complexity of bubble sort in my earlier reply. However to find the complexity of any algorithm you need to know the Master Theorem.

[Psycho_Coder]

@Deque If I improve my code then how would I figure out whether it's optimized or not, I'm guessing the time complexity or something, Please do tell me about this

I think I have explained the time complexity of bubble sort in my earlier reply. However to find the complexity of any algorithm you need to know the Master Theorem.

[Deque]

That is true, but i also believe that this forum and this post should be an occasion to learn about it and understand it better as understanding how things work and reasons behind them should be one of the main purpose here.

You are right, but we need an entire tutorial to explain that. It would be out of topic for a tutorial about sorting algorithms to explain the whole concept.
I have it on my list to make one, but don't expect it soon. I have a huge todo-list.

@Deque If I improve my code then how would I figure out whether it's optimized or not, I'm guessing the time complexity or something, Please do tell me about this

I think I have explained the time complexity of bubble sort in my earlier reply. However to find the complexity of any algorithm you need to know the Master Theorem.

No, you didn't explain time complexity per se. You explained, why bubblesort is O(n²) and that is just an example. It doesn't really answer the question how to apply this in general or what time complexity actually is.

The Master Theorem only helps finding the time complexity for some recursive algorithms.
There is no single method to get the time complexity for every algorithm. In some cases you have to make mathematical proofs. This is not trivial.

@Deque If I improve my code then how would I figure out whether it's optimized or not, I'm guessing the time complexity or something, Please do tell me about this

The time complexity only tells you how much the time grows with growing input.
I.e. how much the sorting time grows if you increase the number of elements that are to be sorted.
A better time complexity does NOT mean that the algorithm is better or faster. Because constant time needed is ignored, it is often the case that algorithms with better time complexity have a huge constant overhead. Meaning, they don't grow that much with growing inputs, they are just slow with every input.

So in order to answer your question: You can always determine the efficiency of an algorithm based on sample input of a given size by testing (measuring the time needed). At least for the practical case (if you write a software) this is enough and the best you can do.
In sorting algorithms you can count the comparisons and swaps needed, which gives a relatively good measure too. If you change your algorithm so that less swaps and comparisons are done, you have probably made it better (this is the part that Psycho_Coder explained in detail with his post.) unless you introduced some functions that eat a lot of (constant) time.

Edit: I will publish a tutorial about performance measurement. It is an old paper I wrote two years ago.

[Deque]

That is true, but i also believe that this forum and this post should be an occasion to learn about it and understand it better as understanding how things work and reasons behind them should be one of the main purpose here.

You are right, but we need an entire tutorial to explain that. It would be out of topic for a tutorial about sorting algorithms to explain the whole concept.
I have it on my list to make one, but don't expect it soon. I have a huge todo-list.

@Deque If I improve my code then how would I figure out whether it's optimized or not, I'm guessing the time complexity or something, Please do tell me about this

I think I have explained the time complexity of bubble sort in my earlier reply. However to find the complexity of any algorithm you need to know the Master Theorem.

No, you didn't explain time complexity per se. You explained, why bubblesort is O(n²) and that is just an example. It doesn't really answer the question how to apply this in general or what time complexity actually is.

The Master Theorem only helps finding the time complexity for some recursive algorithms.
There is no single method to get the time complexity for every algorithm. In some cases you have to make mathematical proofs. This is not trivial.

@Deque If I improve my code then how would I figure out whether it's optimized or not, I'm guessing the time complexity or something, Please do tell me about this

The time complexity only tells you how much the time grows with growing input.
I.e. how much the sorting time grows if you increase the number of elements that are to be sorted.
A better time complexity does NOT mean that the algorithm is better or faster. Because constant time needed is ignored, it is often the case that algorithms with better time complexity have a huge constant overhead. Meaning, they don't grow that much with growing inputs, they are just slow with every input.

So in order to answer your question: You can always determine the efficiency of an algorithm based on sample input of a given size by testing (measuring the time needed). At least for the practical case (if you write a software) this is enough and the best you can do.
In sorting algorithms you can count the comparisons and swaps needed, which gives a relatively good measure too. If you change your algorithm so that less swaps and comparisons are done, you have probably made it better (this is the part that Psycho_Coder explained in detail with his post.) unless you introduced some functions that eat a lot of (constant) time.

Edit: I will publish a tutorial about performance measurement. It is an old paper I wrote two years ago.

[invisal]

@Ex094, I am surprised you choose "Bubble Sort" over "Selection Sort" as a sorting
introduction. "Selection Sort" algorithm makes more sense to human being than
"Bubble Sort"

I agree with @Deque that expressing the complexity in pure bigO is pretty broken.
It ignores constant that could make a big different for small data. A better
measurement should be expressed in term of number of comparison and number
of swap. A lot of people thinks that comparison operation is cheap, which is
a false assumption. Comparison can be expensive for some type of data.

Another performance measurement is locality of reference. It does not make
much different for small list, but it does make much different if the data is
exceeding the cache block-size.

Sorting also involves comparing 2 adjacent values

Not always true. Some sort algorithm does not even involve comparing
value of each element in the list.

Another improvement to this tutorial should be making the sorting
function more flexible by having extra parameter to pass
comparison function.

And as @Deque state, sort stability (it is how to handle when
there are two or more items with the same value) is also important.