-8

I am looking for a faster, less execution time approach to get maximum and minimum elements of an array of integer, which means we need to sort an array of integers. Without using any inbuilt functions like sort() except range() and len() and using only one for or while loop, which I can't figure out.

def getMinMax( a, n):
    while 1 == 1:
        run = False
        for i in range(n):
            if i < (n-1) and a[i] > a[i+1]:
                run = True
        if run:
            for i in range(n):
                if i < (n-1) and a[i] > a[i+1]:
                    temp = a[i]
                    a[i] = a[i+1]
                    a[i+1] = temp
        else:
            break

    return a[0], a[i], a

A = [2, 167, 56, 3, 10000, 1]
min_elem, max_elem, sorted_array = getMinMax(A, len(A))
min_elem, max_elem, sorted_array

Output:

(1, 10000, [1, 2, 3, 56, 167, 10000])

With one loop

def getMinMax( a, n):
    min_elem = a[0]
    max_elem = a[0]

    for i in range(n):
        if i < (n-1):
            if a[i] > a[i+1]:
                temp = a[i]
                a[i] = a[i+1]
                a[i+1] = temp
    max_var, min_var = a[n-1], a[0]
    return max_elem, min_elem

array = [3,123,200,4,500000,1]
getMinMax( array, len(array))

Output:

(500000, 3)
Vega
  • 27,856
  • 27
  • 95
  • 103
Waqar Dongre
  • 57
  • 1
  • 6
  • 4
    Faster on what? Developer's time? `return min(a), max(a)` – Klaus D. Oct 16 '21 at 14:13
  • I strongly advise taking a look at the list of builtin functions: https://docs.python.org/3/library/functions.html – Stef Oct 16 '21 at 14:33
  • Duplicate of https://stackoverflow.com/questions/52354317/efficient-way-to-get-min-and-max-from-a-list, but this is not a high-quality dupe target, so I used another reason. – David Eisenstat Oct 16 '21 at 15:01
  • The output looks *(max, min)*. Can you make do with, say 3/4 the comparisons of above code? Rather than loop over `range(n)` and check for `i < (n-1)`, use `range(n-1)`. – greybeard Oct 17 '21 at 11:15
  • Thank you @greybeard, didn't thought that, updated the code. – Waqar Dongre Oct 17 '21 at 11:24
  • Please do not add solutions in the questions post. Do not re-invent SO's format, it should stay as Q&A site – Vega Oct 18 '21 at 10:14

3 Answers3

1

Basically, your method to find min and max is not having any major effect at all. Besides, it is taking more time to execute than the normal method of finding min and max. (i.e. to iterate twice and swap adjacent elements if the preceding and succeeding are lesser or greater, and then access the first and last element directly to get the min and max values resp.)

To demonstrate why your code is not efficient as the traditional method, I executed your code 100000000 times vs my traditional code the same number of times and found out that your code actually takes more time than mine!

import timeit

A = [3, 2, 1, 56, 10000, 167]

code1 = '''
def getMinMax( a, n):
    while 1 == 1:
        run = False
        for i in range(n):
            if i < (n-1) and a[i] > a[i+1]:
                run = True
        if run:
            for i in range(n):
                if i < (n-1) and a[i] > a[i+1]:
                    temp = a[i]
                    a[i] = a[i+1]
                    a[i+1] = temp
        else:
            break
    print(a[i], a[0])
    return a[i], a[0]
'''

code2 = '''
def min_max(A):
    for i in range(len(A)):
        for j in range(1, len(A)-1):
            if A[j] > A[j+1]:
                A[j],A[j+1] = A[j+1],A[j]
    print(A[0], A[len(A)-1])
    return A[0],A[len(A)-1]
'''

print(timeit.timeit(stmt=code1, number=100000000))
print(timeit.timeit(stmt=code2, number=100000000))

Output:

6.4907884000000005 #<-- your code's execution time after the 100000000th execution

5.600494200000001 #<-- my code's execution time after the 100000000th execution
Shubham Nanche
  • 130
  • 2
  • 11
  • 1
    Uh... what's the point of measuring how long it takes to *define* functions instead of how long it takes to *execute* them? – no comment Oct 16 '21 at 20:14
0

I know this is ridiculous but if the person asking the question really doesn't want to use min() and/or max() then this also works:

def getMinMax(A):
  if A:
    a = sorted(A)
    return a[0], a[-1]
  return None, None
0
l=[1,2,3,4,5]
print(max(l),min(l))

Just use min() and max() function.
syntax:
for min()

min(iterable_name)

for max()

max(iterable_name)
shankar v
  • 1
  • 4
  • Well guys thank you I figured it out, with using only one loop and without using inbuilt functions like sorted(), min(), max(). Got the idea from this link https://stackoverflow.com/questions/52354317/efficient-way-to-get-min-and-max-from-a-list Thank you @DavidEisenstat – Waqar Dongre Oct 17 '21 at 10:39