Data Structures and Algorithims with python.
Tags: python, datascience, algorithms, webdev
Published: 2022-02-21 18:25:31

>**Data Structures** basically describes how we can ogarnise  and stored in memory when a program processes it.For example, we can store a list of items having the same data-type using the array data structure.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8adxoqosnaminmrk646x.png)
>**An Algorithm** on the other hand, is step by step set of instruction to process the data for a specific purpose. So, an algorithm uterlises various data structures in a logical way to solve a specific computing problem.This is a very important concept in computer science .It gives us more insight on the data we are working with.It enables data scientists to make better machine learning predictions.This is however a challenging topic to most people in the tech industry , according to most people.We are going to look at various python data structures in python and their code examples.  
>####Lists
The list is a most versatile datatype available in Python which can be written as a list of comma-separated values (items) between square brackets.Lists are mutable and ordered. It can contain a mix of different data types.
```
list1 = ['chicken', 'pizza', 2022, 2000]
list2 = [1, 2, 3, 4, 5 ]
list3 = ["a", "b", "c", "d"]
```
>We can access values in a list using their index.
**NOTE**: we start counting from 0
```
print (list1[0]) #prints the element in the 0 index
```
>We also use the .append() method to add new items into the list eg
```
list2.append(6) #add 6 to the existing list2
```
>Incase you want to add to a specific place in the list ,we do it as follows
```
list3[2] = "e" # returns ["a", "b", "e", "d"]
```
>Some basic list operations include:

1. len([1, 2, 3]) resulting to 3 which tests the Length
2. [1, 2, 3] + [4, 5, 6]resulting to[1, 2, 3, 4, 5, 6]|Concatenation
3. ['Hi!'] * 3 resulting to ['Hi!', 'Hi!', 'Hi!'] which tests Repetition
4. 3 in [1, 2, 3] resulting to True which tests Membership
5. for x in [1, 2, 3]:print x resulting to 1 2 3 which tests Iteration

>####Dictionaries
Dictionary is a mutable and unordered data structure. It permits storing a pair of items (i.e. keys and values).Each key is separated from its value by a colon (:), the items are separated by commas, and the whole thing is enclosed in curly braces. An empty dictionary without any items is written with just two curly braces, like this − {}.
Keys are unique within a dictionary while values may not be. The values of a dictionary can be of any type, but the keys must be of an immutable data type such as strings, numbers, or tuples.
*<u>Accessing Values in Dictionary<u>*
To access dictionary elements, you can use the familiar square brackets along with the key to obtain its value.
Example:
```
dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Python'}
print "dict['Name']: ", dict['Name']
print "dict['Age']: ", dict['Age']
```
>When the above code is executed, it produces the following result :
```
dict['Name']:  Marrie
dict['Age']:  27
```
>If we attempt to access a data item with a key, which is not part of the dictionary, we get an error as follows:
Example
```
#Using the data above.
print "dict['Alice']: ", dict['Alice']
```
>When the above code is executed, it produces the following result :
```
dict['Alice']:
Traceback (most recent call last):
   File "test.py", line 4, in <module>
      print "dict['Alice']: ", dict['Alice'];
KeyError: 'Alice'
```
><u>*Updating Dictionary*</u>
You can update a dictionary by adding a new entry or a key-value pair, modifying an existing entry, or deleting an existing entry as shown below in the simple example:
```
dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Python'}
dict['Age'] = 28; # update existing entry
dict['School'] = "LuxAcademy"; # Add new entry

print "dict['Age']: ", dict['Age']
print "dict['School']: ", dict['School']
```
>When the above code is executed, it produces the following result :
```
dict['Age']:  28
dict['School']:LuxTech
```
><u>*Delete Dictionary Elements*</u>
You can either remove individual dictionary elements or clear the entire contents of a dictionary. You can also delete entire dictionary in a single operation.
To explicitly remove an entire dictionary, just use the del statement.
```
dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Python'}
del dict['Name']; # remove entry with key 'Name'
dict.clear();     # remove all entries in dict
del dict ;        # delete entire dictionary

print "dict['Age']: ", dict['Age']
print "dict['School']: ", dict['School']
```
>**Note** −that an exception is raised because after del dict dictionary does not exist any more:
```
dict['Age']:
Traceback (most recent call last):
   File "test.py", line 8, in <module>
      print "dict['Age']: ", dict['Age'];
TypeError: 'type' object is unsubscriptable
```

