
def      _a     (   __UpperCamelCase       :  list    ):
			lowerCAmelCase__ :    int				      =			len(__UpperCamelCase    )

			# Set the gap value to be decreased by a factor of 1.3
			# after each iteration
			lowerCAmelCase__ :    Dict				      =			1.3

			# Continue sorting until the gap is 1
			while gap > 1:
						# Decrease the gap value
						lowerCAmelCase__ :    List[Any]				      =			int(gap / shrink    )

						# Sort the elements using insertion sort
						for i in range(__UpperCamelCase	,len(__UpperCamelCase    )    ):
									lowerCAmelCase__ :    Dict				      =			collection[i]
									lowerCAmelCase__ :    Optional[int]				      =			i
									while j >= gap and collection[j - gap] > temp:
												lowerCAmelCase__ :    int				      =			collection[j - gap]
												j -= gap
									lowerCAmelCase__ :    Union[str, Any]				      =			temp

			return collection


if __name__ == "__main__":
							import doctest

							doctest.testmod()





import numpy as np
from numpy import floataa
from numpy.typing import NDArray



def      _a     (   __UpperCamelCase       :  NDArray[floataa]	,__UpperCamelCase       :  NDArray[floataa]    ):
			lowerCAmelCase__      ,				lowerCAmelCase__ :    Any				      =			np.shape(__UpperCamelCase    )

			lowerCAmelCase__ :    NDArray[floataa]				      =			np.zeros((rows, 1)	,dtype=__UpperCamelCase    )
			for row in reversed(range(__UpperCamelCase    )    ):
						lowerCAmelCase__ :    List[str]				      =			0
						for col in range(row + 1	,__UpperCamelCase    ):
									total += coefficients[row, col] * x[col]

						lowerCAmelCase__ :    int				      =			(vector[row] - total) / coefficients[row, row]

			return x



def      _a     (   __UpperCamelCase       :  NDArray[floataa]	,__UpperCamelCase       :  NDArray[floataa]    ):
			lowerCAmelCase__      ,				lowerCAmelCase__ :    str				      =			np.shape(__UpperCamelCase    )
			if rows != columns:
						return np.array(()	,dtype=__UpperCamelCase    )

			# augmented matrix
			lowerCAmelCase__ :    NDArray[floataa]				      =			np.concatenate((coefficients, vector)	,axis=1    )
			lowerCAmelCase__ :    List[str]				      =			augmented_mat.astype('''float64'''    )

			# scale the matrix leaving it triangular
			for row in range(rows - 1    ):
						lowerCAmelCase__ :    str				      =			augmented_mat[row, row]
						for col in range(row + 1	,__UpperCamelCase    ):
									lowerCAmelCase__ :    Optional[int]				      =			augmented_mat[col, row] / pivot
									augmented_mat[col, :] -= factor * augmented_mat[row, :]

			lowerCAmelCase__ :    int				      =			retroactive_resolution(
			    augmented_mat[:, 0:columns]	,augmented_mat[:, columns : columns + 1]    )

			return x


if __name__ == "__main__":
							import doctest

							doctest.testmod()



