quick_sort.py

import time
import random

comparison_num = 0

class Quick(object):
    def particao(self, a, ini, fim):
        global comparison_num
        comparison_num += 1
        pivo = a[fim-1]
        start = ini
        end = ini
        for i in range(ini,fim):
            comparison_num += 1
            if a[i] > pivo:
                end += 1
            else:
                end += 1       
                start += 1
                aux = a[start-1]
                a[start-1] = a[i]
                a[i] = aux
        return start-1
        
    def quick_sort(self, a, ini, fim):
        global comparison_num
        if ini < fim:
            pp = self.randparticao(a, ini, fim)
            self.quick_sort(a, ini, pp)
            self.quick_sort(a, pp+1,fim)
        return a
        
    def randparticao(self,a,ini,fim):
        global comparison_num
        comparison_num += 1
        rand = random.randrange(ini,fim)
        aux = a[fim-1]
        a[fim-1] = a[rand]
        a[rand] = aux
        return self.particao(a,ini,fim)


if __name__ == "__main__":
    entry = [*map(int, input().split(", "))]
    entry_len = len(entry)
    q = Quick()
    start = time.time()
    q.quick_sort(entry, 0, entry_len - 1)
    total_time = time.time() - start
    print("Comparison number:", comparison_num)
    print("Time:", total_time, "sec.")