Searching and Sorting
Searching
Searching algorithms are used to search for a
particular item in data structure where it is stored. Searching is generally
classified into two categories Sequential search and Interval search.
Sequential search- In this we traverse array or list
sequentially and check each element present in the list. Example- Linear
search.
Interval search- We need not to check for each
element. These algorithms are more efficient than Sequential search. Example-
Binary search.
Linear search
Linear search check each element present in the list.
It start traversing from start to end and if the element present in the list it
returns it.
Code-> a=[1,3,5,2,7]
key_element= 5
flag=0
for i in a:
if(i==key_element):
flag=1
break;
if(flag==1):
print("Key
element is present in the list")
else:
print("Key
element is not present in the list")
output-> Key
element is present in the list
Time complexity of linear search is O(n)
and Space complexity is O(1)
Binary search
The elements in the list must be sorted to apply the
binary search algorithm. If elements are not sorted then sort them first.
i.
In Binary search we use three
pointers left, right and middle.
ii.
Initially start left pointer from 0th
index and right from last index i.e. length_of_list –
1
iii.
Calculate middle index by using
formula middle= (left-right)/2
iv.
Check the list element at middle
index
o
if it is equal to the key element
return this index else
o
if
this element is greater than the key element then set right index to mid-1.
o
if this element is
smaller than the key element then set left index to left+1.
v.
Go to step ii. Only if left index is
smaller or equal to right index else return
-1(means key element is not present
in the list)
Code-> a=[1, 3, 5, 6, 7, 9, 10]
key_element=
9
flag=0
left=0
right=len(a)-1
while(left<=right):
middle=(left+right)//2
if a[middle]==key_element:
print("key
element is present at index ",str(middle))
flag=1
break
elif
a[middle]>key_element:
right=middle-1
else:
left=middle+1
if
flag==0:
print("Key
element is not prresent in the list")
output->
key element is present at index 5
Sorting
Sorting means arranging data in a particular manner
example in ascending or descending order. We do sorting so that data searching
can be optimized. Some example of sorting algorithms are Bubble sort, Insertion
sort, Selection sort etc.
Bubble sort
It is a simple sorting technique that repeatedly swaps
the adjacent elements of list if they are in wrong order.
Example-> First pass
2 5
4 1 3
2 5 4 1 3 swap 5 and 4
2
4 5 1 3 swap 5 and 1
2
4 1 5 3 swap 5 and 3
2
4 1 3 5
Second
pass
2 4 1 3 5
2
4 1 3 5 swap 4 and 1
2
1 4 3 5 swap 4 and 3
2
1 3 4 5
Third
pass
2 1 3 4 5 swap 2 and 1
1
2 3 4 5
1
2 3 4 5
1
2 3 4 5
Code-> arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
for i in range(n-1):
for j in range(0,
n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1]
= arr[j+1], arr[j]
print
("Sorted array is:")
for x
in arr:
print(x,end=' ')
output-> Sorted
array is:
11 12 22 25 34 64 90
Insertion
Sort
Insertion sort is a simple sorting algorithm that builds the
final sorted array one item at a time.
It starts from arr[1] element and traverse till arr[n].
Compare the current element with all the previous elements.
If the key element is smaller than its
predecessor, compare it to the elements before. Move the greater elements one
position up to make space for the swapped element.
Code-> arr = [12, 11, 13, 5, 6]
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0
and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
for i in range(len(arr)):
print (arr[i], end=" ")
output-> 5 6 11 12 13
Selection Sort
It sorts the array by repeatedly finding
the minimum element from unsorted part and putting it at the beginning.
It maintains two subarrays one is sorted
subarray and second is unsorted subarray.
Code-> A = [64, 25, 12, 22, 11]
for i in
range(len(A)):
min_idx
= i
for j
in range(i+1, len(A)):
if
A[min_idx] > A[j]:
min_idx
= j
A[i],
A[min_idx] = A[min_idx], A[i]
for i in
range(len(A)):
print(A[i], end=" ")
output-> 11 12 22 25 64
Function
Function is a block of code which
only executes when we call it. In python we can write a function using def
keyword. We can pass parameters into a function.
def function_name():
We can call the function by using
function name followed by parenthesis.
Function_name()
Example-> def my_func():
print(“Hello”)
my_func()
output-> Hello
Passing Arguments
It is the information that is passed to the function.
In the function below the function has one argument (x).
def my_func(x):
x=x+5
print(x)
my_func(5)
output-> 10
A function must be called with correct number of
arguments. Meaning if function is taking two arguments, we have to call it by
using two 2 arguments only, not less, and not more.
Example-> def: my_func(x,y): #2 arguments
print(x)
print(y)
my_func(5,4) # passing two arguments only
Global
variable
A variable which is declared outside the function has
scope in the entire program and is known as global variable. A global variable
can be accessed inside or outside of the function.
Example-> x=5 #global variable
def func():
print(“x inside :”+ str(x))
func(x)
print(“x outside :”+ str(x))
output-> x inside: 5
x outside: 5
What if we want to change x inside the function.
x=5 #global variable
def func():
x=x+2 #not allowed
print(x)
func()
This will give error because python treats x as a
local variable and it is not defined inside the function.
To make this work, we use global keyword.
x=5 #global variable
def func():
global x
x=x+2 #not allowed
print(x)
func()
output-> 7
Local
variable
A variable which is declared inside the function and
are only accessed inside the function are known as Local variable.
Example-> def my_func():
x=
4
print(x)
my_func()
output-> 4
If we try to access local variable from outside the
function it will generate error.
Example-> def my_func():
x=
4
print(x) #Not
allowed
output-> NameError: name 'x' is not defined
Programs on
Function
Q1) Write a Python function to sum all the numbers in
a list.
def
sum(numbers):
total = 0
for x in numbers:
total += x
return total
print(sum((8,
2, 3, 0, 7)))
output-> 20
Q2) What is the output of
following code?
x = "global "
def
function():
global x
y = "local"
x = x * 2
print(x)
print(y)
function()
output-> global global
local
Q3) What is the output of
following code?
x = 5
def my_func():
x = 10
print("local
x:", x)
my_func()
print("global
x:", x)
output-> local x: 10
global x: 5
Q4) Write a Python program to print the even numbers from a given list.
def
is_even_num(l):
enum = []
for
n in l:
if n % 2 == 0:
enum.append(n)
return
enum
print(is_even_num([1, 2, 3, 4, 5, 6, 7, 8,
9]))
output-> [2, 4, 6, 8]
Q5) Write a Python
function to create and print a list where the values are square of numbers
between 1 and 30 (both included).
def printValues():
l = list()
for i in range(1,21):
l.append(i**2)
print(l)
printValues()
output->
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324,
361, 400]
Recursion
Recursion is the
process of function calling itself. We know that a function can call other
functions but it is also possible to call itself. A function call to itself is
called as recursive call.
Example-> def recursive_func(x):
if
x==0:
return
print(x,
end=" ")
recursive_func(x-1)
recursive_func(5)
output-> 5
4 3 2 1
-
Recursive
functions make the code look clean and elegant.
-
A
complex task can be broken down into simpler sub-problems using recursion.
-
Sequence
generation is easier with recursion than using some nested iteration.
Programs on recursion
Q1) Write a program
to calculate factorial of a number in python.
def factorial(x):
if
x == 1:
return 1
else:
return (x * factorial(x-1))
num = 3
print("The factorial of",
num, "is", factorial(num))
output->
The factorial of 3 is 6
Q2) Write a program
to obtain Fibonacci sequence in python.
def recursive_fibonacci(n):
if
n <= 1:
return n
else:
return(recursive_fibonacci(n-1) + recursive_fibonacci(n-2))
n_terms = 10
print("Fibonacci
series:")
for i
in range(n_terms):
print(recursive_fibonacci(i))
output->
Fibonacci series:
0 1 1 2 3 5 8 13
21 34
Lambda function
In Python, an anonymous
function is a function that is defined without a name. A lambda function can
take any number of arguments, but can only have one expression.
Syntax: lambda arguments :
expression
Example-> x = lambda a : a
+ 10
print(x(5))
output->
15
Lambda function can
take any number of arguments.
Example-> x = lambda a, b, c :
a + b + c
print(x(5, 6, 2))
Output-> 13
We use lambda functions when we require a nameless function
for a short period of time.
Programs on Lambda function
Q1) Create a lambda function that takes one parameter (a) and
returns it.
x = lambda a : a
Q2) What is the output of below
code.
adder = lambda x, y: x + y
print (adder (1, 2))
output-> 3
Q3) Write lambda function to calculate cube of a number.
lambda_cube = lambda y: y*y*y
print(lambda_cube(5))
output-> 125
Q4) Write a python program to select all the numbers greater
than 5 from a list of numbers using lambda function.
li = [5, 6, 2, 4, 8, 10]
final_list = list(filter(lambda
x: x>5 , li))
print(final_list)
output-> [6, 8, 10]
Note-> The filter() function in
Python takes in a function and a list as arguments. This offers an elegant way
to filter out all the elements of a sequence “sequence”, for which the function
returns True.
Build in functions
The Python built-in functions are defined as the functions
whose functionality is pre-defined in Python. The python interpreter has
several functions that are always present for use. These functions are known as
Built-in Functions. There are several build in functions in python some of
those are:
abs() Returns the absolute
value of a number
Example-> x = abs(-7.25) output-> 7.25
all() Returns True if all items in an iterable
object are true
Example-> mylist = [True, True,
True]
x = all(mylist)
print(x)
output-> True
bool() Returns the boolean value of the specified object
Example-> x = bool(1)
print(x)
output-> True
dict() Returns a dictionary (Array)
Example-> x = dict(name
= "John", age = 36, country = "Norway")
print(x)
output-> {'name': 'John', 'age': 36,
'country': 'Norway'}
filter() Use a filter function to
exclude items in an iterable object
Example-> ages = [5, 12, 17, 18, 24, 32]
def myFunc(x):
if x < 18:
return False
else:
return True
adults = filter(myFunc,
ages)
for x in adults:
print(x)
output-> 18
24
32
max() Returns the largest item
in an iterable
Example-> x = max(5, 10)
print(x)
output-> 10
Some more important build in functions are:
pow(), range(), round(), set(), input(), print(), sum(),
tuple() etc.