Oct 14, 2022
diff --git a/scripts/Median_algorithm/Median.md b/scripts/Median_algorithm/Median.md
 # Median Algorithm

 ###### It brings the median value of an array

 ## Run Script

 The script already has the array hardcoded.

 ## Command to run the script

 python3 Median_Algorithm.py
diff --git a/scripts/Median_algorithm/Median_Algorithm.py b/scripts/Median_algorithm/Median_Algorithm.py
 import random
 def pick_pivot(l):
    """
    Pick a good pivot within l, a list of numbers
    This algorithm runs in O(n) time.
    """
    assert len(l) > 0

    # If there are < 5 items, just return the median
    if len(l) < 5:
        # In this case, we fall back on the first median function we wrote.
        # Since we only run this on a list of 5 or fewer items, it doesn't
        # depend on the length of the input and can be considered constant
        # time.
        return nlogn_median(l)

    # First, we'll split `l` into groups of 5 items. O(n)
    chunks = chunked(l, 5)

    # For simplicity, we can drop any chunks that aren't full. O(n)
    full_chunks = [chunk for chunk in chunks if len(chunk) == 5]


    # Next, we sort each chunk. Each group is a fixed length, so each sort
    # takes constant time. Since we have n/5 chunks, this operation
    # is also O(n)
    sorted_groups = [sorted(chunk) for chunk in full_chunks]

    # The median of each chunk is at index 2
    medians = [chunk[2] for chunk in sorted_groups]

    # It's a bit circular, but I'm about to prove that finding
    # the median of a list can be done in provably O(n).
    # Finding the median of a list of length n/5 is a subproblem of size n/5
    # and this recursive call will be accounted for in our analysis.
    # We pass pick_pivot, our current function, as the pivot builder to
    # quickselect. O(n)
    median_of_medians = quickselect_median(medians, pick_pivot)
    return median_of_medians


 def chunked(l, chunk_size):
    """Split list `l` it to chunks of `chunk_size` elements."""
    return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]


 def nlogn_median(l):
    l = sorted(l)
    if len(l) % 2 == 1:
        return l[int((len(l) / 2))]
    else:
        return 0.5 * (l[len(l) / 2 - 1] + l[len(l) / 2])


 def quickselect_median(l, pivot_fn=random.choice):
    if len(l) % 2 == 1:
        return quickselect(l, len(l) / 2, pivot_fn)
    else:
        return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +
                      quickselect(l, len(l) / 2, pivot_fn))


 def quickselect(l, k, pivot_fn):
    """
    Select the kth element in l (0 based)
    :param l: List of numerics
    :param k: Index
    :param pivot_fn: Function to choose a pivot, defaults to random.choice
    :return: The kth element of l
    """
    if len(l) == 1:
        assert k == 0
        return l[0]

    pivot = pivot_fn(l)

    lows = [el for el in l if el < pivot]
    highs = [el for el in l if el > pivot]
    pivots = [el for el in l if el == pivot]

    if k < len(lows):
        return quickselect(lows, k, pivot_fn)
    elif k < len(lows) + len(pivots):
        # We got lucky and guessed the median
        return pivots[0]
    else:
        return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)


 l = [9,1,0,2,3,4,6,8,7,10,5]

 print(pick_pivot(l))

 """
 Considere a lista abaixo. Gostaríamos de encontrar a mediana.
 l = [9,1,0,2,3,4,6,8,7,10,5]
 len (l) == 11, então estamos procurando pelo 6º menor elemento
 Primeiro, devemos escolher um pivô. Selecionamos aleatoriamente o índice 3.
 O valor neste índice é 2.

 Particionamento com base no pivô:
 [1,0,2], [9,3,4,6,8,7,10,5]
 Queremos o 6º elemento. 6-len (esquerda) = 3, então queremos
 o terceiro menor elemento na matriz certa

 Agora estamos procurando o terceiro menor elemento na matriz abaixo:
 [9,3,4,6,8,7,10,5]
 Escolhemos um índice aleatoriamente para ser nosso pivô.
 Escolhemos o índice 3, o valor em que, l [3] = 6

 Particionamento com base no pivô:
 [3,4,5,6] [9,7,10]
 Queremos o terceiro menor elemento, então sabemos que é o
 3º menor elemento na matriz esquerda

 Agora estamos procurando o terceiro menor na matriz abaixo:
 [3,4,5,6]
 Escolhemos um índice aleatoriamente para ser nosso pivô.
 Escolhemos o índice 1, o valor em que, l [1] = 4
 Particionamento com base no pivô:
 [3,4] [5,6]
 Estamos procurando o item no índice 3, então sabemos que é
 o menor na matriz certa.

 Agora estamos procurando o menor elemento na matriz abaixo:
 [5,6]

 Neste ponto, podemos ter um caso base que escolhe a maior
 ou item menor com base no índice.
 Estamos procurando o menor item, que é 5.
 retorno 5

 Esse algoritmo roda em O(n)
 http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
 """
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,11 @@
		# Median Algorithm

		###### It brings the median value of an array

		## Run Script

		The script already has the array hardcoded.

		## Command to run the script

		python3 Median_Algorithm.py
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,135 @@
		import random
		def pick_pivot(l):
		"""
		Pick a good pivot within l, a list of numbers
		This algorithm runs in O(n) time.
		"""
		assert len(l) > 0

		# If there are < 5 items, just return the median
		if len(l) < 5:
		# In this case, we fall back on the first median function we wrote.
		# Since we only run this on a list of 5 or fewer items, it doesn't
		# depend on the length of the input and can be considered constant
		# time.
		return nlogn_median(l)

		# First, we'll split `l` into groups of 5 items. O(n)
		chunks = chunked(l, 5)

		# For simplicity, we can drop any chunks that aren't full. O(n)
		full_chunks = [chunk for chunk in chunks if len(chunk) == 5]


		# Next, we sort each chunk. Each group is a fixed length, so each sort
		# takes constant time. Since we have n/5 chunks, this operation
		# is also O(n)
		sorted_groups = [sorted(chunk) for chunk in full_chunks]

		# The median of each chunk is at index 2
		medians = [chunk[2] for chunk in sorted_groups]

		# It's a bit circular, but I'm about to prove that finding
		# the median of a list can be done in provably O(n).
		# Finding the median of a list of length n/5 is a subproblem of size n/5
		# and this recursive call will be accounted for in our analysis.
		# We pass pick_pivot, our current function, as the pivot builder to
		# quickselect. O(n)
		median_of_medians = quickselect_median(medians, pick_pivot)
		return median_of_medians


		def chunked(l, chunk_size):
		"""Split list `l` it to chunks of `chunk_size` elements."""
		return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]


		def nlogn_median(l):
		l = sorted(l)
		if len(l) % 2 == 1:
		return l[int((len(l) / 2))]
		else:
		return 0.5 * (l[len(l) / 2 - 1] + l[len(l) / 2])


		def quickselect_median(l, pivot_fn=random.choice):
		if len(l) % 2 == 1:
		return quickselect(l, len(l) / 2, pivot_fn)
		else:
		return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +
		quickselect(l, len(l) / 2, pivot_fn))


		def quickselect(l, k, pivot_fn):
		"""
		Select the kth element in l (0 based)
		:param l: List of numerics
		:param k: Index
		:param pivot_fn: Function to choose a pivot, defaults to random.choice
		:return: The kth element of l
		"""
		if len(l) == 1:
		assert k == 0
		return l[0]

		pivot = pivot_fn(l)

		lows = [el for el in l if el < pivot]
		highs = [el for el in l if el > pivot]
		pivots = [el for el in l if el == pivot]

		if k < len(lows):
		return quickselect(lows, k, pivot_fn)
		elif k < len(lows) + len(pivots):
		# We got lucky and guessed the median
		return pivots[0]
		else:
		return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)


		l = [9,1,0,2,3,4,6,8,7,10,5]

		print(pick_pivot(l))

		"""
		Considere a lista abaixo. Gostaríamos de encontrar a mediana.
		l = [9,1,0,2,3,4,6,8,7,10,5]
		len (l) == 11, então estamos procurando pelo 6º menor elemento
		Primeiro, devemos escolher um pivô. Selecionamos aleatoriamente o índice 3.
		O valor neste índice é 2.

		Particionamento com base no pivô:
		[1,0,2], [9,3,4,6,8,7,10,5]
		Queremos o 6º elemento. 6-len (esquerda) = 3, então queremos
		o terceiro menor elemento na matriz certa

		Agora estamos procurando o terceiro menor elemento na matriz abaixo:
		[9,3,4,6,8,7,10,5]
		Escolhemos um índice aleatoriamente para ser nosso pivô.
		Escolhemos o índice 3, o valor em que, l [3] = 6

		Particionamento com base no pivô:
		[3,4,5,6] [9,7,10]
		Queremos o terceiro menor elemento, então sabemos que é o
		3º menor elemento na matriz esquerda

		Agora estamos procurando o terceiro menor na matriz abaixo:
		[3,4,5,6]
		Escolhemos um índice aleatoriamente para ser nosso pivô.
		Escolhemos o índice 1, o valor em que, l [1] = 4
		Particionamento com base no pivô:
		[3,4] [5,6]
		Estamos procurando o item no índice 3, então sabemos que é
		o menor na matriz certa.

		Agora estamos procurando o menor elemento na matriz abaixo:
		[5,6]

		Neste ponto, podemos ter um caso base que escolhe a maior
		ou item menor com base no índice.
		Estamos procurando o menor item, que é 5.
		retorno 5

		Esse algoritmo roda em O(n)
		http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
		"""