8000 Merge pull request #166 from srutstein21/CombSort · adithyabhat/swift-algorithm-club@04ce858 · GitHub
[go: up one dir, main page]
Skip to content

Commit 04ce858

Browse files
kelvinlauKLkelvinlauKL
authored
Merge pull request kodecocodes#166 from srutstein21/CombSort
Added Comb Sort
2 parents bc14780 + 0951ea3 commit 04ce858

File tree

5 files changed

+176
-0
lines changed

5 files changed

+176
-0
lines changed

‎Comb Sort/Comb Sort.playground/Contents.swift

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
// Comb Sort Function
2+
// Created by Stephen Rutstein
3+
// 7-16-2016
4+
5+
import Cocoa
6+
7+
func combSort (input: [Int]) -> [Int] {
8+
var copy: [Int] = input
9+
var gap = copy.count
10+
let shrink = 1.3
11+
12+
while gap > 1 {
13+
gap = (Int)(Double(gap) / shrink)
14+
if gap < 1 {
15+
gap = 1
16+
}
17+
18+
var index = 0
19+
while !(index + gap >= copy.count) {
20+
if copy[index] > copy[index + gap] {
21+
swap(&copy[index], &copy[index + gap])
22+
}
23+
index += 1
24+
}
25+
}
26+
return copy
27+
}
28+
29+
// A function to swap two integer values
30+
// Used for swapping within the array of values.
31+
func swap (inout a: Int, inout b: Int) {
32+
let temp = a
33+
a = b
34+
b = temp
35+
}
36+
37+
// Test Comb Sort with small array of ten values
38+
let array: [Int] = [2, 32, 9, -1, 89, 101, 55, -10, -12, 67]
39+
combSort(array)
40+
41+
// Test Comb Sort with large array of 1000 random values
42+
var bigArray = [Int](count: 1000, repeatedValue: 0)
43+
var i = 0
44+
while i < 1000 {
45+
bigArray[i] = Int(arc4random_uniform(1000) + 1)
46+
i += 1
47+
}
48+
combSort(bigArray)
49+
50+

‎Comb Sort/Comb Sort.playground/contents.xcplayground

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
2+
<playground version='5.0' target-platform='osx'>
3+
<timeline fileName='timeline.xctimeline'/>
4+
</playground>

‎Comb Sort/Comb Sort.playground/playground.xcworkspace/contents.xcworkspacedata

Lines changed: 7 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Comb Sort/Comb Sort.swift

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
// Comb Sort.swift
2+
// Comb Sort
3+
//
4+
// Created by Stephen.Rutstein on 7/16/16.
5+
// Copyright © 2016 Stephen.Rutstein. All rights reserved.
6+
//
7+
8+
import Foundation
9+
10+
func combSort (input: [Int]) -> [Int] {
11+
var copy: [Int] = input
12+
var gap = copy.count
13+
let shrink = 1.3
14+
15+
while gap > 1 {
16+
gap = (Int)(Double(gap) / shrink)
17+
if gap < 1 {
18+
gap = 1
19+
}
20+
21+
var index = 0
22+
while !(index + gap >= copy.count) {
23+
if copy[index] > copy[index + gap] {
24+
swap(&copy[index], &copy[index + gap])
25+
}
26+
index += 1
27+
}
28+
}
29+
return copy
30+
}
31+
32+
func swap (inout a: Int, inout b: Int) {
33+
let temp = a
34+
a = b
35+
b = temp
36+
}

‎Comb Sort/README.markdown

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
# Comb Sort
2+
3+
A common issue for Bubble Sort is when small values are located near the end of an array.
4+
This problem severely slows down Bubble Sort, as it must move the small value -- or _turtle_ --
5+
through nearly the entire array. Bubble Sort works by checking the current index of an array
6+
against the next index, and when those two values are unsorted, they are swapped into place.
7+
As a result, the values bubble into their rightful place within the array.
8+
9+
Comb Sort improves upon F438 Bubble Sort by dealing with these turtles near the end of the array.
10+
The value of the current index of the array is compared against one a set distance away. This
11+
removes a worst-case scenario of Bubble Sort, and greatly improves on the time complexity of Bubble Sort.
12+
13+
## Example
14+
15+
A step-by-step example of how Comb Sort works, and differs from Bubble Sort, can be seen [here](http://www.exforsys.com/tutorials/c-algorithms/comb-sort.html).
16+
17+
Here is a visual to see Comb Sort in effect:
18+
19+
![](https://upload.wikimedia.org/wikipedia/commons/4/46/Comb_sort_demo.gif)
20+
21+
## Algorithm
22+
23+
Similar to Bubble Sort, two values within an array are compared. When the lower index value
24+
is larger than the higher index value, and thus out of place within the array, they are
25+
swapped. Unlike Bubble Sort, the value being compared against is a set distance away. This
26+
value -- the _gap_ -- is slowly decreased through iterations.
27+
28+
## The Code
29+
30+
Here is a Swift implementation of Comb Sort:
31+
32+
```swift
33+
func combSort (input: [Int]) -> [Int] {
34+
var copy: [Int] = input
35+
var gap = copy.count
36+
let shrink = 1.3
37+
38+
while gap > 1 {
39+
gap = (Int)(Double(gap) / shrink)
40+
if gap < 1 {
41+
gap = 1
42+
}
43+
44+
var index = 0
45+
while !(index + gap >= copy.count) {
46+
if copy[index] > copy[index + gap] {
47+
swap(&copy[index], &copy[index + gap])
48+
}
49+
index += 1
50+
}
51+
}
52+
return copy
53+
}
54+
```
55+
56+
This code can be tested in a playground by calling this method with a paramaterized array to sort:
57+
58+
```swift
59+
combSort(example_array_of_values)
60+
```
61+
62+
This will sort the values of the array into ascending order -- increasing in value.
63+
64+
## Performance
65+
66+
Comb Sort was created to improve upon the worst case time complexity of Bubble Sort. With Comb
67+
Sort, the worst case scenario for performance is exponential -- O(n^2). At best though, Comb Sort
68+
performs at O(n logn) time complexity. This creates a drastic improvement over Bubble Sort's performance.
69+
70+
Similar to Bubble Sort, the space complexity for Comb Sort is constant -- O(1).
71+
This is extremely space efficient as it sorts the array in place.
72+
73+
74+
## Additional Resources
75+
76+
[Comb Sort Wikipedia](https://en.wikipedia.org/wiki/Comb_sort)
77+
78+
79+
*Written for the _Swift Algorithm Club_ by [Stephen Rutstein](https://github.com/srutstein21)*

0 commit comments

Comments
 (0)
0