Hello,

Do you plan to implement Quadtree and Octree?

Regards

In the HashTable section, while applying it on a new project file, I noticed that private typealias Element, with uppercase E, in this part:

public struct HashTable<Key: Hashable, Value> {
  private typealias Element = (key: Key, value: Value)
  private typealias Bucket = [Element]

  private var buckets: [Bucket]
  private(set) var count = 0

  public init(capacity: Int) {
    assert(capacity > 0)
    buckets = .init(count: capacity, repeatedValue: [])
  }

  public var isEmpty: Bool {
    return count == 0
  }

 ...

}

seems to be the same one used in the for-loop in the updateValue function here :

public mutating func updateValue(value: Value, forKey key: Key) -> Value? {
  let index = indexForKey(key)

  // Do we already have this key in the bucket?
  for (i, element) in buckets[index].enumerate() {
    if element.key == key {
      let oldValue = element.value
      buckets[index][i].value = value
      return oldValue
    }
  }
       ...
}

It works fine on a couple of tests I tried, but is element referencing Element somehow? I could not get it. If it is a typo I can submit a pull request.

Thanks for this amazing source, it has been helping me a lot with my studies.

It would be great if there was a bit more explanation of how the code actually works. The illustrations are very useful already, but a step-by-step explanation of the logic would also be good to have. :-)
#51

I wonder whether you have a plan for a website on this repo, maybe with gh-pages.

This is really cool, do you think it would be nice to add all of these to a hackerrank.com as a challenge so that people can work on them and keep score using the hackerrank.com system?

There are two implementations of min/max, both of which are O(n).
Is there any reason to choose the second algorithm (comparing in pairs) over the first?

And, for swift's minElement() and maxElement(),

let array = [ 8, 3, 9, 4, 6 ]
array.minElement()   // This will return 3
array.maxElement()   // This will return 9

Did they use the first algorithm (one-by-one comparison) or the second (pair comparison)?

I'd love to see a Swift treatment for QuickHull: Compute the convex hull of a set of three dimensional points. Which is useful for computing volumes of convex polygons.

The algorithm is a three dimensional implementation of Quickhull, as described in Barber, Dobkin, and Huhdanpaa http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405&rank=4 "The Quickhull Algorithm for Convex Hulls'' (ACM Transactions on Mathematical Software, Vol. 22, No. 4, December 1996), and has a complexity of O(n log(n)) with respect to the number of points.

A well-known C implementation of Quickhull that works for arbitrary dimensions is provided by http://www.qhull.org

Carl Wieland has contributed a Swift 2.3 QuickHull implementation here: https://github.com/utahwithak/Swift-Quickhull

Radix sort isn't even limited to integers.

By making the GCD function recursive, there is much more clarity and it justifies the text better than with the while loop:

func gcd(m: Int, _ n: Int) -> Int {
    let r = m % n

    if r == 0 {
        return n
    }
    return gcd(n, r)
}

And... we're done!

Thanks everyone for pitching in!

Xcode 8 and Swift 3 will be formally released soon and we need to migrate everything to Swift 3.

Want to help out with the migration? Awesome! :]

Please follow this process for migrating to Swift 3

• Download the Xcode 8.X
• Create a pull request to "claim" an algorithm or data structure you'd like to migrate. Just so multiple people don't work on the same thing.
• Migrate the algorithm/data structure project, playground, tests and readme to Swift 3
  • Uncomment test project in .travis.yml so it will run on our Xcode 8 Travis CI build server
• Comment in the pull request when the changes are ready to be merged

Suggestions and feedback is welcome!

List of algorithms to be migrated to Swift 3

nil

Completed Migrations