><u>*Properties of Dictionary Keys*</u>
Dictionary values have no restrictions. They can be any arbitrary Python object, either standard objects or user-defined objects. However, same is not true for the keys.
There are two important points to remember about dictionary keys:
*More than one entry per key not allowed. Which means no duplicate key is allowed. When duplicate keys encountered during assignment, the last assignment wins.
```
dict = {'Name': 'Marrie', 'Age': 27, 'Name': 'Python'}
print "dict['Name']: ", dict['Name']
```
>When the above code is executed, it produces the following result:
```
dict['Name']:  Python
```
*Keys must be immutable. Which means you can use strings, numbers or tuples as dictionary keys but something like ['key'] is not allowed.
An example is as follows :
```
dict = {['Name']: 'Marrie', 'Age': 27}
print "dict['Name']: ", dict['Name']
```
>When the above code is executed, it produces the following result :
```
Traceback (most recent call last):
   File "test.py", line 3, in <module>
      dict = {['Name']: 'Marrie', 'Age': 27};
TypeError: list objects are unhashable
```
>####Tuples
A tuple is another container. It is a data type for immutable ordered sequences of elements. Immutable because you can’t add and remove elements from tuples, or sort them in place.
Creating a tuple is as simple as putting different comma-separated values. Optionally you can put these comma-separated values between parentheses also.
For example:
```
tuple_one = ('python', 'javascript', 'c++', 2000);
tuple_two = (1, 2, 3, 4, 5 );
tuple_3 = "a", "b", "c", "d";
```
>The empty tuple is written as two parentheses containing nothing −
```
languages = ();
```
>To write a tuple containing a single value you have to include a comma, even though there is only one value −
```
tup1 = (50,);
```
>Like string indices, tuple indices start at 0, and they can be sliced, concatenated, and so on.
<u>*Accessing Values in Tuples*</u>
To access values in tuple, use the square brackets for slicing along with the index or indices to obtain value available at that index.
For example
```
tuple_one = ('python', 'javascript', 'c++', 2000);
tuple_two = (1, 2, 3, 4, 5 );
print "tuple_one[0]: ", tuple_two[0];
print "tuple_two[1:5]: ",tuple_two[1:5];
```
>When the above code is executed, it produces the following result :
```
tuple_one[0]:  python
tuple_two[1:5]:  [2, 3, 4, 5]
```
><u>*Updating Tuples*</u>
Tuples are immutable which means you cannot update or change the values of tuple elements. You are able to take portions of existing tuples to create new tuples as the following example demonstrates −
```
tup1 = (12, 34.56);
tup2 = ('abc', 'xyz');

# Following action is not valid for tuples
# tup1[0] = 100;

# So let's create a new tuple as follows
tup3 = tup1 + tup2;
print tup3;
```
>When the above code is executed, it produces the following result:
```
(12, 34.56, 'abc', 'xyz')
```
><u>*Delete Tuple Elements*</u>
Removing individual tuple elements is not possible. There is, of course, nothing wrong with putting together another tuple with the undesired elements discarded.
To explicitly remove an entire tuple, just use the del statement.
For example:
```
tuple_one = ('python', 'javascript', 'c++', 2000);
print tuple_one;
del tuple_one;
print "After deleting tup : ";
print tuple_one;
```
>Note − an exception raised, this is because after del tup tuple does not exist anymore.
This produces the following result:
```
('python', 'javascript', 'c++', 2000)
```
>After deleting tup :
```
Traceback (most recent call last):
   File "test.py", line 9, in <module>
      print tuple_one;
NameError: name 'tuple_one' is not defined.
```
Assuming our file name is "test.py"
><u>*Basic Tuples Operations*</u>
Tuples respond to the + and * operators much like strings; they mean concatenation and repetition here too, except that the result is a new tuple, not a string.
In fact, tuples respond to all of the general sequence operations we used on strings in the prior chapter.

1. len((1, 2, 3)) which results to 3 used to test Length
2. (1, 2, 3) + (4, 5, 6)which results to(1, 2, 3, 4, 5,6) and is used to test Concatenation
3. ('Hi!',) * 4 which results to('Hi!', 'Hi!', 'Hi!', 'Hi!') and is used to test Repetition
4.  3 in (1, 2, 3) which results to True and is used to test Membership
5. for x in (1, 2, 3): print x which results to 1 2 3 and is used to test Iteration

