





import math
def      _A       (		SCREAMING_SNAKE_CASE     :   list       ,       SCREAMING_SNAKE_CASE     :   int = 0       ,       SCREAMING_SNAKE_CASE     :   int = 0						):





  """simple docstring"""



  a__	:					Union[str, Any]										=end or len(SCREAMING_SNAKE_CASE						)
  for i in range(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						):
    a__	:					Dict										=i
    a__	:					Optional[int]										=array[i]
    while temp_index != start and temp_index_value < array[temp_index - 1]:
      a__	:					Tuple										=array[temp_index - 1]
      temp_index -= 1
    a__	:					Any										=temp_index_value
  return array
def      _A       (		SCREAMING_SNAKE_CASE     :   list       ,       SCREAMING_SNAKE_CASE     :   int       ,       SCREAMING_SNAKE_CASE     :   int						):  # Max Heap





  """simple docstring"""



  a__	:					Optional[int]										=index
  a__	:					Any										=2 * index + 1  # Left Node
  a__	:					Tuple										=2 * index + 2  # Right Node

  if left_index < heap_size and array[largest] < array[left_index]:
    a__	:					int										=left_index

  if right_index < heap_size and array[largest] < array[right_index]:
    a__	:					int										=right_index

  if largest != index:
    a__					,							a__	:					str										=array[largest], array[index]
    heapify(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						)
