Merge branch 'master' into master

abranhe · web-flow · commit c7e9fda7bf6e · 2019-10-02T14:28:27.000-04:00
diff --git a/allalgorithms/sorting/quicksort.py b/allalgorithms/sorting/quicksort.py
@@ -0,0 +1,29 @@
+# -*- coding: UTF-8 -*-
+#
+# Quick Sort Algorithm
+# The All ▲lgorithms library for python
+#
+# Contributed by: Brian D. Hopper
+# Github: @bubbabeans
+#
+def partition(xs, start, end):
+    follower = leader = start
+    while leader < end:
+        if xs[leader] <= xs[end]:
+            xs[follower], xs[leader] = xs[leader], xs[follower]
+            follower += 1
+        leader += 1
+    xs[follower], xs[end] = xs[end], xs[follower]
+    return follower
+
+def _quicksort(xs, start, end):
+    if start >= end:
+        return
+    p = partition(xs, start, end)
+    _quicksort(xs, start, p-1)
+    _quicksort(xs, p+1, end)
+    
+def quicksort(xs):
+    _quicksort(xs, 0, len(xs)-1)
+
+# To use: create a list and send it to quicksort:  quicksort(list placed here)
diff --git a/allalgorithms/sorting/shell_sort.py b/allalgorithms/sorting/shell_sort.py
@@ -0,0 +1,30 @@
+# -*- coding: UTF-8 -*-
+#
+# Shell Sort Algorithm
+# The All ▲lgorithms library for python
+#
+# Contributed by: Elias
+# Github: @eliasbayona
+#
+
+def shell_sort(arr): 
+    n = len(arr) 
+    h = int(n/2)
+
+
+    while h > 0: 
+        for i in range(h,n):
+            
+            temp = arr[i] 
+            j = i 
+
+            while  j >= h and arr[j-h] >temp: 
+                arr[j] = arr[j-h] 
+                j -= h 
+
+            arr[j] = temp 
+
+        h = int(h/2)
+        
+    return arr
+
diff --git a/allalgorithms/string/__init__.py b/allalgorithms/string/__init__.py
@@ -1,2 +1,3 @@
 from .palindrome_check import *
-from .is_unique import *
+from .is_unique import *
+from .hamming_dist import *
diff --git a/allalgorithms/string/hamming_dist.py b/allalgorithms/string/hamming_dist.py
@@ -0,0 +1,14 @@
+# -*- coding: UTF-8 -*-
+#
+# Binary search works for a sorted array.
+# The All ▲lgorithms library for python
+#
+# Contributed by: ninexball
+# Github: @ninexball
+#
+
+def hamming_dist(seq1: str, seq2: str) -> int:
+    """Compare hamming distance of two strings"""
+    if len(seq1) != len(seq2):
+        raise ValueError("length of strings are not the same")
+    return sum(c1 != c2 for c1, c2 in zip(seq1, seq2))
diff --git a/docs/sorting/quicksort.md b/docs/sorting/quicksort.md
@@ -0,0 +1,39 @@
+# Quicksort
+
+A quicksort is a quicker method of sorting, and there are four different ways of implementing it.  The example given uses a pivot point.
+
+A pivot point is created in the middle of an array, and all larger items go after the pivot point, and smaller items are placed in front
+of the pivot point.
+
+The pivot point is then moved to the middle of either the smaller or larger items, and the sort is run again on that half.
+
+This continues over and over again until everything is in the proper place.
+
+## Install
+
+```
+pip install allalgorithms
+```
+
+## Usage
+
+```py
+from allalgorithms.sorting import quicksort
+
+arr = [77, 2, 10, -2, 1, 7]
+
+print(quicksort(arr))
+# -> [-2, 1, 2, 7, 10, 77]
+```
+
+## API
+
+```
+quicksort(array)
+```
+
+> Returns a sorted array
+
+##### Params:
+
+- `array`: Sorted Array
diff --git a/docs/sorting/shell-sort.md b/docs/sorting/shell-sort.md
@@ -0,0 +1,29 @@
+# Selection Sort
+
+In computer science, shell sort improves upon insertion sort by moving out of order elements more than one position at a time. It has a best case O(n log n) time complexity, and for other cases, it depends on the gap sequence. According to Poonen Theorem, worst case complexity for shell sort is Θ(NlogN)^2/(log logN)^2) or Θ(NlogN)^2/log logN) or Θ(N(logN)^2) or something in between.
+## Install
+
+```
+pip install allalgorithms
+```
+
+## Usage
+
+```py
+from allalgorithms.sorting import shell_sort
+
+arr = [77, 2, 10, -2, 1, 7]
+
+print(shell_sort(arr))
+# -> [-2, 1, 2, 7, 10, 77]
+```
+
+## API
+
+### selection_sort(array)
+
+> Returns a sorted array
+
+##### Params:
+
+- `array`: Unsorted Array
diff --git a/docs/string/hamming-dist.md b/docs/string/hamming-dist.md
@@ -0,0 +1,32 @@
+# Hamming Distance
+
+In informatics, Hamming distance is the number of positions where the characters differ between two strings of equal length
+
+## Install
+
+```
+pip install allalgorithms
+```
+
+## Usage
+
+```
+>>> from allalgorithms.sorting import hamming_dist
+
+>>> hamming_dist("hello world", "hello wario")
+3
+```
+
+## API
+
+### hamming_dist(seq1, seq2)
+
+> Returns an integer
+
+> Raises a ValueError if strings are of unequal length
+
+##### Params:
+
+- `seq1`: first string to compare
+- `seq2`: second string to compare
+
diff --git a/readme.md b/readme.md
@@ -61,7 +61,7 @@ print(binary_search(arr, 3))
   - [Binary Search](https://python.allalgorithms.com/searches/binary-search)
   - [Fibonacci Search](https://python.allalgorithms.com/searches/fibonacci-search)
   - [Jump Search](https://python.allalgorithms.com/searches/jump-search)
-  
+
 - ### Sorting
   - [Bubble Sort](https://python.allalgorithms.com/sorting/bubble-sort)
   - [Cocktail Shaker Sort](https://python.allalgorithms.com/sorting/cocktail-shaker-sort)
@@ -75,7 +75,7 @@ print(binary_search(arr, 3))
 
 # Related
 
-- [allalgorithms-javascript](https://github.com/abranhe/allalgorithms-javascript): All ▲lgorithms Javascript library
+- [allalgorithms-js](https://github.com/abranhe/allalgorithms-js): All ▲lgorithms Javascript library
 
 # Maintainers
 
diff --git a/tests/test_sorting.py b/tests/test_sorting.py
@@ -8,7 +8,8 @@
     pigeonhole_sort,
     stooge_sort,
     cocktail_shaker_sort,
-    tree_sort
+    tree_sort,
+    shell_sort,
 )
 
 
@@ -37,6 +38,8 @@ def test_cocktail_shaker_sort(self):
     def tree_sort(self):
         self.assertEqual([-44, 1, 2, 3, 7, 19], tree_sort([7, 3, 2, 19, -44, 1]))
 
+    def test_shell_sort(self):
+        self.assertEqual([-44, 1, 2, 3, 7, 19], shell_sort([7, 3, 2, 19, -44, 1]))
 
 if __name__ == "__main__":
     unittest.main()