• AVL Tree #183
• All-Pairs Shortest Paths #347
• Array2D #189
• B-Tree #203
• Binary Search Tree
• Binary Search #184
• Binary Tree #213
• Bit Set #194
• Bloom Filter #195
• Bounded Priority Queue #218
• Boyer-Moore #248
• Breadth-First #237
• Brute-Force String Search #239
• Bubble Sort (no code)
• Bucket Sort #281
• Comb Sort #350
• Combinatorics #270
• Count Occurrences #201
• Counting Sort #235
• Depth-First Search #238
• Deque #303
• Fixed Size Array #271
• Fizz Buzz #229
• GCD #219
• Graph #267
• Hash Set #276
• Hash Table #216
• Heap Sort #334
• Heap 3945383
• Huffman Coding #344
• Insertion Sort #198
• K-Means #349
• Kth Largest Element #228
• Linear Regression #283
• Linear Search #200
• Linked List #250
• Longest Common Subsequence #243
• Merge Sort #199
• Minimum Edit Distance #302
• Minimum Spanning Tree (Unweighted) #345
• Monty Hall Problem #241
• Ordered Array #232
• Ordered Set #234
• Palindromes #187
• Priority Queue #233
• Queue #197
• Quicksort #217
• Radix Sort #347
• Radix Tree #242
• Red-Black Tree #214
• Ring Buffer #265
• Run-Length Encoding #364
• Segment Tree #220
• Selection Sampling (no changes necessary)
• Select Minimum Maximum #333
• Selection Sort
• Set Cover (Unweighted) #366
• Shell Sort #260
• Shortest Path (Unweighted) #343
• Shuffle #273 #274
• Shunting Yard #365
• Single-Source Shortest Paths (Weighted) #356
• Stack #196
• Ternary Search Tree
• Topological Sort #259
• Treap #251
• Threaded Binary Tree #367
• Tree #193
• Trie #208
• Two-Sum Problem #266
• Union-Find #192

Since you've added SegmentTree, I think it's good to add Fenwick too, they differ on speed and some usages.

When I open the playground of HashTable.playground in Xcode 8 beta 3 , It produce many errors.
error:

I don't know how to solve it. Some can help me.

Thank you!

Hey!
I'd like to write a guide and provide an example for Bubble Sort. Though I agree we shouldn't have to learn it, I'd like to use the opportunity to familiarize myself with GitHub and continue to contribute this project.
Thanks

