What are the most F.A.Q on this forum? (part 2)

[Duthomhas]

Thanks for the answer. However, that isn't what I meant.

Believe it or not, I could be a copy editor. Both are technically correct. (I just tend to personally use what I was taught in grade school.)

The question is which I should use here on the forum. I am really leaning toward the single L right now...

[chrisname]

Most people outside of England who speak English speak American English for some stupid reason, so you should probably use the American spelling, as much as I disdain American misspellings of English words.

[ResidentBiscuit]

I'd go with single L's. I think it's more common. Though I don't think it really matters.

[ne555]

¿where do you get your statistics, chrisname?

travelling 6 - 2 traveling http://en.wikipedia.org/wiki/Wikipedia:Manual_of_Style/Spelling
[edit]¿what do the colours mean?[/edit]

Also, firefox highlight traveling as misspelled.

[Duthomhas]

The Counting Sort is done. Please review.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/#counting-sort

@ne555
Firefox misspells a lot of things. (As do many browsers, text-box dictionaries being what they are.) Alas.

[edit] Also, even though I can copy edit, it does not mean that my first pass writing a thing is copy proofed. Please look for errors.

[chrisname]

@ne555,
Hm, I'd always thought that people in other countries learned American English instead of English. Maybe I was wrong.

[Duthomhas]

Heapsort is done.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/heapsort/

Please remark on the gif animations, also -- particularly on the frame timings. My wife wants you to give me grief on the font choice, particularly on the forth frame of the second animation. Is it readable to you? I also wonder if I should increase the time on the last frame to five seconds or so instead of three.

Any advantages or disadvantages I have missed?

Thanks again!

[Duthomhas]

Also, insertion sort is done.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/

[ne555]

About heapsort
_ The idea is not clear. I think you should start with something like `it's an improvement of selection sort, using an structure that will determine the max/min element faster'

_ "a parent node’s value must be greater than or equal to each child’s value."
Corollary: the root is the greatest of all the nodes.

_

the parent’s value must not be (...) of each child’s value.

Missing adjective.
(second paragraph, The Heap Property)

_ The `Basic Algorithm'
Taking into account the corollary is easier.
__The root has the greatest element. So remove it from the heap and put it in the last place of your `sorted array'.
__Heapify.
__Repeat till the heap is empty.

[Duthomhas]

Wow, thank you for the excellent commentary!

1 - Hmm... good point on the introduction. I'll work on coming up with something more substantive.

2 - Will do.

3 - I don't think I like the way I have that all worded anyway right now... I'll have to rethink it some.

4 - Hmm. I think I understand what you are suggesting, and while more simply written it is a much more expensive way to sort.

However, I agree that it might be a bit wordy... I'll give it another look later.

[Duthomhas]

OK, I'm still not sure I like the new basic algorithm description, but let me know what y'all think. I'm going to bed.

[Duthomhas]

Alright! I think I am done (or nearly so) with Mergesort. Yay!
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/mergesort/

It was a very long article. To any experts on anything to do with mergesort: please look through and tell me if I made any mistakes.

Thanks again!

[edit]
Oh, yeah. Should I mention that the STL has merge() and merge_inplace() functions?

[Duthomhas]

Also, I am wondering if I should add any pointers to getting ICU and Boost up and running on Windows using MinGW? It isn't very difficult, actually, but only if you are very familiar with configure scripts, makefiles, and hunting down errors in logs.

(And yes, this relates to the FAQ. If you want to be able to convert case, you should have ICU installed and Boost Locale compiled and installed atop that. The other options still apply, but this is the best -- and what I will recommend.)


PS. Please look at mergesort.

[coder777]

Duoas wrote:

It was a very long article.

Yes, and sorry, that's my main critique. It should have been shorter esp. for a F.A.Q. The reader is simply clobbered with words...

You should leave out the padding words. For example the first sentence:

Mergesort is a very flexible, simple algorithm with a whole lot of practical applications.

-> Mergesort is a flexible algorithm with practical applications.
simple? This seems a contradiciton: Beginners may be confused by it
practical applications? I'd expect examples or at least a link

The first thing is the table without commentary. I think it needs an introduction. And please, not everyone is familiar with the Big O notation. A short explanation or link would be fine.

The algorithm first breaks the input into smaller pieces, which at some point are either: (1) already sorted or (2) sorted by some other algorithm, and then merges those smaller sequences back together.

This confuse me. How is it done? Isn't (1) and (2) the same? Why the numbers? Later:

Mergesort has so many variations that it would be too much to even mention them all here.

so many variations...but they're all doing the same?
-> Not all variations [of Mergesort] are mentioned here.

I'd suggest to go through the text and discard unnecessary words and sentences. The reader would be grateful

Also, I am wondering if I should add any pointers to getting ICU and Boost up and running on Windows using MinGW?

That has nothing to do with mergesort? But yes that would be good in a F.A.Q