JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Re: Why do i need to study different sorting of algorithms? (response to post by rrpai) | Reply
Well, the selection sort method is O(n^2), using cycles, the process of following the cycles themselves is probably amortized O(n), but that's not important, since in order to do that, you still have to sort the data in the first place, which will take at least O(nlogn) time.
Re: Why do i need to study different sorting of algorithms? (response to post by Kawigi) | Reply
Couldnt we calculate it as also n - <number of cycles in input> ?

( i am not sure about the complexity of this approach though - anyone ?
I think amortized analysis is required (?) and i am not familiar with that )
Re: Why do i need to study different sorting of algorithms? (response to post by eleusive) | Reply
prob you are telling is "HowUnsorted" i think
Re: Why do i need to study different sorting of algorithms? (response to post by mafoko) | Reply
In my opinion, the main reason why different sorting algorithms should be taught is the following one:

Different sorting algorithms introduce different approaches to the design of effective algorithms:
- MergeSort is one of the simplest examples of the divide&conquer paradigm
- HeapSort introduces the heap, a fundamental data structure
- QuickSort can be easily generalized e.g. to find the median of a sequence

On simple sorting algorithms a good teacher can explain lots and lots of concepts. IMHO this is why sorting algorithms are considered fundamental to algorithm design.
Re: Why do i need to study different sorting of algorithms? (response to post by eleusive) | Reply
I think I remember a div2 hard that you had to find the minimum number of swaps to sort something, which is a selection sort :-)
Re: Why do i need to study different sorting of algorithms? (response to post by mafoko) | Reply
I remember a while back there was a div1 hard that was solved a modified merge-sort algorithm, and it wasn't a "sorting" problem :) I think the problem was to find all pairs of values in a sequence that were out of order, and the sequence could be up to like 1,000,000 values long.
Re: Why do i need to study different sorting of algorithms? (response to post by timmac) | Reply
Hi thanks for your responses.

I still can't find a solid incentive with theoritical value from your posts. Doesn't justify why universities and governments are hiring mathematicians all around the world; hiring them just to entertain themselves with interesting problems is not reason enough, IMHO.

I need technical reasons for the emphasis in areas like sorting. Read some while ago that string manupulating algorithms are more general, which could justify why sorting is highly regarded in research. Somewhere I heard sorting is a fundamental to algorithm design just like in calculus the "fundamental theorem of calculus" is. How so?

I will like to know what constitutes a fundamental problem worthy of study?

[edit: typo]
Re: Why do i need to study different sorting of algorithms? (response to post by mafoko) | Reply
To add my own few thoughts on this, I'd say the reason to study sorting algorithms is because it's a good real world example of the importance of algorithms. Even though, usually, the algorithmic inner workings go unnoticed, of course.

That in mind though, because it's such a common situation, and so much attention has been given to it over the years, there are a lot of different algorithms out there, and the differences in performance can be pretty easily approached and discussed. Things like general case, best case, and worst case... expected performance vs. guaranteed performance. There's a lot to be said, even well beyond the scope of what I could get into in the article.
Re: Why do i need to study different sorting of algorithms? (response to post by mafoko) | Reply
As far as I'm concerned, the answer to both the questions is simply "because they are interesting".

Of course, it's possible that there really is some real-life use to them, but I think that's not why most CS/Maths people try solving them.
Re: Why do i need to study different sorting of algorithms? (response to post by mafoko) | Reply
I am waiting to hear what experienced coders will say about this one.

Why did you study many sorting algorithm when you could do well with one(well, at least for most purposes).

The question is asking for a motivation. A similar question to that one is why will one try to solve cs/math problems(some of which are highly distant from reality) in the first place?, well, I got an fuzzy answer for that one.
Why do i need to study different sorting of algorithms? | Reply
I was hoping the article will address this question. Finding which sorting algorithm is good for what type of data can be done in a catalog fashion: list an agorithm against an input sizes/type/etc.

What i was hoping to hear was that when learning sorting/searching algorithms, it is esential to learn the internals most because the sorting algorithms have properties beyond sorting alone. Thus in a particular problem one may be interested in how some sorting-algorithm-internal-variable changes for example, and that wont be got by calling a sort() routine. We should not be interested in mere sorting alone but in the properties of the variable involved. This sounds almost like the goal of doing pure mathematics.Ever wondered why someone may be concerned with the distribution of prime numbers? Distribution of primes is not the goal they are after.They are interested in the system of logically related theorems that pop out while trying to solve the problem.I guess the study of sorting algorithms has the same goal besides mere sorting.
RSS