Outils d'utilisateurs

Outils du Site


fondamentaux:algos_tri

Algorithmes de tri

Note : je donnerais ici des implémentations directes en Python, avec quelques commentaires pour permettre la compréhension.

QuickSort (Tri Rapide)

#!/bin/python
# -*- coding: utf-8 -*- 
#
# Soft : QuickSort in Python
# Author : NekoLover
 
def partition(array, start, end, compare):
    """Make a permutation sort inside the given range"""
    while start < end:
        # The partition use the first element of the range as pivot
        while start < end:
            if compare(array[start], array[end]):
                (array[start], array[end]) = (array[end], array[start])
                break
            end = end - 1
        # The partition use the last element of the range as pivot
        while start < end:
            if compare(array[start], array[end]):
                (array[start], array[end]) = (array[end], array[start])
                break
            start = start + 1
    return start
 
def quicksort(array, compare=lambda x, y: x > y, start=None, end=None):
    """Main sort function"""
    if start is None: start = 0
    if end is None: end = len(array)
    if start < end:
        i = partition(array, start, end-1, compare)
        quicksort(array, compare, start, i)
        quicksort(array, compare, i+1, end)
 
# Sample execution if not executed as a module
if __name__ == "__main__":
    t = [ 25, 20, 35, 32, 2, 4, 42 ]
    print "Before : ", t
    quicksort(t)
    print "Sorted : ", t

Tri Fusion

Tri à Bulles

fondamentaux/algos_tri.txt · Dernière modification: 2012/02/21 22:49 (modification externe)