Quicksort in Swift | Hacker News Reader

Quicksort in Swift

gist.github.com

30 pointsfjcaetano47 comments

If anyone's wondering, yes, there's a quickSort function already in the Swift standard library (no import required):

    var ar = [3456,45,53567,356,7225,47858]

    quickSort(&ar, Range(start: ar.startIndex, end: ar.endIndex))

    // [45, 356, 3456, 7225, 47858, 53567]

There's also a version that let's you specify the "less" comparator.

How did you discover this?

Use a Swift standard library function in the documentation (like println). Command-Click on it to go to it's definition. You're taken to a header-like description of the standard library (assuming the index has been built for your project – sometimes you have to wait a few minutes in a new project).

I was surprised this example didn't take advantage of Swift's built-in Comparable protocol, so I rewrote it! I also wrote an example of how you can implement the Comparable protocol for a struct, so that they can then be sorted.

https://gist.github.com/dstaley/e7171375d3f5cb9f2fe4

This actually highlights one area where I find Swift slightly deficient. I was just thinking earlier today that Swift is remarkably close to my dream language, i.e. incorporates the great features of many languages I've come in contact with. But one thing it lacks is Haskell's amazing list comprehension, which helps make Haskell quicksort so succinct.

That quicksort one-liner that you often see for Haskell is crap.

Had a chat about Swift over lunch today, one topic was the choice of using .. and ... to represent ranges. Interesting to see the comments of the gist focus on this as well. Surely is a confusing and potentially dangerous syntax.

Interestingly, the .. and ... operators are not part of the language but are defined in the standard library.

This means you can override .. (to disable it) and define your own operator for half-closed ranges if you'd prefer (Swift supports building your own operators from combinations of punctuation characters). At least I think you could do this: I haven't tried.

If so, that opens entire new routes for obfuscation.

