Merge pull request raviprakashdev#62 from akanksha0820/master

raviprakashdev · web-flow · commit f46c845858c8 · 2020-10-16T22:47:57.000+05:30
Binary Instertion Sort
diff --git a/BinaryInsertionSort.py b/BinaryInsertionSort.py
@@ -0,0 +1,36 @@
+class Sort:
+    def __init__(self, array):
+        self.array = array
+
+    def binary_insertion_sort(self):
+        for i in range(1, len(self.array)):
+            key = self.array[i]
+            pos = self.binary_search(key, 0, i) + 1
+            for k in range(i, pos, -1):
+                self.array[k] = self.array[k - 1]
+            self.array[pos] = key
+        return self.array
+ 
+    def binary_search(self, element, first, last):
+        if last - first <= 1:
+            if element < self.array[first]:
+                return first - 1
+            else:
+                return first
+        mid = (first + last)//2
+        if self.array[mid] < element:
+            return self.binary_search(element, mid, last)
+        elif self.array[mid] > element:
+            return self.binary_search(element, first, mid)
+        else:
+            return mid
+            
+def main():
+    array = list(map(int, input("Enter unsorted array: ").split(' ')))
+    obj = Sort(array)
+    sorted_array = obj.binary_insertion_sort()
+    print("Sorted Array: ", end = '')
+    print(*sorted_array)
+
+if __name__ == "__main__":
+    main()     
