+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: Coding (https://sinister.li/Forum-Coding--71)
+--- Thread: Introduction to Sorting and Sorting Algorithms (/Thread-Introduction-to-Sorting-and-Sorting-Algorithms)
RE: Introduction to Sorting and Sorting Algorithms - Deque - 08-23-2013
Quote: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.
I didn't say it is broken and I also don't believe it is. The problem imho is that people aren't able to interpret it correctly, because they don't understand what the time complexity actually says.
For the fun of it I once introduced in a forum a relatively unknown (because impractical) algorithm--I can't even remember what it was for--that had a very good worst case time complexity. But the c (constant time) of this one is so large, that no one really uses it.
One of the first answers to this was: "Oh, that's great, I will use this algorithm from now on."
RE: Introduction to Sorting and Sorting Algorithms - Deque - 08-23-2013
Quote: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.
I didn't say it is broken and I also don't believe it is. The problem imho is that people aren't able to interpret it correctly, because they don't understand what the time complexity actually says.
For the fun of it I once introduced in a forum a relatively unknown (because impractical) algorithm--I can't even remember what it was for--that had a very good worst case time complexity. But the c (constant time) of this one is so large, that no one really uses it.
One of the first answers to this was: "Oh, that's great, I will use this algorithm from now on."
RE: Introduction to Sorting and Sorting Algorithms - invisal - 08-23-2013
Quote:The problem imho is that people aren't able to interpret it correctly,
because they don't understand what the time complexity actually says.
I am not saying that the time complexity using the big O notation is useless. Just it
is broken as a mean to measure algorithm performance. Lets say that I want to
choose between "insertion sort" and "selection sort". The average complexity of both
algorithm are O(n^2). Without seeing how the algorithm works, it is hard
to make decision which one to choose to suit my current data.
RE: Introduction to Sorting and Sorting Algorithms - invisal - 08-23-2013
Quote:The problem imho is that people aren't able to interpret it correctly,
because they don't understand what the time complexity actually says.
I am not saying that the time complexity using the big O notation is useless. Just it
is broken as a mean to measure algorithm performance. Lets say that I want to
choose between "insertion sort" and "selection sort". The average complexity of both
algorithm are O(n^2). Without seeing how the algorithm works, it is hard
to make decision which one to choose to suit my current data.
RE: Introduction to Sorting and Sorting Algorithms - Ex094 - 08-24-2013
(08-23-2013, 03:05 PM)invisal Wrote: @Ex094, I am surprised you choose "Bubble Sort" over "Selection Sort" as a sortingI see Bubble sort makes more sense for Beginners to start understanding other Algorithms though will be adding other algorithms one by one
introduction. "Selection Sort" algorithm makes more sense to human being than
"Bubble Sort"
RE: Introduction to Sorting and Sorting Algorithms - Ex094 - 08-24-2013
(08-23-2013, 03:05 PM)invisal Wrote: @Ex094, I am surprised you choose "Bubble Sort" over "Selection Sort" as a sortingI see Bubble sort makes more sense for Beginners to start understanding other Algorithms though will be adding other algorithms one by one
introduction. "Selection Sort" algorithm makes more sense to human being than
"Bubble Sort"
RE: Introduction to Sorting and Sorting Algorithms - lady_godiva - 08-25-2013
@Deque if you need any help about making that tutorial about sorting agorithms or complexity, just let me know
RE: Introduction to Sorting and Sorting Algorithms - Psycho_Coder - 08-25-2013
(08-25-2013, 01:39 PM)lady_godiva Wrote: @Deque if you need any help about making that tutorial about sorting agorithms or complexity, just let me know
Well I think she is very knowledgeable in this field, she won't require much help other than time.
RE: Introduction to Sorting and Sorting Algorithms - invisal - 08-25-2013
(08-25-2013, 01:39 PM)lady_godiva Wrote: @Deque if you need any help about making that tutorial about sorting agorithms or complexity, just let me know
I can donate my article about "Introduction to Comparison Sort" if someone can reformat
it to post it in the forum. It is my unfinished work that I discontinue because I have no
time to continue writing that article now. If anyone would like to continue after me,
I am more than welcome.
http://invisal.com/doc/1-introduction-to-comparision-sort
RE: Introduction to Sorting and Sorting Algorithms - Psycho_Coder - 08-26-2013
(08-25-2013, 03:57 PM)invisal Wrote:(08-25-2013, 01:39 PM)lady_godiva Wrote: @Deque if you need any help about making that tutorial about sorting agorithms or complexity, just let me know
I can donate my article about "Introduction to Comparison Sort" if someone can reformat
it to post it in the forum. It is my unfinished work that I discontinue because I have no
time to continue writing that article now. If anyone would like to continue after me,
I am more than welcome.
http://invisal.com/doc/1-introduction-to-comparision-sort
I think you should post the tutorial here on HC as well as a tutorial for others too. It would be a great share.