>####Sets
Set is a mutable and unordered collection of unique elements. It can permit us to remove duplicate quickly from a list.The sets in python are typically used for mathematical operations like union, intersection, difference and complement etc. 
A Python set is similar to this mathematical definition with below additional conditions:
*The elements in the set cannot be duplicates.
*The elements in the set are immutable(cannot be modified) but the set as a whole is mutable.
*There is no index attached to any element in a python set. So they do not support any indexing or slicing operation.

><u>*Creating a set*</u>
A set is created by using the set() function or placing all the elements within a pair of curly braces.

```
Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
Months={"Jan","Feb","Mar"}
Dates={21,22,17}
print(Days)
print(Months)
print(Dates)
```

>Note how the order of the elements has changed in the result.

```
set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
set(['Jan', 'Mar', 'Feb'])
set([17, 21, 22])
```
><u>*Accessing Values in a Set*</u>
We cannot access individual values in a set. We can only access all the elements together as shown above. But we can also get a list of individual elements by looping through the set.

```
#Considering the data above.
Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
 
for d in Days:
   print(d)
```
>When the above code is executed, it produces the following :

```
Wed
Sun
Fri
Tue
Mon
Thu
Sat
```

><u>*Adding Items to a Set*</u>
We can add elements to a set by using add() method. Remember,there is no specific index attached to the newly added element.

```
#Adding to the data above. 
Days.add("Sun")
print(Days)
```

 >results

```
set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
```

><u>*Removing Item from a Set*</u>
We can remove elements from a set by using discard() method. 
Example

```
#Using the data above.
Days.discard("Sun")
print(Days)
```

Output

```
set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
```

><u>*Union of Sets*</u>
The union operation on two sets produces a new set containing all the distinct elements from both the sets. In the below example the element “Wed” is present in both the sets.

```
DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA|DaysB
print(AllDays)
```

>Output will be as shown,note the result has only one “wed”.

```
set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
```

><u>*Intersection of Sets*</u>
The intersection operation on two sets produces a new set containing only the common elements from both the sets. In the below example the element “Wed” is present in both the sets.

```
DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA & DaysB
print(AllDays)
```

Output

```
set(['Wed'])
```

><u>*Difference of Sets*</u>
The difference operation on two sets produces a new set containing only the elements from the first set and none from the second set. In the below example the element “Wed” is present in both the sets so it will not be found in the result set.

```
DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA - DaysB
print(AllDays)
```

>Output
When the above code is executed, it produces the following result. Please note the result has only one “wed”.

```
set(['Mon', 'Tue'])
```

><u>*Compare Sets*</u>
We can check if a given set is a subset or superset of another set. The result is True or False depending on the elements present in the sets.
Example

```
DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
SubsetRes = DaysA <= DaysB
SupersetRes = DaysB >= DaysA
print(SubsetRes)
print(SupersetRes)
```

Output

```
True
True
```


>####Queue
The queue is a linear data structure where elements are in a sequential manner. It follows the F.I.F.O mechanism that means first in first out. 
Below the aspects that characterize a queue.
Two ends:
    *front → points to starting element
    *rear → points to the last element
