forked from menault/TD4_DEV51_Qualite_Algo
122 lines
3.1 KiB
Python
122 lines
3.1 KiB
Python
def heapify(array, n, i):
|
|
|
|
largest = i
|
|
left = 2 * i + 1
|
|
right = 2 * i + 2
|
|
|
|
if left < n and array[left] > array[largest]:
|
|
largest = left
|
|
|
|
if right < n and array[right] > array[largest]:
|
|
largest = right
|
|
|
|
if largest != i:
|
|
array[i], array[largest] = array[largest], array[i]
|
|
heapify(array, n, largest)
|
|
|
|
def heap_sort(array):
|
|
n = len(array)
|
|
|
|
# Construire un tas max
|
|
for i in range(n // 2 - 1, -1, -1):
|
|
heapify(array, n, i)
|
|
|
|
|
|
for i in range(n - 1, 0, -1):
|
|
array[i], array[0] = array[0], array[i]
|
|
heapify(array, i, 0)
|
|
|
|
return array
|
|
|
|
def total_sum(array):
|
|
if isinstance(array[0], int):
|
|
return sum(array)
|
|
return sum(total_sum(subarray) for subarray in array) # Si tableau multidimensionnel
|
|
|
|
|
|
def sort_with_sum(array):
|
|
for i in range(1, len(array)):
|
|
key = array[i]
|
|
key_sum = total_sum(key)
|
|
j = i - 1
|
|
# Réorganise les sous-tableaux en fonction de leur somme
|
|
while j >= 0 and total_sum(array[j]) > key_sum:
|
|
array[j + 1] = array[j]
|
|
j -= 1
|
|
array[j + 1] = key
|
|
|
|
return array
|
|
|
|
|
|
|
|
def sort_nd_array(array):
|
|
# Si le tableau est de dimension 1, tri simple par insertion
|
|
if isinstance(array[0], int):
|
|
return heap_sort(array)
|
|
|
|
# Si le tableau est multidimensionnel, on trie récursivement les sous-tableaux
|
|
sorted_subarrays = [sort_nd_array(subarray) for subarray in array]
|
|
|
|
sorted_subarrays = sort_with_sum(sorted_subarrays)
|
|
|
|
return sorted_subarrays
|
|
|
|
|
|
def print_nd_array(array, level=0):
|
|
"""
|
|
Affiche un tableau N-dimensionnel de manière lisible.
|
|
"""
|
|
if isinstance(array[0], int): # Si tableau 1D
|
|
print(" " * level + str(array))
|
|
else: # Tableau multidimensionnel
|
|
print(" " * level + "[")
|
|
for subarray in array:
|
|
print_nd_array(subarray, level + 1)
|
|
print(" " * level + "]")
|
|
|
|
|
|
def main():
|
|
# Exemple 1 : Tableau 2D
|
|
array_2d = [[0, 3, 2], [9, 4, 5], [4, 1, 3]]
|
|
print("Tableau 2D avant tri :")
|
|
print_nd_array(array_2d)
|
|
result_2d = sort_nd_array(array_2d)
|
|
print("Tableau 2D après tri :")
|
|
print_nd_array(result_2d)
|
|
|
|
# Exemple 2 : Tableau 3D
|
|
array_3d = [
|
|
[[3, 1], [4, 2], [1, 3]],
|
|
[[5, 7], [2, 8], [9, 4]],
|
|
[[0, 0], [1, 1], [1, 0]]
|
|
]
|
|
print("\nTableau 3D avant tri :")
|
|
print_nd_array(array_3d)
|
|
result_3d = sort_nd_array(array_3d)
|
|
print("Tableau 3D après tri :")
|
|
print_nd_array(result_3d)
|
|
|
|
# Exemple 3 : Tableau 4D
|
|
array_4d = [
|
|
[
|
|
[[1, 3], [4, 5], [2, 2]],
|
|
[[7, 8], [5, 6], [3, 4]]
|
|
],
|
|
[
|
|
[[9, 1], [6, 7], [8, 3]],
|
|
[[2, 5], [7, 3], [9, 9]]
|
|
],
|
|
[
|
|
[[3, 3], [2, 1], [5, 6]],
|
|
[[4, 2], [8, 7], [3, 9]]
|
|
]
|
|
]
|
|
print("\nTableau 4D avant tri :")
|
|
print_nd_array(array_4d)
|
|
result_4d = sort_nd_array(array_4d)
|
|
print("Tableau 4D après tri :")
|
|
print_nd_array(result_4d)
|
|
|
|
if __name__ == "__main__":
|
|
main()
|