Utilisateur:Suaudeau/Code de génération des animations
Voici le code qui a généré les animations suivantes:
#----------------------------------------------------------
# Create an animated series of SVG images of a sort algorithm
# Author : Hervé Suaudeau (herve.suaudeau (at) parisdescartes.fr)
#----------------------------------------------------------
#----------------------------------------------------------
# Librairy for creating animations
#----------------------------------------------------------
#CONSTANTS
#---------
# Vector to sort
input_vector = [1,38,171,206,213,31,45,24,164,157,52,10,
66,150,59,73,122,192,87,136,129,185,143,17,
80,220,178,108,101,227,199,115,94]
#SVG constant codes
SVG_HEADER="""<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg width="277" height="257" version="1.1" >"""
SVG_FOOTER="""</svg>"""
SVG_out_rectangle_start="""
<rect x="0" y="0" width="277" height="257"
style="fill:rgb(255,255,255);stroke-width:1;stroke:none" />
<g transform="translate(5.5, 5.5)">
<rect x="0" y="0" width="266" height="246"
style="fill:none;stroke-width:1;stroke:rgb(234,234,234)" />
<g transform="translate(1.5, 1.5)">"""
SVG_out_rectangle_stop="""</g><g class="anim %s"></g></g>"""
#Create a SVG file from svg code.
def createFileFromSvg(filename, svg_code):
try:
filehandler = open(filename,'w') # Trying to create a new file or open one
except:
print('Something went wrong in createFileFromSvg! Can\'t tell what?')
sys.exit(0) # quit Python
filehandler.write(SVG_HEADER + svg_code + SVG_FOOTER)
filehandler.close()
#Draw one of the 33 bars in the chart in a square of 264x244 pixels.
def draw_bar(rank, height, color="rgb(200,200,200)"):
svg='<rect x="' + str(8*rank) + '" y="' + str(243-height) + '" width="7" height="'+ str(height) +'" style="fill:'+color+';stroke-width:0;none" />'
svg+='<rect x="' + str(8*rank) + '" y="' + str(243-height-7) + '" width="7" height="7" style="fill:rgb(0,0,0);stroke-width:0;stroke:none" />'
return svg
#Draw the whole image, from the vector, with specific action dedicated to two compared ranks
def drawChart(vector, rank1, rank2, action):
rank=0
svg_bars=""
for i in vector:
if ( ( rank==rank1 ) or ( rank==rank2 ) ):
if ( action == "SWITCH" ) :
svg_bars+=draw_bar(rank,i,"rgb(254,0,0)") #red
else :
svg_bars+=draw_bar(rank,i,"rgb(254,200,200)") #light red
else:
svg_bars+=draw_bar(rank,i)
rank+=1
return svg_bars
#Class that creates linked successive images
class SvgSuccessiveImagesClass:
image_rank = 0
last_vector= []
last_rank1=0
last_rank2=0
last_action=""
#Should be called at each step to create an image
def drawStepImage(self, vector, rank1, rank2, action):
self.image_rank+=1
self.last_vector=vector
self.last_rank1=rank1
self.last_rank2=rank2
self.last_action=action
inner_svg = SVG_out_rectangle_start + drawChart(vector, rank1, rank2, action) + SVG_out_rectangle_stop
createFileFromSvg("frames/frame"+str(self.image_rank).zfill(4)+".svg",inner_svg)
if self.image_rank==1 : #The first 10 images are repeated
for x in range(1,10):
self.image_rank+=1
createFileFromSvg("frames/frame"+str(self.image_rank).zfill(4)+".svg",inner_svg)
#Should be called at the end to insert still images
def drawEndImages(self):
self.image_rank+=1
inner_svg = SVG_out_rectangle_start + drawChart(self.last_vector, self.last_rank1, self.last_rank2, self.last_action) + SVG_out_rectangle_stop
for x in range(0,10): #The last 10 images are repeated
self.image_rank+=1
createFileFromSvg("frames/frame"+str(self.image_rank).zfill(4)+".svg",inner_svg)
return self.image_rank
#----------------------------------------------------------
#Sort algorithms instrumented to print images at each steps
#----------------------------------------------------------
def bubbleSort_optimized(vector):
s=SvgSuccessiveImagesClass();
n = len(vector)
for i in range(n-1):
sorted = True
for j in range(0, n-i-1):
if vector[j] > vector[j+1] :
vector[j], vector[j+1] = vector[j+1], vector[j]
s.drawStepImage(vector, j, j+1, "SWITCH")
sorted = False
else :
s.drawStepImage(vector, j, j+1, "ONLY_COMPARE")
if sorted :
return s.drawEndImages()
break
return s.drawEndImages()
def bubbleSort_dummy(vector):
s=SvgSuccessiveImagesClass();
n = len(vector)
for i in range(n-1):
for j in range(0, n-i-1):
if vector[j] > vector[j+1] :
vector[j], vector[j+1] = vector[j+1], vector[j]
s.drawStepImage(vector, j, j+1, "SWITCH")
else :
s.drawStepImage(vector, j, j+1, "ONLY_COMPARE")
return s.drawEndImages()
def cocktailShakerSort(vector):
s=SvgSuccessiveImagesClass();
swapped = True
n = len(vector)
start = 0
end = n-1
while swapped == True:
swapped = False
for i in range(start, end):
if vector[i] > vector[i+1] :
vector[i], vector[i+1] = vector[i+1], vector[i]
s.drawStepImage(vector, i, i+1, "SWITCH")
swapped = True
else :
s.drawStepImage(vector, i, i+1, "ONLY_COMPARE")
if swapped == False :
break
swapped = False
end = end-1
for i in range(end-1,start-1,-1):
if vector[i] > vector[i+1] :
vector[i], vector[i+1] = vector[i+1], vector[i]
s.drawStepImage(vector, i, i+1, "SWITCH")
swapped = True
else :
s.drawStepImage(vector, i, i+1, "ONLY_COMPARE")
start = start+1
return s.drawEndImages()
def OddEvenSort(vector):
s=SvgSuccessiveImagesClass();
n = len(vector)
is_sorted = False
while is_sorted == False:
is_sorted = True
for i in range(2, n-1, 2):
if vector[i] > vector[i+1] :
vector[i], vector[i+1] = vector[i+1], vector[i]
s.drawStepImage(vector, i, i+1, "SWITCH")
is_sorted = False
else :
s.drawStepImage(vector, i, i+1, "ONLY_COMPARE")
for i in range(1, n-1, 2):
if vector[i] > vector[i+1] :
vector[i], vector[i+1] = vector[i+1], vector[i]
s.drawStepImage(vector, i, i+1, "SWITCH")
is_sorted = False
else :
s.drawStepImage(vector, i, i+1, "ONLY_COMPARE")
return s.drawEndImages()
def combsort_inplace(data):
s=SvgSuccessiveImagesClass();
length = len(data)
shrink = 1.3
_gap = length
sorted = False
while not sorted:
# Python has no builtin 'floor' function, so we/I just have one variable (_gap) to be shrunk,
# and an integer variable (gap) to store the truncation (of the other variable) in and
# to use for stuff pertaining to indexing
_gap /= shrink
# gap = np.floor(_gap)
gap = int(_gap)
if gap <= 1:
sorted = True
gap = 1
for i in range(length - gap):
sm = gap + i
if data[i] > data[sm]:
data[i], data[sm] = data[sm], data[i]
s.drawStepImage(data, i, sm, "SWITCH")
sorted = False
else:
s.drawStepImage(data, i, sm, "ONLY_COMPARE")
return s.drawEndImages()
def gnomeSort(a):
s=SvgSuccessiveImagesClass();
pos = 0
n = len(a)
while pos < n:
if (pos == 0 or a[pos] >= a[pos-1]):
s.drawStepImage(a, pos, pos-1, "ONLY_COMPARE")
pos += 1
else:
a[pos], a[pos-1] = a[pos-1], a[pos]
s.drawStepImage(a, pos, pos-1, "SWITCH")
pos -= 1
return s.drawEndImages()
def stoogesort_in(s, L, i, j):
if L[i] > L[j]: # If the leftmost element is larger than the rightmost element
L[i], L[j] = L[j], L[i] # Swap the leftmost element and the rightmost element
s.drawStepImage(L, i, j, "SWITCH")
#else:
# s.drawStepImage(L, i, j, "ONLY_COMPARE")
if (j - i + 1) > 2 : # If there are at least 3 elements in the array
t = int((j - i + 1) / 3)
stoogesort_in(s, L, i , j-t) # Sort the first 2/3 of the array
stoogesort_in(s, L, i+t, j) # Sort the last 2/3 of the array
stoogesort_in(s, L, i , j-t) # Sort the first 2/3 of the array again
return L
def stoogesort(L):
s=SvgSuccessiveImagesClass();
stoogesort_in(s,L, 0, len(L)-1)
return s.drawEndImages()
def shellsort(a):
s=SvgSuccessiveImagesClass();
n = len(a)
gaps = [23, 10, 4, 1]
# Start with the largest gap and work down to a gap of 1
for gap in gaps:
# Do a gapped insertion sort for this gap size.
# The first gap elements a[0..gap-1] are already in gapped order
# keep adding one more element until the entire array is gap sorted
for i in range(gap,n):
# add a[i] to the elements that have been gap sorted
# save a[i] in temp and make a hole at position i
temp = a[i]
temp_i = i
# shift earlier gap-sorted elements up until the correct location for a[i] is found
j = i
while ( (j >= gap) and (a[j - gap] > temp) ):
a[j] = a[j - gap]
s.drawStepImage(a, j, j - gap, "SWITCH")
j -= gap
# put temp (the original a[i]) in its correct location
a[j] = temp
s.drawStepImage(a, j, temp_i, "SWITCH")
return s.drawEndImages()
def insertionSort(arr):
s=SvgSuccessiveImagesClass();
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
key_key = i
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
s.drawStepImage(arr, j+1, j, "SWITCH")
j -= 1
arr[j + 1] = key
s.drawStepImage(arr, j+1, key_key, "SWITCH")
return s.drawEndImages()
def oddEvenSort(arr):
s=SvgSuccessiveImagesClass();
n = len(arr)
# Initially array is unsorted
isSorted = 0
while isSorted == 0:
isSorted = 1
temp = 0
for i in range(1, n-1, 2):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
s.drawStepImage(arr, i, i+1, "SWITCH")
isSorted = 0
for i in range(0, n-1, 2):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
s.drawStepImage(arr, i, i+1, "SWITCH")
isSorted = 0
return s.drawEndImages()
def quickSort_partition(s, arr, low, high):
i = (low-1) # index of smaller element
pivot = arr[high] # pivot
for j in range(low, high):
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
s.drawStepImage(arr, i, j, "SWITCH")
arr[i+1], arr[high] = arr[high], arr[i+1]
s.drawStepImage(arr, i+1, high, "SWITCH")
return (i+1)
def quickSort_recursive(s, arr, low, high):
if len(arr) == 1:
return arr
if low < high:
pi = quickSort_partition(s, arr, low, high)
quickSort_recursive(s, arr, low, pi-1)
quickSort_recursive(s, arr, pi+1, high)
def quickSort(arr):
s=SvgSuccessiveImagesClass();
n = len(arr)
quickSort_recursive(s, arr, 0, n-1)
return s.drawEndImages()
def selectionSort(A):
s=SvgSuccessiveImagesClass();
for i in range(len(A)):
# Find the minimum element in remaining
# unsorted array
min_idx = i
for j in range(i+1, len(A)):
s.drawStepImage(A, min_idx, j, "ONLY_COMPARE")
if A[min_idx] > A[j]:
min_idx = j
# Swap the found minimum element with
# the first element
A[i], A[min_idx] = A[min_idx], A[i]
s.drawStepImage(A, min_idx, i, "SWITCH")
return s.drawEndImages()
# To heapify subtree rooted at index i.
# n is size of heap
def heapify(s, arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < n:
s.drawStepImage(arr, i, l, "ONLY_COMPARE")
if arr[i] < arr[l]:
largest = l
# See if right child of root exists and is
# greater than root
if r < n:
s.drawStepImage(arr, r, largest, "ONLY_COMPARE")
if arr[largest] < arr[r]:
largest = r
# Change root, if needed
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # swap
s.drawStepImage(arr, i, largest, "SWITCH")
# Heapify the root.
heapify(s, arr, n, largest)
# The main function to sort an array of given size
def heapSort(arr):
n = len(arr)
s=SvgSuccessiveImagesClass();
# Build a maxheap.
# Since last parent will be at ((n//2)-1) we can start at that location.
for i in range(n // 2 - 1, -1, -1):
heapify(s, arr, n, i)
# One by one extract elements
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
s.drawStepImage(arr, 0, i, "SWITCH")
heapify(s, arr, i, 0)
return s.drawEndImages()
def cycleSort(array):
s=SvgSuccessiveImagesClass();
writes = 0
# Loop through the array to find cycles to rotate.
for cycleStart in range(0, len(array) - 1):
item = array[cycleStart]
# Find where to put the item.
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# If the item is already there, this is not a cycle.
if pos == cycleStart:
continue
# Otherwise, put the item there or right after any duplicates.
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
# Rotate the rest of the cycle.
while pos != cycleStart:
# Find where to put the item.
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# Put the item there or right after any duplicates.
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
return s.drawEndImages()
return writes
#----------------------------------------------------------
# Main
#----------------------------------------------------------
rank=0
svg_bars=""
print('Create SVG files...')
#number_of_picture = bubbleSort_dummy(input_vector)
#number_of_picture = bubbleSort_optimized(input_vector)
#number_of_picture = cocktailShakerSort(input_vector)
#number_of_picture = OddEvenSort(input_vector)
#number_of_picture = combsort_inplace(input_vector)
#number_of_picture = gnomeSort(input_vector)
#number_of_picture = stoogesort(input_vector)
#number_of_picture = shellsort(input_vector)
#number_of_picture = insertionSort(input_vector)
#number_of_picture = oddEvenSort(input_vector)
#number_of_picture = quickSort(input_vector)
#number_of_picture = selectionSort(input_vector)
#number_of_picture = heapSort(input_vector)
number_of_picture = cycleSort(input_vector)
print('Done!')
print("Please convert these " + str(number_of_picture) + " SVG files into an animated GIF.")