There are two operations:
*enqueue → inserting an element into the queue. It will be       done at the rear.
*dequeue → deleting an element from the queue. It will be done at the front.
There are two conditions:
*overflow → insertion into a queue that is full
*underflow → deletion from the empty queue
Lets see a code example of this:
```
class myqueue:
    
    def __init__(self):
        self.data = []
        
    def length(self):
        return len(self.data)
    
    def enque(self, element): # put the element in the queue
        if len(self.data) < 5:
            return self.data.append(element)
        else:
            return "overflow"
        
    def deque(self): # remove the first element that we have put in queue
        if len(self.data) == 0:
             return "underflow"
        else:
            self.data.pop(0)
            
b = myqueue()
b.enque(2) # put the element into the queue
b.enque(3)
b.enque(4)
b.enque(5)
print(b.data)
b.deque()# # remove the first element that we have put in the queue
print(b.data)
```
This will procuce the  following results. 
```
[2, 3, 4, 5]
[3, 4, 5]
```
>####Stack
In the english dictionary the word stack means arranging objects on over another. Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
In the following program we implement it as add and and remove functions. We declare an empty list and use the append() and pop() methods to add and remove the data elements.
*Pushing into a Stack*
Example
```
class Stack:
   def __init__(self):
      self.stack = []

   def add(self, dataval):
# Use list append method to add element
      if dataval not in self.stack:
         self.stack.append(dataval)
         return True
      else:
         return False
# Use peek to look at the top of the stack
   def peek(self):     
	   return self.stack[-1]

AStack = Stack()
AStack.add("Mon")
AStack.add("Tue")
AStack.peek()
print(AStack.peek())
AStack.add("Wed")
AStack.add("Thu")
print(AStack.peek())
```
Output
```
Tue
Thu
```
>*POP from a Stack*
As we know we can remove only the top most data element from the stack, we implement a python program which does that. The remove function in the following program returns the top most element. We check the top element by calculating the size of the stack first and then use the in-built pop() method to find out the top most element.
```
class Stack:
   def __init__(self):
      self.stack = []

   def add(self, dataval):
# Use list append method to add element
      if dataval not in self.stack:
         self.stack.append(dataval)
         return True
      else:
         return False
        
# Use list pop method to remove element
   def remove(self):
      if len(self.stack) <= 0:
         return ("No element in the Stack")
      else:
         return self.stack.pop()

AStack = Stack()
AStack.add("Mon")
AStack.add("Tue")
AStack.add("Wed")
AStack.add("Thu")
print(AStack.remove())
print(AStack.remove())
```
Output:
```
Thu
Wed
```
>###Linked list
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2ajjq426s60mxxk5qtvn.png)
>Now lets create a linked list
```
class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3
```
>*Traversing a Linked List*
Singly linked lists can be traversed in only forward direction starting form the first data element. We simply print the value of the next data element by assigning the pointer of the next node to the current data element.
Example
```
class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None

   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()
```
Output:
```
Mon
Tue
Wed
```
><u>*Insertion in a Linked List*</u>
Inserting element in the linked list involves reassigning the pointers from the existing nodes to the newly inserted node. Depending on whether the new data element is getting inserted at the beginning or at the middle or at the end of the linked list, we have the below scenarios.
<u>*Inserting at the Beginning*</u>
This involves pointing the next pointer of the new data node to the current head of the linked list. So the current head of the linked list becomes the second data element and the new node becomes the head of the linked list.
Example
```
class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None
# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval
   def AtBegining(self,newdata):
      NewNode = Node(newdata)

# Update the new nodes next val to existing node
   NewNode.nextval = self.headval
   self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")
list.listprint()
```
Output:
```
Sun
Mon
Tue
Wed
```
<u>Inserting at the End</u>
This involves pointing the next pointer of the the current last node of the linked list to the new data node. So the current last node of the linked list becomes the second last data node and the new node becomes the last node of the linked list.
Example
```
class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None
class SLinkedList:
   def __init__(self):
      self.headval = None
# Function to add newnode
   def AtEnd(self, newdata):
      NewNode = Node(newdata)
      if self.headval is None:
         self.headval = NewNode
         return
      laste = self.headval
      while(laste.nextval):
         laste = laste.nextval
      laste.nextval=NewNode
# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtEnd("Thu")

list.listprint()
```
Output
```
Mon
Tue
Wed
Thu
```
><u>*Inserting in between two Data Nodes*</u>
This involves changing the pointer of a specific node to point to the new node. That is possible by passing in both the new node and the existing node after which the new node will be inserted. So we define an additional class which will change the next pointer of the new node to the next pointer of middle node. Then assign the new node to next pointer of the middle node.
```
class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None
class SLinkedList:
   def __init__(self):
      self.headval = None

# Function to add node
   def Inbetween(self,middle_node,newdata):
      if middle_node is None:
         print("The mentioned node is absent")
         return

      NewNode = Node(newdata)
      NewNode.nextval = middle_node.nextval
      middle_node.nextval = NewNode

# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

list.headval.nextval = e2
e2.nextval = e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()
```
Output:
```
Mon
Tue
Fri
Thu
```
><u>*Removing an Item*<u>
We can remove an existing node using the key for that node. In the below program we locate the previous node of the node which is to be deleted.Then, point the next pointer of this node to the next node of the node to be deleted.
Example
```
class Node:
   def __init__(self, data=None):
      self.data = data
      self.next = None
class SLinkedList:
   def __init__(self):
      self.head = None

   def Atbegining(self, data_in):
      NewNode = Node(data_in)
      NewNode.next = self.head
      self.head = NewNode

# Function to remove node
   def RemoveNode(self, Removekey):
      HeadVal = self.head
         
      if (HeadVal is not None):
         if (HeadVal.data == Removekey):
            self.head = HeadVal.next
            HeadVal = None
            return
      while (HeadVal is not None):
         if HeadVal.data == Removekey:
            break
         prev = HeadVal
         HeadVal = HeadVal.next

      if (HeadVal == None):
         return

      prev.next = HeadVal.next
         HeadVal = None

   def LListprint(self):
      printval = self.head
      while (printval):
         print(printval.data),
         printval = printval.next

llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()
```
Output:
```
Thu
Wed
Mon
```
>####Algorithims
>Algorithms are instructions that are formulated in a finite and sequential order to solve problems.
The word algorithm derives itself from the 9th-century Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī, whose name was Latinized as Algorithmi. Al-Khwārizmī was also an astronomer, geographer, and a scholar in the House of Wisdom in Baghdad.

