Mínimo y máximo de una lista en Python (sin usar la función mínimo / máximo)

Me preguntaba si hay una manera de encontrar min y max de una lista sin usar las funciones min / max en Python. Así que escribí un pequeño código para el mismo usando recursión. Mi lógica es muy ingenua: hago dos stacks (min_stack y max_stack) que hacen un seguimiento del mínimo y máximo durante cada llamada recursiva. Tengo dos preguntas:

  1. ¿Podría alguien ayudarme a estimar la complejidad de mi código?
  2. ¿Hay una mejor manera de hacer esto? ¿La clasificación de la lista con mergesort / quicksort y la selección del primer y último elemento dará un mejor rendimiento?

Gracias

Aquí está mi bash en Python:

minimum = [] maximum = [] # Defining Stack Class class Stack: def __init__(self) : self.items = [] def push(self, item) : self.items.append(item) def pop(self) : return self.items.pop() def access(self, index): return self.items[index] def isEmpty(self) : return (self.items == []) def length(self): return len(self.items) def minmax(input_list): # make two stacks, one for min and one for max min_stack = Stack() max_stack = Stack() # comparing the first two elements of the list and putting them in appropriate stack if input_list[0]<input_list[1]: min_stack.push(input_list[0]) max_stack.push(input_list[1]) else: max_stack.push(input_list[0]) min_stack.push(input_list[1]) # Pushing remaining elements of the list into appropriate stacks. for i in range(2, len(input_list)): if input_list[i]  0: minlist.append(min_stack.pop()) # to find maximum maxlist = [] while max_stack.length() > 0: maxlist.append(max_stack.pop()) if len(minlist) > 1: minmax(minlist) else: minimum.append(minlist) if len(maxlist) > 1: minmax(maxlist) else: maximum.append(maxlist) def main(): input_list = [2, 0, 2, 7, 5, -1, -2] print 'Input List is: ', input_list minmax(input_list) print 'Global Minimum is: ', minimum[0] print 'Global Maximum is: ', maximum[len(maximum)-1] if __name__ == "__main__": main() 

    El uso de sorted() sería, por supuesto, confiable, rápido de escribir y alto rendimiento para listas de tamaño moderado porque está integrado. Para listas grandes, un algoritmo O (n) sería más rápido, por ejemplo:

     def minmax1 (x): # this function fails if the list length is 0 minimum = maximum = x[0] for i in x[1:]: if i < minimum: minimum = i else: if i > maximum: maximum = i return (minimum,maximum) print(minmax1([9,8,7,6,5,4,3,2,1,11,12,13,14,15,16,17,18,19])) print(minmax1([1])) print(minmax1([2, 0, 2, 7, 5, -1, -2])) 

    … para lo cual la salida es:

     (1, 19) (1, 1) (-2, 7) 

    Estaba interesado en comprobar el rendimiento de las dos alternativas. En mi PC con Windows XP y Python 3.2.3, encontré que el enfoque de clasificación es más rápido que la función minmax1() definida anteriormente para listas de menos de 500 elementos pero, para listas más largas, la O (n) minmax1() es Más rápido. Mi código de prueba de tiempo fue el siguiente:

     def minmax_sort(x): x = sorted(x) return (x[0],x[-1]) import timeit aa = list(range(0,100)) a = aa while (1): stime = min(timeit.repeat('minmax_sort(a)', "from __main__ import minmax_sort,a",number=1000)) mtime = min(timeit.repeat('minmax1(a)', "from __main__ import minmax,a",number=1000)) if (stime > mtime): break else: a = a + aa print(len(a)) 

    Encontrando Min y Max de una lista usando solo recursividad.

    Tuve esta tarea similar la semana pasada y dividí el código en tres partes.

    Paso 1: Encontrar el valor mínimo en la lista

     def RecursiveMin(L): if len(L)==2: if L[0] 

    Paso 2: Ordenar la lista en orden ascendente (de menor a mayor)

     def Sort(x): L=sorted(x) if x==L: return x else: i=0 for i in range (len(x)): if x[i] > x[i+1] : break unsortedPart = x[i:] R = RecursiveMin(unsortedPart) I = unsortedPart.index(R) for j in range (len(x)): if x[j] > R : del x[(I+i)] x.insert(j,R) break return Sort(x) 

    (Anteriormente respondí una pregunta de clasificación y proporcioné el mismo código. Así que, por favor, no me marque por plagio, ya que es mi propio código. Me gusta: encontrar el elemento mínimo en una lista (recursivamente) - Python ).

    ** Paso 3: Cree una nueva función con un argumento si el usuario desea Valor mínimo o Máx *

     def minMax(lst,user): if user == min: return Sort(lst) elif user == max: s = Sort(lst) return s[::-1] 

    El último paso no es recursivo, pero si comstack los tres pasos en una función, será "1 función recursiva". PD: si su pregunta solo trataba de encontrar el Mínimo y el Máximo en una lista, puede omitir el Paso 2 y hacer algunos cambios al Paso 1 y al Paso 3