13 ms·
Why does sorting in computer science mean ordering rather than categorizing?
- larrik 8y agoThis is great stuff, too bad it's on Twitter instead of a real website or platform.
- X6S1x6Okd1st 8y agoRegardless of if you like twitter or their practices they are a real website and platform.
- bcaa7f3a8bbc 8y agoI agree. I hate to post anything longer than random thoughts on Twitter, but this is an unfortunate consequence of the culture shift in past 10 years driven by the social media giants. Like it or not, Twitter is now the center of gravity of the entire Internet, and currently the most effective online platform to make posts with high visibility is Twitter... Other platforms like forums declined, even forums did nothing wrong by themselves, and they are in fact much more suitable for real discussion. But the culture is already changed, people got used to make random 20 words posts on their mobile phones instead of reading a long threads of discussion, microblog-like, social-media-like platforms would prevail in the shortterm future. The only thing we can do is to promote a OStatus-based, open, alternative social media implemented by GNU/Social, Mastodon, etc, to make the situation less harmful. I'm happy that we can still have real discussion on Hacker News.
- TangoTrotFox 8y agoAs of the end of 2016, 24% of active internet users in America use Twitter. According to Twitter, they have 335 million active users, which is declining - thanks largely to declines in America [2]. One can only speculate on the percent of those that are bots. By contrast Facebook still has north of 2billion monthly active users. Both sites, on top of bots, of course also have an incentive to count as loosely as possible within the realm of plausible deniability. Ultimately, if Twitter is the center of gravity of the internet, then Pluto must be the center of gravity of our solar system. The only reason I mention this is because I find people make the sort of arguments like you're making to convince themselves that they're not just wasting time on these platforms. I don't think there's been any shift in culture. There probably has been a shift in demographics as the internet has become much more common among less technically oriented individuals, but I think the real player is simply that these platforms are designed to be addictive, and they are. People keep using them even when they want to quit or do not find the time spent on them beneficial. Dopamine's a hell of a drug. [1] - http://www.pewinternet.org/2016/11/11/social-media-update-2016/ http://www.pewinternet.org/2016/11/11/social-media-update-20... [2] - https://venturebeat.com/2018/07/27/twitter-loses-1-million-monthly-users-in-q2-2018-revenue-grows-to-711-million/ https://venturebeat.com/2018/07/27/twitter-loses-1-million-m...
- saltcured 8y agoI think there are sub-populations who think Twitter encompasses all, particularly in the pop culture and journalism crossroads. I had a strange professional experience encountering media school academics about 5-7 years ago who were all so gung-ho about it. This was when the "firehose" could be acquired with a budget plausible within a grant-funded research group, and they seemed to imagine themselves having total information awareness like they had joined the five eyes. They spoke as if they were on the cusp of a future where this tool replaced all other forms of polling and data-gathering for social science, with no apparent concern for the incompleteness of this perspective nor of the ethical quandaries if it really were that powerful.
- marssaxman 8y agoTwitter is now the center of gravity of the entire Internet Journalists and celebrities certainly seem to think so, and I'm glad they do, because I can easily avoid them by simply ignoring Twitter.
- mirimir 8y agoSame here. Maybe if there were decent tools for aggregating and filtering. But there aren't.
- PhasmaFelis 8y agoIt's pretty clear from context that by "a real platform" OP means "a platform suited to this sort of work" (long-form writing).
- est 8y agoas if my wordpress / static pages is not a real website?
- icc97 8y agoThe parent is only replying to this comment: > This is great stuff, too bad it's on Twitter instead of a real website or platform.
- asaph 8y agoIt's a "tweetstorm". https://www.merriam-webster.com/words-at-play/tweeting-up-a-tweetstorm https://www.merriam-webster.com/words-at-play/tweeting-up-a-...
- hk__2 8y ago“tweetstorm” is somewhat pejorative; here it’s just a “thread”.
- csours 8y agohttps://threadreaderapp.com/thread/1036704758696960001.html https://threadreaderapp.com/thread/1036704758696960001.html
- icc97 8y agoThat threadreadapp pollutes the thread with pointless replies
- deleted 8y ago[deleted]
- johannes1234321 8y agoThis is quite interesting. From my German background I associate "sortieren" with alphabetic/numerical /calendaring order. Whereas "ordnen" ist more like "putting in order"/"categorize" or "sorting". So maybe it's as easy as blaming the Germans ;-)
- jdmichal 8y agoExcept that -ieren ending on sortieren is indicative of an import from Romantic languages, typically French or Italian. [0] So it's likely that the English and German word both share French sortir as an imported root. Etymonline lists it as 14th century English, so too late to have inherited it through German. [1] [0] https://en.wiktionary.org/wiki/-ieren#German https://en.wiktionary.org/wiki/-ieren#German [1] https://www.etymonline.com/word/sort#etymonline_v_24299 https://www.etymonline.com/word/sort#etymonline_v_24299
- anticensor 8y ago> Except that -ieren ending on sortieren is indicative of an import from Romantic languages, typically French or Italian. Except that it is Romance or Romanic languages, not Romantic languages.
- em-bee 8y agoalthough french and italian are seen as romantic by some :-)
- mattkrause 8y agoI think that’s a false cognate: in French, sortir means to leave or go/take out. Trier is means to sort or classify.
- jdmichal 8y agoThe meaning you listed seems to correlate across many Romance languages and caused me to start looking deeper. I found an Anglo-Norman dictionary [0], which lists meanings very much in line with those listed at Etymonline [1]. I can't explain the difference... The listed Latin root seems to allow the noted Anglo-Norman and later English meaning [2]. But modern Romance languages seem to have standardized a meaning similar to what you mention. There does seem to be widely-attested noun forms like French sorte, Italian sorta with a meaning along the lines of "type" or "kind". [0] http://www.anglo-norman.net/gate/ http://www.anglo-norman.net/gate/ [1] http://www.anglo-norman.net/D/sortir http://www.anglo-norman.net/D/sortir [2] https://en.wiktionary.org/wiki/sortior#Latin https://en.wiktionary.org/wiki/sortior#Latin
- bagrow 8y agoIf you decorate each item with a category tag and then sort using those tags, you are categorizing. The power of decorate-sort-undecorate.
- kazinator 8y agoSorting is categorizing, just with an order imposed on the categories. If the categories have a natural order, then people will exploit that when they sort. Suppose you had to put some cards with names on them into bins labeled by first letter. You might go through the cards one by one and stick each in the appropriate bin. It would help you if the bins are in alphabetic order, rather than scrambled. Sorting into categories involves a search to find the category for an item; the search benefits from order.
- hk__2 8y ago> Sorting is categorizing, just with an order imposed on the categories. …and infinite categories.
- jdmichal 8y agoInfinite, or recursive? Alphabetic, lexographic, and numeric sorts are recursive over "significant digits", which is why we can write radix sorts. (Scare quotes because that term doesn't necessarily directly translate to alphabetic and lexographic sorting, but the basic prinicple is the same.)
- solipsism 8y ago"recursively" is but one way to build a potentially infinite set. They're not mutually exclusive.
- mywittyname 8y agoI actually asked a non-math/cs person the question, "if I gave you a shuffled deck of cards and asked you to sort them, what would you give me?" Her response was, I'd give you the deck order them by suit (spade, club, heart, diamond), then by number (with j,q,k after 9). Which was what I expected. The twitter post seems to suggest that his expectation for the given question would be four decks, one for each suit (i.e., categorized).
- Isamu 8y agoKnuth discusses this in Vol 3 Sorting and Searching ... we mean "collate" by sorting. Unfortunately I don't have that volume at hand to quote. Anybody?
- sp332 8y ago> 5.2.4 Sorting by Merging > Merging (or collating) means the combination of two or more ordered files into a single ordered file. So it's not quite the same idea.
- outsidetheparty 8y agoMaybe it's just because I've spent too long with computers, but I thought the everyday meaning of "sorting" was ordering, not categorizing. (Though now that I think about it, it's both: if I handed a random non-coder a deck of cards and asked them to sort them, I'd expect them to group by suit and then order by value. I wouldn't expect four stacks by suit in random order, or a deck of all the cards in numerical order regardless of suit...) That nitpick aside, it was a good excuse to get into the interesting pre-digital computing history stuff.
- adamzochowski 8y agoThere are phrases using word sort as a category: "this sort of people" , "sort of liked".
- o_nate 8y agoI had the same initial reaction, but the dictionary supports the idea that the everyday usage of sort means to group by category, not to order. I've probably just been coding too long as well.
- outsidetheparty 8y agoYou’re right, it does! I wonder if the definition is going to drift towards “ordering” as computing becomes ever more ubiquitous, or if we’re just in a linguistic cul de sac by virtue of our profession...
- alanbernstein 8y agoAre you referring to a dictionary of word definitions? The kind that is structured as a list of words, ordered lexicographically? Where is the categorization in that?
- mort96 8y agoWhat do you mean? I agree that dictionaries are ordered and not categorized, but do dictionaries claim to be sorted?
- randomwalker 8y agoOP here. The number and variety of special-purpose computing devices that existed before general purpose computers is astounding. The surprising (to me) conclusion is that the main impediment to the development of computers wasn't technology. After all, Babbage's machine could have been built in his time if funding hadn't run out. Rather, the limitation was that people didn't have the abstractions, vocabulary, and mental tools to properly conceive of general purpose computers as a concept and to understand their usefulness. They couldn't see that devices as seemingly disparate as tide prediction machines[1], census tabulation machines, and loom controllers were all instances of a single, terrifyingly general idea. From what I can tell, Babbage mostly understood this, but it was Ada Lovelace who grasped it fully. But her writings weren't understood in her time and had to be "rediscovered" a century later. For example, she wrote [2]: Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent. This leads me to wonder: what abstractions are we missing today that will be obvious to future generations? BTW I have a follow-up thread on the optical telegraph, a form of networking that long predates the Internet. [3] My long-term goal is to teach a course on computing/networking/information processing before computers, with a view to extracting lessons that are still applicable today. [1] https://en.wikipedia.org/wiki/Tide-predicting_machine https://en.wikipedia.org/wiki/Tide-predicting_machine [2] https://googleblog.blogspot.com/2012/12/honouring-computings-1843-visionary.html https://googleblog.blogspot.com/2012/12/honouring-computings... [3] https://twitter.com/random_walker/status/1037031465735860224 https://twitter.com/random_walker/status/1037031465735860224
- garmaine 8y ago> After all, Babbage's machine could have been built in his time if funding hadn't run out. Funding ran out in large part because of cost overruns due to the fact that the technology of the time wasn’t capable of building the analytic engine design.
- irrational 8y agoThis was my understanding as well. The tight machining tolerances required simply didn't exist in his time.
- codazoda 8y agoI dunno... phonebooks we're sorted alphabetically before they were created with computers. That's a single sorted list and not a set of categories. The card sorting is interesting but it seems like the word is simply used in multiple ways.
- adamzochowski 8y agoSoundex, the word similarity hashing algorithm, also predates computers. It was developed in early 1900, to help perform census in USA. One of its goals was to sort similar last names together. https://en.wikipedia.org/wiki/Soundex https://en.wikipedia.org/wiki/Soundex
- olejorgenb 8y agoAssoc: Edge-notched cards - https://kk.org/thetechnium/one-dead-media/ https://kk.org/thetechnium/one-dead-media/
- fiftyfifty 8y agoThat's exactly what bucket sort is. Don't they teach that in Comp Sci anymore?
- wodenokoto 8y agoThese "twitter stories" are horrible to read. Someone else posted a much more readable version, but it is buried under a downvoted post: https://threadreaderapp.com/thread/1036704758696960001.html https://threadreaderapp.com/thread/1036704758696960001.html
- jalayir 8y agoOrdering is just a special case of categorizing.
- wyattpeak 8y agoI'd say it's arguably a degenerate case, but it's very arguable. Few people would claim that each position in an order is a different category. And if I asked someone to categorise a pile of papers and they handed me back a single stack, I'd be unimpressed.
- rjurney 8y agoIn MapReduce, they're the same thing.
- nixpulvis 8y agoYawn, words mean things in context... yada yada. That said, the details about old school punch card sorting is pretty neat.
- jancsika 8y agoI'm not sure what the difference is in sorting by category vs. order. For example, consider an array of one million arbitrary alpha-numeric strings. If you were to sort them by category, would that mean simply making contiguous regions of the array where each string begins with the same character?
- femto 8y ago> If the electric telegraph hadn’t been invented, would engineers have continued to optimize the optical telegraph? Isn't that today's Free Space Optical Communications? Bandwidth is measured in Gigabits per second. https://en.wikipedia.org/wiki/Free-space_optical_communication https://en.wikipedia.org/wiki/Free-space_optical_communicati...
- admax88q 8y agoHoly hell do I hate reading articles as a series of tweets.
- icc97 8y agoThe OP says it was just a random collection of thoughts rather than an article. He's going to turn them into a proper blog post.
- billfruit 8y agoSome words do have different meaning in computer science, as is the case with other fields as well. Perhaps a more illustrative example is the word "or", in plain english it normally means an "exclusive or", but in CS it means an "inclusive or".
- anonytrary 8y ago"That sort of person would sort the blocks into buckets" uses "sort" twice (differently) without implying some underlying metric for "people" or "blocks" and it's pretty clear in context. I saw a few people in the comments say they are surprised that "sort" would be used that way, but I'd bet money that they understood my example correctly. "The blocks were sorted by size" implies that there is some metric, and again, it's pretty clear in context.
- acct1771 8y agoOrdering is categorizing organized into a vertical grid.
- dexen 8y agoConsider the following four combinations of {stable, unique}: - stable sort of unique values is ordering - stable sort of non-unique values is categorization + ordering; this is a most general algorithm which could reasonably be used for either operation - non-stable sort of non-unique values is categorization without ordering - non-stable sort of unique values technically could be implemented as a NOP. Given that various strategies of ordering and categorizing have different trade-offs between {memory,computational} complexity, and linear vs random access patterns, it makes sense to consider them pluggable algorithms that can be swapped depending on requirements.