[Python] Algoritmi de sortare (console) [cmiN]

[cmiN]

Pentru cei care vor sa mai prinda cate ceva fara sa se chinuie pe wiki...

Am scris o clasa in Python (mai mult pentru implementare teoretica nu si pentru aplicabilitate) care sorteaza un tablou unidimensional (vector), mai exact o lista ce poate contine orice, iar in functie de compatibilitatea operatorilor in alte limbaje de programare lista se poate rezuma doar la intregi.

Am pus accentul pe 2 metode de sortare foarte usoare si destul de populare (bubblesort si quicksort) si am mai folosit o metoda aflata printre functiile implicite in Python (timsort) de asemenea aceeasi metoda este folosita si in Java.

Cea mai optima este timsort (functia sorted din Python) O(n*log(n)), dar mai la indemana este bubblesort O(n*(n+1)/2) si ceva mai bun de atat este quicksort O(n*log(n)). In cel mai rau caz se poate obtine O(n^2) atat pentru bubblesort cat si pentru quicksort in schimb pentru timsort nu se poate obtine un timp mai mare ca O(n*log(n)) deci ca performanta timsort > quicksort > bubblesort.

Voi incepe cu cea mai simpla, bubblesort. Sunt luate doua cate doua elemente la rand si sunt schimbate intre ele in caz de nu respecta conditia (primul sa fie mai mic decat al doilea). Cat timp este efectuata cel putin o schimbare se reia procesul de cautare + schimb pana cand nu se va mai gasi niciun element care sa fie mai mare ca urmatorul. De fiecare data cand se reia procesul de cautare se va cauta pana la un index mai mic cu 1 decat cel anterior deoarece pe acea pozitie se stie sigur ca se afla cel mai mare element.

Exemplu:

5 3 6 5 4
... se parcurge pana la penultimul element al vectorului ...
5 > 3 -> adevarat atunci swap -> 3 5 6 5 4
5 > 6 -> fals -> 3 5 6 5 4
6 > 5 -> adevarat atunci swap -> 3 5 5 6 4
6 > 4 -> adevarat atunci swap -> 3 5 5 4 6
... se termina prima parcurgere a vectorului ...
<dupa cum se vede cel mai mare element a fost impins in coada vectorului si au existat schimburi>

3 5 5 4 6
... se parcurge pana la antepenultimul element al vectorului ...
3 > 5 -> fals -> 3 5 5 4 6
5 > 5 -> fals -> 3 5 5 4 6
5 > 4 -> adevarat -> 3 5 4 5 6
... se termina a doua parcurgere a vectorului ...
<dupa cum se vede au existat schimburi iar cel mai mare element in afara de ultimul a fost mutat imediat in stanga ultimului>

3 5 4 5 6
... se parcurge pana la cel din stanga antepenultimului ...
3 > 5 -> fals 3 5 4 5 6
5 > 4 -> adevarat -> 3 4 5 5 6
... se termina a treia parcurgere ...
<desi vectorul e ordonat au existat schimbari>

3 4 5 5 6
... se mai parcurge inca o data vectorul pana la o pozitie cu 1 mai la stanga cazului anterior (acelasi procedeu ca si in celelalte cazuri) ...
3 > 4 -> fals -> 3 4 5 5 6
... se termina a patra parcurgere ...
<vectorul e ordonat si NU au existat schimbari>

sortarea se termina cu rezultatul final: 3 4 5 5 6

Cealalta metoda, quicksort. Se alege si se elimina un element din vector numit pivot (de obicei ultimul). Se creeaza inca 2 vectori goi sa zicem "mic" si "mare". Se ia fiecare element din noul vector format (cel fara pivot) si este comparat cu pivotul, daca este mai mic sau egal cu el elementul este adaugat in "mic" altfel daca este mai mare atunci este adaugat in "mare". Apoi vectorul "mic" este supus aceluiasi procedeu ca si primul vector, este concatenat cu pivot si din nou concatenat cu "mare" care si el la randul lui este supus aceluiasi procedeu cat timp vectorul argument are lungimea mai mare ca 1. Astfel solutia este creeata recursiv prin dezbina si cucereste.

Exemplu:

procedeu(5 3 6 5 4)
pivot1: 4
mic1: 3
mare1: 5 6 5
solutia1 = procedeu(mic1) + pivot1 + procedeu(mare1)

procedeu(3)
solutia2 = 3

procedeu(5 6 5)
pivot3: 5
mic3: 5
mare3: 6
solutia3 = procedeu(mic3) + pivot3 + procedeu(mare3)

procedeu(5)
solutia4 = 5

procedeu(6)
solutia5 = 6

Deci: solutia1 = solutia2 + pivot1 + solutia3 dar solutia3 = solutia4 + pivot3 + solutia5
Astfel: solutia1 = solutia2 + pivot1 + solutia4 + pivot3 + solutia5
Adica: solutia1 = 3 4 5 5 6

Ultima metoda, timsort este un hibrid intre mergesort si insertionsort vezi wiki pentru mai multe detalii. E ceva mai complicat gen quicksort, insa nu este folosit pivotul si se insereaza in alt vector elemente spre deosebire de bubblesort si quicksort care sunt metode de comparatie.

Python 3.x (vezi python.org)

#! /usr/bin/env python3
# 04.01.2011 cmiN

class Sort:
    pyvec = list()
    bubblevec = list()
    quickvec = list()

    def pysort(self, vec):
        return sorted(vec)

    def bubblesort(self, vec):
        flag = True
        length = len(vec)
        j = 1
        while flag:
            flag = False
            for i in range(length - j):
                if vec[i] > vec[i + 1]:
                    tmp = vec[i]
                    vec[i] = vec[i + 1]
                    vec[i + 1] = tmp
                    flag = True
            j += 1
        return vec

    def quicksort(self, vec):
        if len(vec) > 1:
            lss, grt = list(), list()
            piv = vec.pop()
            for x in vec:
                if x <= piv:
                    lss.append(x)
                else:
                    grt.append(x)
            return self.quicksort(lss) + [piv] + self.quicksort(grt)
        else:
            return vec

    def str_to_int(self, vec):
        for i in range(len(vec)):
            vec[i] = int(vec[i])
        return vec

    def __init__(self, vec):
        self.pyvec = self.pysort(vec[:])
        self.bubblevec = self.bubblesort(vec[:])
        self.quickvec = self.quicksort(vec[:])

def show(args):
    for arg in args:
        for x in arg:
            print(x, end=" ")
        print()

def main():
    vec = input("Enter numbers separated by spaces: ")
    sob = Sort(vec.split())
    show([sob.pyvec, sob.bubblevec, sob.quickvec])

if __name__ == "__main__":
    main()

Credite: cmiN (inspirat de pe wiki, am scris doar si la inceput "alora carora le este sila")

Data: 04.01.2011

[BadBoy-ALbania]

Algortmeare simple.