[go: up one dir, main page]
Scribd
Upload
18 views4 pages

STEP - 1: Start The Program STEP - 2: Initialize The List

DAA LAB

Uploaded by

sushmitaa9193
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
18 views4 pages

STEP - 1: Start The Program STEP - 2: Initialize The List

DAA LAB

Uploaded by

sushmitaa9193
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

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

You might also like