For the subject at hand: I would like to have seen ranges use () for open endings and [] for closed ones. For example, [1..5) would include 1 but exclude (that is standard notation in mathematics. See http://en.wikipedia.org/wiki/Interval_(mathematics)#Excludin...)

Back to the obfuscation thing: unfortunately for that goal, one cannot create prefix operators with names (, [ or {

It is possible to define an infix operator named ., though. That could give whole new meaning to what look like floating point values such as 3.14.

Interesting, would it be possible, then, to use the perl6 style operators? (^ at either end to make it exclusive instead of inclusive)

Hoare's original paper from 1962.

http://comjnl.oxfordjournals.org/content/5/1/10.full.pdf+htm...

There are reasons not to perform quickSort the way people did fifty years ago. Data sets are larger and worst case time for quickSort approach 0(n^2) when data is already ordered and pivots are selected in-order. Randomizing pivot selection mitigates this back toward O(log n).

All that mutation and pointer swapping are artifacts of the way things used to have to be done by programmers. And they're useful as academic exercises. Hoare's algorithm is really fucking brilliant. But mapping and filtering in a functional style, makes more sense than dotting the 'i's and 'j's if someone is going to be reading and maintaining the code. There's a reason people don't use C to program mobile devices.

Moreover, while Hoare's original algorithm was designed to work in place, the idea of working in place is less coherent today. When we strive to distribute and parallelize big nasty resource intensive jobs, what does "in-place" mean? See Leslie Lamport, Thinking for Programmers at about time = 36:00

http://channel9.msdn.com/Events/Build/2014/3-642

And even on a non-distributed system, when are we really coming up against the bounds of 'fast memory' these days? A serious problem that stretches 16 GigaBytes of RAM is less than $10,000 from 64 GigaBytes...or $200 from an SSD and using 'slow memory'.

Of course if we are parallelizing, we can even do it on one machine and again, what is 'in-place'? The caches? Again which ones and at what level. The Swift code (or Java or C#) may look like C, but it's not. It may be garbage collected, JIT'd, byte coded, and micro-coded all before it hits the mulit-stage branch predicting pipeline from several levels of cache reading from code pages that may have gone in and out to disk as threads and tasks switch.

'Place' might just mean somewhere. But probably somewheres.

I can't wait until GitHub or someone adds in Swift syntax highlighting

What kind of monster writes i += 1?

Among others, people who have learned to take JSLint a little too seriously [1].

[1] http://stackoverflow.com/questions/971312/why-avoid-incremen...

Python devs :)

I do, only because I've never seen a convincing case where unary increment/decrement improves the code in any way (and I've searched).

So, what convincing cases have you find of i += 1 over i = i + 1?

It reduces code redundancy, especially when 'i' is something more descriptive. Though if someone were to claim that the redundancy of i=i+1 is a trivial price for settling on one consistent multipurpose construct, I wouldn't put up a fight. :)

Consider a more descriptive variable name and hopefully it becomes obvious:

    sheepCounted += 1

vs.

    sheepCounted = sheepCounted + 1

It can easily get way worse once you consider classes and their properties:

    pInterface->m_someField[currentItem] += 1;

Anyone who writes python

From that, it's not too hard how people could think it was influenced by Go (though it apparently wasn't): http://play.golang.org/p/oWNRd0D2Zp looks superficially very similar

I like the syntax of Swift

Looks like a bizarre mix of JavaScript and C to me.

But then, hey... Objective-C syntax just offends me right-out ;-P

was waiting for someone to put this out :) awesome.

Until Apple open Swift, I'm sorry, it's DOA.

I'm sorry but that's silly. While I really hope that Swift does become a cross-platform language, it's pretty safe to assume that it will become the defacto Apple development language. It offers way too much in terms of developer productivity.

DOA (Dead On Arrival) implies that Swift will not be adopted by developers. If you're saying that, I disagree. It will almost definitely become the default way to write iOS apps very quickly.

If you're saying it's "dead to me", that's valid. It would be good to see them open up the Swift toolchain, and there will definitely be a significant percentage of devs who won't touch it unless they do.

This is WAY TOO early. Swift at the very least will very likely replace Objective-C which is nowhere near DOA. The fact is that there ARE a ton of developers that don't care if it's open or not.

Objective-C is open source, but without Foundation et al it's pretty useless. As tied as Swift is to Cocoa, it's almost certainly going to be in the same boat.

Put another way, how well does Objective-C do outside of Apple development?

I put your code on npm: https://www.npmjs.org/package/quicksort.swift

Edit: ...and then swiftly unpublished. It is unclear to me the legal issues involved in forking and publishing unlicensed gists.

http://stackoverflow.com/questions/4007674/whats-the-default...

why would you publish that on npm? i'm not familiar with the ecosystem, is there a precedent for publishing non-js source files on npm?

And why would you claim MIT license on the code which you didn't write and has no license listed?

I think it is good practice to license packages on npm, even when you are not the original author (which is very common on npm).

Well... technically something with no license is the most restrictive form of a license; as-in nobody has the right to use it nor republish it nor modify it. Not being the copyright holder forbids you from assigning a license.

However, for a trivial piece of code as this... it could be argued it's not copyright-able and therefore you are OK... but just be careful in the future.

If it's not copyrightable it's deceptive to add a purported copyright license. If it is, he has no right to relicense it. Either way not a good move.

Actually I just looked the copyright issue up: http://stackoverflow.com/questions/4007674/whats-the-default....

Unpublishing!

Again, I dont think a snippet this trivial is subject to copyright... I just wanted to point out you should mind these matters in the future. Besides offending a developer, you could get into some trouble.

Many times I've emailed devs on Github regarding some code they have that I'd like to use part of but they've failed to assign a license. A few time's I've been turned away... but usually the dev just forgot or was not aware others couldn't freely use it.

There is precedence for publishing non-js code on npm: https://github.com/substack/dotc

That looks to be JS code that implements a C preprocessor. And the C code present in it seems to be for demonstrating/testing the preprocessor.

Scroll down to the section "publishing c modules". It advocates publishing dotc modules on npm.

"npm? Isn't that for javascript?

Yes, but:

native node modules are written in c++

npm already exists

npm installs packages in a way that avoids dependency hell"

someone said there is already quicksort in the standard lib... so this code snippet is really only academic...

Wow... seems like a nightmare for several reasons:

>Naming Constants and Variables

>You can use almost any character you like for constant and

>variable names, including Unicode characters:

>let π = 3.14159

>let 你好 = "你好世界"

>let 🐶🐮 = "dogcow"

https://developer.apple.com/library/prerelease/ios/documenta...

I think if you're going to make a strong criticism of a complete design and implementation that includes decisions that were almost certainly made deliberately, then you owe an explanation or some kind of argument.

My position is that it's the language's job to allow expression of ideas and not its job to police or disallow bad sentences. I think such a thing [EDIT: disallowing bad sentences] is impossible and leads to COBOL-like languages. (Compilers can have options for coding standards, like "house rules" but I don't think it's the language's role.)

Well, besides adding to complexity of debugging or just reading/understanding of the codebase when the dev may not be familiar with say.. .Chinese characters, it may also limit which platforms it can run on. But, this is an apple language targeting only apple devices so the last part isn't much of an issue.

Basically using unicode characters is comparable to purposeful obfuscation, are difficult to type (no keyboard i'm aware of has a "cow" key), difficult to read/remember, and may become wrongly converted if the code is copy/pasted into a text editor not supporting that character.

Now, I don't think this constituted as a "strong criticism" nor warranted the downvote nor the expletive.

I don't think that is what "several" means.

I was not commenting on the entire languages design... talk about jumping to conclusions lol.

Reply on news.ycombinator.com