Wikipedia:Reference desk/Archives/Computing/2020 March 8

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 8

Very quicksort

= Hi, this is not about any original research as I do rmb I have read about it on web, something year 2005 =

hi ,I think i was able to read about a variant of quicksort that got the worst time consuming of only 2*N*log(N) , by calculating the pivot (for lets first say an array of longint) by the formula pivot= int ((min+max)/2) where min and max are the minimum and maximum values of curent partition and the recursion ended when min=max, for the current one partition. I guess that it could be adapted for others data type than longint, with just a lil bit of extra care. I am saying all this bcz at some brief check on wiki, i got still O(N^2) worst time for qsort. thank You, hope i didnt cause too much bother about this . Yours respectfully, Florin Matei Florin747 (talk) 11:13, 8 March 2020 (UTC)

Quicksort pretty much always has a worst time of O(n^2), using clever pivot selection just makes actually hitting the worst time on real data sets much much much less likely. Picking the median of three (first, mid, and last item) will usually get nearly O(n*log(n)) time but it's entirely possible to run into (or deliberately create) a dataset that thwarts that (which is why it's frequently recommended to select the pivot randomly if security is a concern). 108.29.123.212 (talk) 14:19, 8 March 2020 (UTC)

Funnily enough I was thinking about this this morning. What the IP says above is pretty much spot on, barring some constraint on the data set. Perl changed the behaviour of its hashes for a variant of precisely the security issue mentioned. All the best: Rich Farmbrough (the apparently calm and reasonable) 21:27, 8 March 2020 (UTC).

Alrite, thank You for wasting Your time for processing my little nonsense, I wish to add that, probabily, the idea that i put above may look something like the variant for HHL implementations of the binary sort. I understand that there can be other reasons too, other than the optimizations. Thank You, very useful , in did. Yours respectfully, Florin747 (talk) 07:56, 9 March 2020 (UTC)

You can guarantee O(n log n) by choosing the actual median as the pivot, and you can find the median in O(n) time. See median of medians. 73.93.153.132 (talk) 11:01, 9 March 2020 (UTC)

Actually, standard Quicksort will always degenerate to $O(n^{2})$ for a sequence of identical values. You need a three-fold partition (<pivot, =pivot, >pivot) to avoid that. --Stephan Schulz (talk) 20:28, 13 March 2020 (UTC)

Thank You for reminding me that! For the moment, due to my not so good memory, I just wasnt able to get that into my memory. Thank You , once again, for Your patience and for Your welness that You are showing to me!

Florin747 (talk) 11:37, 9 March 2020 (UTC)

...Computing Sum(N)=1+2+3+...+N can be try without using formulas, by reducing Sum(2*N) to computing first Sum(1*N), wasting polynomial time. We could try that for Sum1(N)=1*1+2*2+3*3+...+N*N. The interesting point I would like to mention is that we might be able to compute Sum(N*N) by directly aplying Sum(N) for the Sum(N*N)=1+2+3+...+N*N, maybe for more complicated sums either. Sometimes these kinda ideas could be seen as some polynomizations like ideas that could work for EDU purposes. Again, I am not so sure what could go any wrong for these stuff of mine (too). Thank You! Florin747 (talk) 12:55, 9 March 2020 (UTC)

@Florin747: Calculating a pivot is not always that obvious – for example, what is a mean value between character strings "Chirp" and "Quack"...? (Consider foreign languages, where alphabetic order of diacritic letters is not necessarily reflected by their code point values.) Additionally, some algorithms require the pivot value to be placed at its final position as a side effect of the partitioning routine (see the description of Lomuto's algorithm in our Quicksort article and how it differs from the Hoare's one); then you need a delimiting value present in the array, so you can't devise one, but you need to choose it from the array. That last requirement is most important in the Dutch national flag problem problem – when you expect multiple duplicates of key values, you need to choose one of them (the more frequent, the better) to get the central partition as fat as possible. --CiaPan (talk) 15:02, 9 March 2020 (UTC)

Wow!!! this looks much too complicate for me. lets get back, please, to the point that You are saying "Jump!" and I say "How high, Sir!" . I got much more experience for that one topic, I guess... LOL

Anyway, if You are asking me, I would dare to say that I must agree with that hip-hop that are saying something like that :... saluting all schools, they neva were the way, just check out my books!

Anyway, kind respect from Romania , Florin747 (talk) 15:15, 9 March 2020 (UTC)

Alrite, I do apologise , just in case my stuff above here were any unappropriate to You. In case that You really like my ideas , I think that, IF You really wish that, then You may come with some offer on me, for me be treated of skitzophrenia some better place, I mean more expansive care, western stuff like that. In exchange , I may be able to work/create any better, in the field of the middle grade up to highschool level applied maths.

I am saying that bcz I feel like doing myself a favor and try that too. Thank You, whateva Your choice may be! Florin747 (talk) 07:56, 11 March 2020 (UTC)

...for the Dutch Flag Problem, in case that we wish to try stable sorting, what it came to me was something like a possible combination of sorting of a permutation, and some count sort idea, more as for some start possibilities ideas. we might try ,first, equal numbers for each set of same colour balls. Some ago I tried to formulate something like the Problematic of the Problemistics, basicaly if the problem to be solved is too easy then we can try to complicate it, make it any harder, and if the problem to be solved is too hard, make an easier variant of it.