func binarySearch<T: Comparable>(a: [T], key: T, range: Range) -> Int? {
if range.startIndex >= range.endIndex {
// If we get here, then the search key is not present in the array.
return nil

Can you answer why startIndex is >= endIndex rather than = ?
I can't think of a situation where startIndex will ever be bigger than endIndex.

There's an error in the readme of the fizz buzz algorithm found here: https://github.com/raywenderlich/swift-algorithm-club/tree/master/Fizz%20Buzz

A table giving example results of using the modulus operator shows that 1/3 results in 0 with a remainder of 3. This should however be 0 with a remainder of 1. and thus the modulus result in the last column of the table should also be 1 instead of 3.

AVL Tree will crash with following conditions:

let tree = AVLTree<Int, String>()

tree.insert(1, "five")
tree.insert(2, "four")
tree.insert(3, "three")
tree.insert(4, "two")
tree.insert(5, "one")

tree.delete(5)
tree.delete(1)
tree.delete(4) // Crashes here
tree.delete(2)
tree.delete(3)

There are other combinations of remove that will crash. Examples:

[2, 3, 1, 5, 4]  // Crashes at 3
[4, 5, 3, 2, 1]  // Crashes at 5
[3, 2, 5, 4, 1]  // Crashes at 2

Swift was trying to unwrap a nil reference in delete, causing the program to crash.

Please advice thanks!

I note that Trie appears to have a good use case for finding string values amongst a set. However because Swift strings are actually interpreted as a set of glyphs (or unicode-based codes). I wonder whether this algorithm would also work well with a language like Chinese? And thinking about this, perhaps another avenue to open up for contribution might be real world use-cases (we'd need a place to store such examples, but it could be helpful to those wanting to go from theory to application). In any case if anyone has a good example of searching Chinese with a Trie, please share.

There is a link to build status at the bottom of README.md. However the link is not valid as the project is not found on Travis CI.

Is this project dropping support for Travis CI? If so please remove the build status badge. Thanks!

Any plans to upgrade the Xcode version set in travis?

It's very hard to find tutorials talking about Treap, could you implement and teach it?

for games like asteroids and other stuff... that would be cool.

Currently working on this.

• Create TST with insertion and find supported
• Document source code
• Write README explaining the data structure, its uses, and its pros and cons.

Some things that could be improved in the AVL tree:

• Explain how the rotations work.
• Unit tests. This is a fairly complex data structure so it would be good to have extensive tests.
• The code uses too much forced unwrapping.

When removing a node with two children, the node you're calling remove() on stays in the tree. It's just given a new value.

When removing a node with 1 child or with no children, that particular node instance is removed from the tree. So this doesn't always work the same way.

Usually that's not a problem, except when the node you're calling remove() on is the root node. If the root only has 1 child, that instance becomes invalid. The child is now the new root node. But since you yourself are responsible for tracking which node is the root, this can result in bugs.

Possible solutions:

1. Return the node instance that is actually removed. Require the user to check with node.isRoot whether the root changed.
2. When there is only one child, don't remove the node itself but the child. Give the node the value of the child, just like we do when there are 2 children. This seems like the better solution.

There is currently no unit test that catches this.

I think that we need unit testing to validate some complicated algorithms, even the simplest ones need testing to avoid regressions.

XCTests is not supported in playgrounds, hope that it will be in the future.
I think that we should organize the project to have a test target.

What is the issue?

Open discussion adding multiple methods of code to accomplish the same algorithm. There is always different ways to do the same thing. If it completes the same algorithm in the same time complexities it would be great to show different ways to implement. Some may understand different ways better.

Example

This is proposing to add a quick sort and binary search alternative code examples to the one in the repo currently. The quick sort currently is a little more advanced. This proposes to add a simpler quick sort, no need an extra function for partition.

Quick sort alternative

func quickSort<T: Comparable>(inout array: [T], left: Int, right: Int) -> [T] {
    if array.count <= 1 { return array }
    var i = left
    var j = right

    let mid = array[(left + right) / 2]

    repeat {
        while array[i] < mid && i < right {
            i += 1
        }

        while mid < array[j] && j > left {
            j -= 1
        }

        if i <= j {
            if i != j {
                swap(&array[i], &array[j])
            }
            i += 1
            j -= 1
        }
    } while (i <= j)

    if left < j {
        quickSort(&array, left: left, right: j)
    }

    if i < right {
        quickSort(&array, left: i, right: right)
    }

    return array
}

Binary search alternative

func binarySearch<T :Comparable>(arry: [T], key: T, low: Int, high: Int) -> Int? {
    if arry.count == 0 {
        return nil
    }

    if low > high {
        return nil
    }

    let mid = (low + high) / 2

    if arry[mid] == key {
        return mid
    }

    if arry[mid] < key {
        return binarySearch(arry, key: key, low: mid + 1, high: high)
    } else {
        return binarySearch(arry, key: key, low: low, high: mid - 1)
    }
}

Discussion

This isn't about adding 15 ways to implement some simple algorithms but more about showing simpler ways to implement harder to comprehend algorithms such as merge sort, quick sort and binary tree. The more lower level the better. The algorithms should be written in Swift but not depend on Swift helper methods to achieve the goals. It defeats the purpose of understanding the underlying algorithm.

Hey Matthijs,
I am pretty new to swift and I have been looking to contribute to this repo as a learning experience. Right now i am taking a look at the Binary Search Tree implementation and in both solution 1 and 2 when i try to compile the playground contents.swift file, it gives me and unresolved identifier error for Binary Search Tree, i was wondering if you could help me understand why this is happening/how to fix it. Thanks!

Contents.swift:4:12: error: use of unresolved identifier 'BinarySearchTree'
var tree = BinarySearchTree.Leaf(7)

I am compiling using

swiftc Contents.swift -o out

Instead of

public mutating func pop() -> T? {
  if isEmpty {
    return nil
  } else {
    return array.removeLast()
  }
}

we can just do

public mutating func pop() -> T? {
  return array.popLast()
}

Hey @johnsgill3,

I was trying to clean up your BoundedPriorityQueue a little but now I'm horribly confused...

Is this supposed to be a min- or max-priority queue? From the description I gathered it was a min-priority queue, so the item with the lowest priority value would be the most important and therefore be at the front of the queue.

However, in the implementation the item with the highest priority is at the front of the queue. When you dequeue() it always returns the highest priority item. So that leads me to believe it's a max-priority queue.

The confusing thing is this: when the queue gets full, you call dequeue() to throw away the least important item. But that actually throws away the most important item!

What am I missing here?

Hi @hollance
Some times ago I decided to create very similar repo with ObjC code.
https://github.com/EvgenyKarkan/EKAlgorithms
Can we mention each other in our repos?
It would be great if we could be friends.
I guess it will be useful for community.

Best wishes.

Comments in the current style are not parsed by Xcode and do not show up in Quick Help. Comments must either be preceded by /// on each line or start with /** and end with */. Both alternatives listed below are parsed by Xcode and show up in Quick Help.

Reference:

1. Quick NSHipster article
2. Full Markup Formatting Reference

Current - Unparsed comments

/*
  A fixed-size sequence of n bits. Bits have indices 0 to n-1.
*/
public struct BitSet {
    /* How many bits this object can hold. */
    private(set) public var size: Int

Option 1 - Apple (see example)

/// A fixed-size sequence of n bits. Bits have indices 0 to n-1.
public struct BitSet {
    /// How many bits this object can hold.
    private(set) public var size: Int

Option 2

/**
  A fixed-size sequence of n bits. Bits have indices 0 to n-1.
*/
public struct BitSet {
    /** How many bits this object can hold. */
    private(set) public var size: Int

I am a huge fan of the Option+Click Quick Help inspector and feel it would be a helpful addition.
If you would like this done; i'd be happy to start working on converting existing files over to Option 1 or Option 2.

Hi guys, I've seem some of the algorithms are copy-pasting the code inside the playgrounds in order to access to it. For example Bloom Filter.

I'd say it's better to include the files we develop for the algorithms inside the playground's sources folder.

This can be achieved doing this Apple recommended steps to add auxiliary code to your playgrounds.

This option still has the limitation that the changes made on the original file are not reflected inside the playground's sources folder. But I think it's cleaner than copying all the source code inside the playground itself.
The changes are not reflected because the file is actually duplicated not referenced.
If somebody knows how to reflect the changes you made on the original file inside the playground please let me know.
I have been trying creating symbolic links for the command line but this is not working.

The Deque page even mentions that a deque can also be implemented using two stacks rather than one array. Using two stacks is a lot easier because you don't have to deal with getting rid of empty space at the front, and I bet that makes it faster as well. What's the point of using a single array?

Love the repository, it's been very useful in my recent learning endeavors. Being a professional iOS developer without a CS background, I've been looking to increase my understanding of foundational CS topics like algorithms and data structures.

I really like the Algorithm Visualizer linked in the README, and also really like the images and visualizations that accompany many of the algorithms or data structures in the repository.

A couple questions:
• Have folks thought about a way to visualize algorithms right inside the playground, a la the Algorithm Visualizer?
• What tools do you all use to generate your static visualizations of arrays, graphs, etc.?

I'm interested in a task to improve my understanding of these topics and I'd be really interested in creating visualizations of these algorithms that were accessible right in the playground. Has anyone thought about or started this task?

why is it that i can access, array variable outside the class?
I am new to swift, but when i was in java, i coudn't access a private variable outside the class.
here, in playground, i am using the array variable and functions like popLast() in Queues which completely looses the meaning of a Queue.
var que = Queue<String>()
que.enqueue("Mayur")
que.enqueue("Tolani")
que.array //this is private, it should give an error
que.array.popLast()//this shouldn't be allowed, right?

Hey!

Great project and idea! I'm a computer science student and I'm sure many developers will find this repo very useful.
I was thinking that maybe it'd be better to provide the Swift code inside a Playground so people can start running an algorithm and play around with it right away. What do you think? 😀

I tried to implement merge sort manipulating original array itself rather than allocating new arrays within sub problems.

https://gist.github.com/madnik/924168b045f57f94183908a0bc1010e9

Appreciate discussion and conclude the best.

Are there any plans to make this available through carthage, cocoapods or SPM? This may dictate how we set up our submissions. Some want library/framework targets, others want a file/directory structure (SPM).

For instance, the breadth first search algorithm uses the Queue data structure that is presented in the Queue article. I think we should add a note and a link to the article for convenience and to prevent confusion for the reader.

An important field of algorithm missing from the examples implementations in Swift is the field of graph algorithms. You can find many algorithms in the Open Graph Drawing Framework (OGDF). It is a popular open source C++ library of algorithms and data structures for graph drawing.

http://cs.brown.edu/~rt/gdhandbook/chapters/ogdf.pdf

http://www.ogdf.net

Please add some graph algorithm examples in the Swift algorithm club, thank you!

I've found a book on Wikibooks about algorithms implementation, which I think it's worthy to include in the main README.
The goals of the book is to collect several algorithms and documentation, it's unifying information from wiki articles and wiki source code.
Let me know what do you think about the book, and I'd add it to the main README.

I think a weighted variant of the shortest path algorithm would fit this great repository as well. Perhaps implementing Dijkstras or Bellman-Fords (allowing negative vertices) would yield usability for people trying to learn algorithms and also want a way of calculating the shortest, most cheap path from a given node to all others.

Just a thought 👍

This actually was asked by a hiring manager at Apple:

"Given two arrays with integers, find integers that are in both arrays."

And of course, there are:

1. Brute force (O(n^2)
2. Sort an array + Binary search (O(n log n))
3. Create hash table of one + find matches (O(n))

Based on the way the code for the RemoveChildWith2Nodes, the condition right === successor will never happen. We first call successor.remove() before updating the successor's right and left positions. The remove() call initially, will ensure that if successor was indeed same as the right, its parent's right is set to nil. So this check is moot as there is no way that the right can be exactly same as successor

I will try to give a better explanation if this isn't sufficient soon.

Hi guys, I've added to my personal collection, some data structure and algorithms as code snippets.
barbaramartina/swift-code-snippets@49572e0
I was thinking if code snippets could be added to this repo, and how useful it would be. Due to probable changes in the implementations, if we don't have the snippet generation done automatically, the sync between algorithms/snippets can be easily lost.
Anyway, I think having the snippets prepared to be imported into any other XCode could be great.
In this line of thoughts, I was considering including some kind of MARKUP... like:
//
//

In the part of the code that we would like to have automatically converted to code snippets.
That way we could prepare an script later to parse all the .swift file and load the snippets content.

Hello,

I think adding to the Stack data structure the conformance to the CollectionType protocol, but a Stack has two principal opérations : push, pop.

What do you think ?

Thanks

I want to contribute my Swifty implementation of Manacher's Algorithm . I searched and didn't seem to find anything in the code--but I've been wrong many times before.

let a = [11.0, 2.0, 5.0, 9.0, 10.0, 10.0, 1.0]
a's median value is 9.0
but that's not my purpose, I want find value the most close to middle value between 11.0 and 1.0, and it would be 5.0

Is this exist algorithm?
If may not being. I want update that.

I have made production-quality Swift implementations of some common algorithms and data structures.
Some/all of them might be a bit too complex for educational use, but feel free to use them as you like.
(Or it might be useful to link to them, to illustrate the work necessary to make stuff feature complete, reusable and performant.)

• Arbitrary precision integers
• Deque using a circular buffer
• In-memory B-Trees and ordered collection types with copy-on-write value semantics
• Red-Black Trees with COW value semantics

Feel free to close this if they're not a good fit!

Hi there I am just started to learn Swift. Do you think swift-algorithm would be too advanced for me?