Merge pull request geekquad#22 from vlx01/vlx01/sublist-search

geekquad · web-flow · commit 6c9bf9f328ce · 2020-10-01T00:40:48.000+05:30
Vlx01/sublist search
diff --git a/python/searching/sublist-search.py b/python/searching/sublist-search.py
@@ -0,0 +1,76 @@
+# SUBLIST SEARCH
+
+#Checks whether the first list is present in second list or not.
+
+#Taking fisrt node of second list
+class Nodes:
+    def __init__(self, value = 0):
+        self.value = value
+        self.next = None
+
+#Returns TRUE if fisrt list is in the second list.
+def findList(first,second):
+
+    if not first or not second:
+        return False
+
+    if not first and not second:
+        return True
+
+    p1 = first
+    p2 = second
+    # Traversing the second LL
+    # Checking nodes from both lists
+    while p2:
+        #Initializing p2 with current node of second LL
+        p2 = second
+#Starting our matching
+        while p1:
+            # If second LL become empty and
+            # first not, return False,
+            if not p2:
+                return False
+
+            #if nodes match, increase the pointers
+            #for checking the next nodes
+            elif p1.value == p2.value:
+                p1 = p1.next
+                p2 = p2.next
+
+            #If nodes don't match further or the
+            #p1 is None/empty
+            else:
+                break
+            #Checks
+
+        if not p1:       #p1 is empty/None
+            return True  #Completely traversed and matched
+
+        #If p1 is not empty/None
+        p1 = first #bringing back to fisrt
+        second = second.next   #increament second node element
+    return False
+
+#Driver Code
+#Enter two linked list
+# Example -
+#node_a: 1-> 2-> 3-> 4
+# node_b: 1->2->1->2->3->4
+node_a = Nodes(1)
+node_a.next = Nodes(2)
+node_a.next.next = Nodes(3)
+node_a.next.next.next = Nodes(4)
+
+node_b = Nodes(1)
+node_b.next = Nodes(2)
+node_b.next.next = Nodes(1)
+node_b.next.next.next = Nodes(2)
+node_b.next.next.next.next = Nodes(3)
+node_b.next.next.next.next.next = Nodes(4)
+
+if findList(node_a, node_b):
+    print("LIST FOUND")
+else:
+    print("LIST NOT FOUND")
+
+#OUTPUT : LIST FOUND     
diff --git a/python/sorting/cocktail-shaker-sort.py b/python/sorting/cocktail-shaker-sort.py
@@ -0,0 +1,59 @@
+#Cocktail Shaker Sort
+
+#This is a variation of Bubble Sort
+#Cocktail sort traverses through a given array in both
+#directions alternatively
+
+def cocktailSort(a):
+    n = len(a)
+    swapped = True
+    start = 0
+    end = n-1
+    while (swapped==True):
+
+        #rest swap =False
+        #because it might be true from the
+        #previous iteration
+        swapped = False
+
+        for i in range (start, end): #loop similar to bubble sort
+            if (a[i] > a[i+1]) :
+                a[i], a[i+1]= a[i+1], a[i]
+                swapped=True
+
+        #no change , then array is already sorted
+        if(swapped ==False):
+                 break
+
+        #otherwise reset sp that it can be used in next stage
+        swapped = False
+
+        #move end point back by one
+        #because
+        #item at the end is in its rightful spot
+        end= end-1
+
+        #now, since cocktail shaker traverses from both sides so,
+        #from right to left doing the same
+        #comparision similar to the previous stage
+        for i in range(end-1, start-1,-1):
+            if (a[i] > a[i+1]):
+                a[i], a[i+1] = a[i+1], a[i]
+                swapped = True
+        #increasing starting point
+        #so, the last stage will move the next
+        #smallest number
+        start = start+1
+
+
+#Main/Driver Code
+a = []
+n = int(input("Enter no of elements:"))
+for i in range(0,n):
+    element = int(input())
+    a.append(element)
+
+cocktailSort(a)
+print("Sorted array is:")
+for i in range(len(a)):
+    print ("%d" %a[i]),
