EX – 1.
b
Implement recursive and non-recursive algorithms and study the order of growth from
log2n to n!.
AIM :
To write a python program to implement Non-Recursive algorithm for
permutation and binary search and studying the order of growth from log2n to
n!.
ALGORITHM – PERMUTATION :
STEP – 1 : Start the Program
STEP – 2: Initialize the List:
Start with the input list arr in its sorted order to ensure that the
permutations are generated in lexicographical order.
STEP – 3 : Generate Permutations:
i. Continuously generate the next permutation of the list until all
permutations have been generated.
ii. Use the next_permutation function to modify the list in-place to the
next permutation in lexicographical order.
STEP – 4 : Next Permutation Logic:
i. Find the Rightmost Ascending Pair (k):
Find the largest index k such that arr[k] < arr[k + 1]. If no such index
exists (k == -1), the current permutation is the last permutation, and
the function returns False.
ii. Find the Rightmost Successor to Pivot (l):
Find the largest index l such that arr[l] > arr[k].
iii. Swap k and l:
Swap the elements at indices k and l.
iv. Reverse the Sequence after k:
Reverse the sequence of elements from k + 1 to the end of the list to
get the next permutation in lexicographical order.
STEP – 5 : Stop the Program
PSEUDOCODE – PERMUTATION :
Function next_permutation(arr):
k = length of arr - 2
while k >= 0 and arr[k] >= arr[k + 1]:
k = k - 1
if k == -1:
return False
l = length of arr - 1
while arr[k] >= arr[l]:
l = l - 1
Swap arr[k] and arr[l]
Reverse the sequence arr[k + 1:]
return True
Function generate_permutations(arr):
Sort arr
while True:
Print arr
if not next_permutation(arr):
break
arr = [1, 2, 3]
start_time = current time
generate_permutations(arr)
execution_time = current time - start_time
Print "Execution time: ", execution_time
ALGORITHM – BINARY SEARCH:
STEP – 1: Start the program.
STEP – 2 : Initialization:
o Set two pointers: left to the beginning of the array (0) and right to the
end of the array (len(arr) - 1).
STEP – 3: Iterative Search Process:
o Use a while loop to repeatedly narrow down the search range as long
as left is less than or equal to right.
o Calculate the mid index as the average of left and right using the
formula mid = left + (right - left) // 2 to prevent overflow.
o Compare the Middle Element:
If arr[mid] is equal to the target x, return mid since the target is
found.
If arr[mid] is less than x, this means the target must be in the
right half of the array. Thus, move the left pointer to mid + 1.
If arr[mid] is greater than x, this means the target must be in the
left half of the array. Thus, move the right pointer to mid - 1.
STEP – 4 : Termination of Search:
o The loop terminates either when the target is found or when the left
pointer surpasses the right pointer, indicating that the element is not
present in the array.
STEP – 5: Return Result:
o If the element is found, return its index (mid).
o If the loop exits without finding the element, return -1.
STEP – 6 : Stop the program.
PSEUDOCODE – BINARY SEARCH:
Function binary_search(arr, x):
left = 0
right = length(arr) - 1
While left <= right:
mid = left + (right - left) // 2
If arr[mid] == x:
Return mid # Target found, return its index
Else If arr[mid] < x:
left = mid + 1
Else:
right = mid - 1
Return -1