As you already know algorithms are instructions that are formulated in a finite and sequential order to solve problems.

When we write an algorithm, we have to know what is the exact problem, determine where we need to start and stop and formulate the intermediate steps.

>There are three main approaches to solve algorithms:

 *Divide et Impera (also known as divide and conquer) → it divides the problem into sub-parts and solves each one separately
  *Dynamic programming → it divides the problem into sub-parts remembers the results of the sub-parts and applies it to similar ones
   *Greedy algorithms → involve taking the easiest step while solving a problem without worrying about the complexity of the future steps

><u>*Tree Traversal Algorithm*</u>
Trees in python are non-linear data structures. They are characterized by roots and nodes. I take the class I constructed before for the binary tree.

Tree Traversal refers to visiting each node present in the tree exactly once, in order to update or check them.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t8qq4zja9nqqy134i27o.png)

```
# create the class Node and the attrbutes 
class Node:
    def __init__(self, letter):
        self.childleft = None
        self.childright = None
        self.nodedata = letter

# create the nodes for the tree
root = Node('A')
root.childleft = Node('B')
root.childright = Node('C')
root.childleft.childleft = Node('D')
root.childleft.childright = Node('E')
```

>There are three types of tree traversals:
*In-order traversal → refers to visiting the left node, followed by the root and then the right nodes.
Here D is the leftmost node where the nearest root is B. The right of root B is E. Now the left sub-tree is completed, so I move towards the root node A and then to node C.

```
def InOrd(root):
    if root:
        InOrd(root.childleft)
        print(root.nodedata)
        InOrd(root.childright)
InOrd(root)
```

>Out:

```
D
B
E
A
C
```

>*Pre-order traversal → refers to visiting the root node followed by the left nodes and then the right nodes.
In this case, I move to the root node A and then to the left child node B and to the sub child node D. After that I can go to the nodes E and then C.

```
def PreOrd(root):
    if root:
        print(root.nodedata)
        PreOrd(root.childleft)
        PreOrd(root.childright)
PreOrd(root)
```

>out:

```
A
B
D
E
C
```

>*Post-order traversal → refers to visiting the left nodes followed by the right nodes and then the root node.
I go to the most left node which is D and then to the right node E. Then, I can go from the left node B to the right node C. Finally, I move towards the root node A.

```
def PostOrd(root):
    if root:
        PostOrd(root.childleft)
        PostOrd(root.childright)
        print(root.nodedata)
PostOrd(root)
```

>out:

```
D
E
B
C
A
```

><u>*Sorting Algorithm*</u>
The sorting algorithm is used to sort data in some given order. It can be classified in Merge Sort and Bubble Sort.
*Merge Sort → it follows the divide et Impera rule. The given list is first divided into smaller lists and compares adjacent lists and then, reorders them in the desired sequence. So, in summary from unordered elements as input, we need to have ordered elements as output. Below, the code with each step described.

```
def merge_sort(ourlist, left, right): #left and right corresponds to starting and ending element of ourlist
    if right -left > 1: # check if the length of ourlist is greater than 1
        middle = (left + right) // 2 # we divide the length in two parts
        merge_sort(ourlist, left, middle) # recursevely I call the merge_sort function from left to middle
        merge_sort(ourlist, middle, right) # then from middle to right
        merge_list(ourlist, left, middle, right) # finally I create ourlist in complete form(left, middle and right) 
        
def merge_list(ourlist, left, middle, right):# I create the function merged_list
    leftlist = ourlist[left:middle] # I define the leftlist
    rightlist = ourlist[middle:right] # I define the right list
    k = left # it is the the temporary variable
    i = 0 # this variable that corespond to the index of the first group help me to iterate from left to right
    j = 0 # this variable that corespond to the index of the second group help me to iterate from left to right
    while (left + i < middle and middle+ j < right): # the condition that I want to achive before to stop my iteration
        if (leftlist[i] <= rightlist[j]): #if the element in the leftlist is less or equal to the element in the rightlist
            ourlist[k] = leftlist[i] # In this case I fill the value of the leftlist in ourlist with index k
            i = i + 1 #now I have to increment the value by 1
        else: # if the above codition is not match
            ourlist[k] = rightlist[j] # I fill the rightlist element in ourlist with index k
            j = j + 1 # I increment index j by 1
        k = k+1 # now I increment the value of k by 1
    if left + i < middle: # check if left + i is less than middle
        ourlist[k] = leftlist[i] # I place all elements of my leftlist in ourlist
        i = i + 1
        k = k + 1
    else: # otherwise if my leftlist is empty
        while k < right: # untill k is less then right
            ourlist[k] = rightlist[j] # I place all elements of rightlist in ourlist 
            j = j + 1
            k = k + 1
            
ourlist = input('input - unordered elements: ').split() # insert the input and split
ourlist = [int(x) for x in ourlist]
merge_sort(ourlist, 0, len(ourlist))
print('output - ordered elements: ')
print(ourlist)
```