def      _A       (		SCREAMING_SNAKE_CASE     :   list						):





  """simple docstring"""



  a__	:					Any										=len(SCREAMING_SNAKE_CASE						)

  for i in range(n // 2       ,       -1       ,       -1						):
    heapify(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						)

  for i in range(n - 1       ,       0       ,       -1						):
    a__					,							a__	:					Optional[Any]										=array[0], array[i]
    heapify(SCREAMING_SNAKE_CASE       ,       0       ,       SCREAMING_SNAKE_CASE						)

  return array
def      _A       (		SCREAMING_SNAKE_CASE     :   list       ,       SCREAMING_SNAKE_CASE     :   int       ,       SCREAMING_SNAKE_CASE     :   int       ,       SCREAMING_SNAKE_CASE     :   int						):





  """simple docstring"""



  if (array[first_index] > array[middle_index]) != (
      array[first_index] > array[last_index]
  ):
    return array[first_index]
  elif (array[middle_index] > array[first_index]) != (
      array[middle_index] > array[last_index]
  ):
    return array[middle_index]
  else:
    return array[last_index]
def      _A       (		SCREAMING_SNAKE_CASE     :   list       ,       SCREAMING_SNAKE_CASE     :   int       ,       SCREAMING_SNAKE_CASE     :   int       ,       SCREAMING_SNAKE_CASE     :   int						):





  """simple docstring"""



  a__	:					str										=low
  a__	:					List[Any]										=high
  while True:
    while array[i] < pivot:
      i += 1
    j -= 1
    while pivot < array[j]:
      j -= 1
    if i >= j:
      return i
    a__					,							a__	:					Tuple										=array[j], array[i]
    i += 1
def      _A       (		SCREAMING_SNAKE_CASE     :   list						):





  """simple docstring"""



  if len(SCREAMING_SNAKE_CASE						) == 0:
    return array
  a__	:					str										=2 * math.ceil(math.loga(len(SCREAMING_SNAKE_CASE						)						)						)
  a__	:					str										=16
  return intro_sort(SCREAMING_SNAKE_CASE       ,       0       ,       len(SCREAMING_SNAKE_CASE						)       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						)
def      _A       (		SCREAMING_SNAKE_CASE     :   list       ,       SCREAMING_SNAKE_CASE     :   int       ,       SCREAMING_SNAKE_CASE     :   int       ,       SCREAMING_SNAKE_CASE     :   int       ,       SCREAMING_SNAKE_CASE     :   int						):





  """simple docstring"""



  while end - start > size_threshold:
    if max_depth == 0:
      return heap_sort(SCREAMING_SNAKE_CASE						)
    max_depth -= 1
    a__	:					Dict										=median_of_a(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       start + ((end - start) // 2) + 1       ,       end - 1						)
    a__	:					Any										=partition(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						)
    intro_sort(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						)
    a__	:					Tuple										=p
  return insertion_sort(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						)


if __name__ == "__main__":
     import doctest

     doctest.testmod()

     UpperCAmelCase	:	Optional[Any]		     =       input("""Enter numbers separated by a comma : """).strip()
     UpperCAmelCase	:	Dict		     =       [float(item) for item in user_input.split(""",""")]
     print(sort(unsorted))













import numpy

# List of input, output pairs
UpperCAmelCase	:	str		     =       (
    ((5, 2, 3), 15),
    ((6, 5, 9), 25),
    ((11, 12, 13), 41),
    ((1, 1, 1), 8),
    ((11, 12, 13), 41),
)
UpperCAmelCase	:	Optional[int]		     =       (((515, 22, 13), 555), ((61, 35, 49), 150))
UpperCAmelCase	:	str		     =       [2, 4, 1, 5]
UpperCAmelCase	:	List[str]		     =       len(train_data)
UpperCAmelCase	:	Dict		     =       0.0_0_9
def      _A       (		SCREAMING_SNAKE_CASE     :   Tuple       ,       SCREAMING_SNAKE_CASE     :   Tuple="train"						):





  """simple docstring"""



  return calculate_hypothesis_value(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						) - output(
      SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						)
def      _A       (		SCREAMING_SNAKE_CASE     :   Tuple						):





  """simple docstring"""



  a__	:					Tuple										=0
  for i in range(len(SCREAMING_SNAKE_CASE						) - 1						):
    hyp_val += data_input_tuple[i] * parameter_vector[i + 1]
  hyp_val += parameter_vector[0]
  return hyp_val
def      _A       (		SCREAMING_SNAKE_CASE     :   Dict       ,       SCREAMING_SNAKE_CASE     :   Dict						):





  """simple docstring"""



  if data_set == "train":
    return train_data[example_no][1]
  elif data_set == "test":
    return test_data[example_no][1]
  return None
def      _A       (		SCREAMING_SNAKE_CASE     :   Optional[Any]       ,       SCREAMING_SNAKE_CASE     :   Tuple						):





  """simple docstring"""



  if data_set == "train":
    return _hypothesis_value(train_data[example_no][0]						)
  elif data_set == "test":
    return _hypothesis_value(test_data[example_no][0]						)
  return None
def      _A       (		SCREAMING_SNAKE_CASE     :   Union[str, Any]       ,       SCREAMING_SNAKE_CASE     :   int=m						):





  """simple docstring"""



  a__	:					Any										=0
  for i in range(SCREAMING_SNAKE_CASE						):
    if index == -1:
      summation_value += _error(SCREAMING_SNAKE_CASE						)
    else:
      summation_value += _error(SCREAMING_SNAKE_CASE						) * train_data[i][0][index]
  return summation_value
def      _A       (		SCREAMING_SNAKE_CASE     :   int						):





  """simple docstring"""



  a__	:					Any										=summation_of_cost_derivative(SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE						) / m
  return cost_derivative_value
def      _A       (		):





  """simple docstring"""



  global parameter_vector
  # Tune these values to set a tolerance value for predicted output
  a__	:					Dict										=0.0_0_0_0_0_2
  a__	:					Union[str, Any]										=0
  a__	:					Any										=0
  while True:
    j += 1
    a__	:					Any										=[0, 0, 0, 0]
    for i in range(0       ,       len(SCREAMING_SNAKE_CASE						)						):
      a__	:					Tuple										=get_cost_derivative(i - 1						)
      a__	:					List[Any]										=(
          parameter_vector[i] - LEARNING_RATE * cost_derivative
      )
    if numpy.allclose(
        SCREAMING_SNAKE_CASE       ,       SCREAMING_SNAKE_CASE       ,       atol=SCREAMING_SNAKE_CASE       ,       rtol=SCREAMING_SNAKE_CASE       ,       ):
      break
    a__	:					Optional[Any]										=temp_parameter_vector
  print(("Number of iterations:", j)						)
def      _A       (		):





  """simple docstring"""



  for i in range(len(SCREAMING_SNAKE_CASE						)						):
    print(("Actual output value:", output(SCREAMING_SNAKE_CASE       ,       "test"						))						)
    print(("Hypothesis output:", calculate_hypothesis_value(SCREAMING_SNAKE_CASE       ,       "test"						))						)


if __name__ == "__main__":
     run_gradient_descent()
     print("""\nTesting gradient descent for a linear hypothesis function.\n""")
     test_gradient_descent()