...for some pivot for array of string items, in the common variant based on ASCII codes of characters, idk, for each byte of any rank, we can try the arithmetical mean (related of only two strings). For more than two strings we might focus on the most significant byte/character ASCII code.

Alrite I guess this is all I can do so far, I mention that I am better at some middle grade and highschool problems rather the ones more complicated than that. Thank You! Florin747 (talk) 12:47, 11 March 2020 (UTC)

Funny letters; what are they?

Facebook just served me an ad that began with the following text:

𝗛𝗲𝗹𝗽𝗶𝗻𝗴 𝗼𝘃𝗲𝗿 𝟭,𝟬𝟬𝟬,𝟬𝟬𝟬 𝗿𝗲𝗮𝗹𝗶𝘇𝗲 𝘁𝗵𝗲𝗶𝗿 𝗽𝗲𝗿𝘀𝗼𝗻𝗮𝗹 𝗵𝗼𝗽𝗲 𝗶𝗻 𝗝𝗲𝘀𝘂𝘀 𝗲𝘃𝗲𝗿𝘆 𝗦𝘂𝗻𝗱𝗮𝘆.

What are these characters? They stay bold no matter what I do; see 𝗵𝗼𝗽𝗲 versus 𝗵𝗼𝗽𝗲, for example. They're distinct from normal characters; if I go to 𝘀, for example, I end up at https://en.wikipedia.org/wiki/𝘀, which isn't the same as S or 𝗦. They're essentially normal letters; if I put one of them into Google, I get the same results as if I look for the lookalike normal letter. I know the percent encoding for 𝗦, gained by mousing over the link in this question; it's %F0%9D%97%A6, and if I tweak the last couple of characters, I can end up at the other 25 capitals or the 26 miniscules. Nyttend (talk) 22:25, 8 March 2020 (UTC)

I copy-pasted them in the "Characters" field at https://r12a.github.io/app-conversion/ and clicked "View in UniView". It says "1D5DB MATHEMATICAL SANS-SERIF BOLD CAPITAL H" and so on. See Mathematical Alphanumeric Symbols. PrimeHunter (talk) 22:56, 8 March 2020 (UTC)

A cheesy way to show the message in boldface without using html markup, resembling an IDN homograph attack. 73.93.153.132 (talk) 11:19, 9 March 2020 (UTC)

I think the important question here is, did it help you realize your personal hope in Jesus? Elizium23 (talk) 11:30, 9 March 2020 (UTC)

By the way, Gucharmap is a nice utility (I use it under MATE) for identifying weird Unicode characters by pasting them. 2601:640:108:A5F5:F823:7F80:84B2:C54D (talk) 04:19, 10 March 2020 (UTC)

I use a nifty Firefox plugin named, believe it or not, Identify Characters. —Tamfang (talk) 07:00, 11 March 2020 (UTC)

Malware/spam

Cleaning out my spam folder on Gmail I started to examine a spurious unsubscribe message. It appeared that clicking either yes or no would email about 30 people. This seemed pointless from the PoV of the sender, although I suppose its a multiplier you would have to trick over 1/30 of the recipients.

Any ideas how this was supposed to work? All the best: Rich Farmbrough (the apparently calm and reasonable) 23:15, 8 March 2020 (UTC).

Were the 30 recipients encoded in the spam message? Would all have received the same e-mail message? Was it identical to the spam message?  --Lambiam 15:12, 9 March 2020 (UTC)

How do you know that it would email 30 people? Do you mean that you got a message with 30 addresses in the To: field? 93.138.43.92 (talk) 20:22, 9 March 2020 (UTC)

Yikes, turn off javascript in emails. Turn it off everywhere if you can. 2601:640:108:A5F5:F823:7F80:84B2:C54D (talk) 05:38, 10 March 2020 (UTC)

Javascript is wholly unnecessary to create a link that emails someone. That's what the mailto: URI scheme is for. Elizium23 (talk) 23:17, 11 March 2020 (UTC)

Those links typically launch a mail client on your desktop. Also, without JS, the mailto url shows in the status line. JS allows the status line to be spoofed. 2601:648:8202:96B0:54D9:2ABB:1EDB:CEE3 (talk) 05:12, 12 March 2020 (UTC)

Doesn't Gmail block Javascript? In attachments, anyway. Elizium23 (talk) 05:21, 12 March 2020 (UTC)

Blocking .js attachments is not the same as blocking Javascript code in your email messages. The second is a much more dangerous thing because .js attachments need to be manually downloaded and started by the victim, while Javascript code can execute immediately when the email is opened. It's best to avoid using webmail and turn off Javascript in your email client. 93.136.43.47 (talk) 04:35, 13 March 2020 (UTC)

Couple things here. There is no way in Gmail settings to disable Javascript. That is why I am fairly confident that they block, or at least filter it, in message bodies. Gmail has a "basic HTML" version that should work without benefit of JavaScript. But if you decided to disable JavaScript in your browser, the default full-featured Gmail web client would malfunction. Elizium23 (talk) 06:09, 13 March 2020 (UTC)