Out:

```
input - unordered elements: 15 1 19 93
output - ordered elements: 
[1, 15, 19, 93]
```

*Bubble Sort → it first compares and then sorts adjacent elements if they are not in the specified order.

```
def bubble_sort(ourlist): # I create my function bubble_sort with the argument called ourlist
    b=len(ourlist)-1 # for every list, I will have a minus 1 iteration
    for x in range(b): # for each element in the range of b, I check if they are ordered or not
        for y in range(b-x): 
            if ourlist[y]>ourlist[y+1]: # if one element is greater than the nearest elemnt in the list
                ourlist[y],ourlist[y+1]=ourlist[y+1],ourlist[y] # I have to swap the elemnts, in other words
                                                          # I exchange the position of the two elements
        return ourlist
    
ourlist=[15,1,9,3]
bubble_sort(ourlist)
```

Out:

```
[1, 3, 9, 15]
```
 *Insertion Sort → it picks one item of a given list at the time and places it at the exact spot where it is to be placed.

```
def ins_sort(ourlist):
    for x in range(1, len(ourlist)): # loop for each element starting from 1 to the length of our list
        k = ourlist[x] # element with the index x
        j = x-1 # j is the index previus the index x
        while j >=0 and k < ourlist[j]: # untill each elermnt of the list are less than their previous element my loop don't stop
                ourlist[j+1] = ourlist[j] # the elemnt indexed before the element considered is set to the next one index
                j -= 1 # I decrement index j by 1
        ourlist[j+1] = k # now k is the element in the index j+1
    return ourlist
        
ourlist = [15, 1, 9, 3]
ins_sort(ourlist)
```

out:

```
[1, 3, 9, 15]
```

>There are other Sorting Algorithms like Selection Sort and Shell Sort.

Searching Algorithms

*Searching algorithms are used to seek for some elements present in a given dataset. There are many types of search algorithms such as Linear Search, Binary Search, Exponential Search, Interpolation Search, and so on. In this section, we will see the Linear Search and Binary Search.

 *Linear Search → in a single-dimensional array we have to search a particular key element. The input is the group of elements and the key element that we want to find. So, we have to compare the key element with each element of the group. In the following code, Lets try to seek element 27 in our list.
```
def lin_search(ourlist, key):
    
    for index in range(0, len(ourlist)):
        if (ourlist[index] == key):
            return  index
    else:
        return "not fund"
    
ourlist = [15, 1, 9, 3]

lin_search(ourlist, 27)
```
out:
```
'not fund'
```
 *Binary Search → in this algorithm, we assume that the list is in ascending order. So, if the value of the search key is less than the element in the middle of the list, we narrow the interval to the lower half. Otherwise, we narrow to the upper half. We continue our check until the value is found or the list is empty.
```
def bin_search(ourlist, key):
    left = 0 # I assign left position to zero
    right = len(ourlist)-1 # I assign right position by defining the length of ourlist minus one 
    matched = False
    while(left<=right and not matched): # the loop will continue untill the left element is less or equal to the right element and the matched is True
        mid = (left+right)//2 # I find the position of the middle element
        if ourlist[mid] == key: # if the middle element correponds to the key element
             matched = True
        else: #otherwise 
            if key < ourlist[mid]: # if key element is less than the middle element
                right = mid - 1 #I assign the position of the right element as mid - 1
            else: #otherwise
                left = mid + 1 #left position will become the middle position plus 1
    return matched

print(bin_search([1, 3, 9, 15], 17))
print(bin_search([1, 3, 9, 15], 3))
```
out:
```
False
True
```