LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> Řadící algoritmy

Edituj záznam
Kategorie: Python
Programovací jazyk: Python
Domovská stránka:
Download:
Tvůrce: bubersson
Popis skriptu: Jednoduchá implementace řadících algoritmů bubbleSort, selectSort, quickSort a gnomeSort a ukázka funkčnosti doctestu.
Nároky na klienta: Python 3.0+
Nároky na server:
Kód s komentáři:
#! /usr/bin/env python3.0
# author: bubersson [Petr Mikota]
""" Program s ukázkami jednotlivých sortovacích algoritmů """
__version__ = "0.3"
__author__ = "bubersson@gmail.com"
__license__ = "do whatever"

#-------------------------------------------------------
def bubbleSort(pole):
""" implementuje bubblesort - je stabilní - O(n**2)
>>> bubbleSort([3,6,2,1])
[1, 2, 3, 6]"""
nochange = False
while not nochange:
nochange = True
for i in range(len(pole)-1):
if pole[i] > pole[i+1]:
pole[i],pole[i+1] = pole[i+1],pole[i]
nochange = False
return pole
#-------------------------------------------------------
def selectSort(pole):
""" implementuje selectsort - neni stabilní - O(n**2)
>>> selectSort([3,6,2,1])
[1, 2, 3, 6]"""
index = 0
for i in range(len(pole)):
minimum = pole[i]
for j in range(i,len(pole)):
if pole[j] <= minimum:
minimum = pole[j]
index = j
pole[i],pole[index] = pole[index],pole[i]
return pole
#-------------------------------------------------------
def quickSort(pole):
""" implementuje quicksort - neni stabilní - O(nlogn)
>>> quickSort([3,6,2,1])
[1, 2, 3, 6]"""
if len(pole) > 1:
pivot = pole[0]
right = left = []
for i in range(1,len(pole)):
if pole[i] < pivot:
left = [pole[i]] + left
else:
right = [pole[i]] + right
return quickSort(left)+[pivot]+quickSort(right)
else: return pole
#-------------------------------------------------------
def gnomeSort(pole):
""" implementuje gnomesort - je stabilní - O(n**2)
>>> gnomeSort([3,6,2,1])
[1, 2, 3, 6]"""
i,j=1,2
while i<(len(pole)):
if pole[i-1] <= pole[i]:
i,j=j,j+1
else:
pole[i-1],pole[i]=pole[i],pole[i-1]
i-=1
if i==0: i=1
return pole
#-------------------------------------------------------
def _timing(funkce,data):
from time import clock
t=clock()
funkce(50*data)
done=clock()-t
print((int(10*done))*"#",(10-int(10*done))*".",funkce.__name__,"doba:",done,clock())
return 0
#-------------------------------------------------------
def main():
""" hlavní funkce, která je volána, když je skript spouštěn přímo """
print(__doc__)
#pole=["a","c","f","b","s","a","s","d"]
pole=[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8]
print("bubble",bubbleSort(pole))
pole=[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8]
print("select",selectSort(pole))
pole=[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8]
print("quick",quickSort(pole))
pole=[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8]
print("gnome",gnomeSort(pole))


_timing(sorted,[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8])
_timing(bubbleSort,[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8])
_timing(selectSort,[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8])
_timing(quickSort,[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8])
_timing(gnomeSort,[8,3,5,6,4,7,6,2,1,3,8,5,13,0,12,16,7,6,2,1,7,6,8])


if True:
print("probíhá doctest...",end="")
import doctest
doctest.testmod()
print("hotovo!!")
return 0

if __name__ == '__main__': main()
Zadal/a: bubersson


pridej.cz

> Vyhledávání software
> Vyhledávání článků

8.1.2017 17:51 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 19. ledna od 18:30 v pražském hackerspacu Brmlab. Tentokrát je tématem srazu ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. K vidění bude mechanická klávesnice dasKeyboard, trackball Logitech nebo grafický tablet (a velký touchpad) Wacom. Přineste i vy ukázat svoje zajímavé klávesnice a další HW. V 18:20 je sraz před budovou, v 18:30 jdeme společně dovnitř, je tedy dobré přijít včas. Podle zájmu se později přesuneme do nějaké restaurace v okolí.
Přidat komentář

1.12.2016 22:13 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.
Komentářů: 1

4.9.2016 20:13 /Pavel `Goldenfish' Kysilka
PR: Dne 22.9.2016 proběhne v Praze konference Cloud computing v praxi. Tématy bude např. nejnovější trendy v oblasti cloudu a cloudových řešení, provozování ERP v cloudu, o hostování různých typů softwaru, ale třeba i o zálohování dat nabízeném podnikům formou služby.
Přidat komentář

1.9.2016 11:27 /Honza Javorek
Česká konference o Pythonu, PyCon CZ, stále hledá přednášející skrz dobrovolné přihlášky. Máte-li zajímavé téma, neváhejte a zkuste jej přihlásit, uzávěrka je již 12. září. Konference letos přijímá i přednášky v češtině a nabízí pomoc s přípravou začínajícím speakerům. Řečníci mají navíc vstup zadarmo! Více na webu.
Přidat komentář

27.8.2016 8:55 /Delujek
Dnes po 4 letech komunitního vývoje vyšla diaspora 0.6.0.0
diaspora* je open-source, distribuovaná sociální síť s důrazem na soukromý
Více v oficiálním blog-postu
Přidat komentář

24.8.2016 6:44 /Ondřej Čečák
Poslední týden CFP LinuxDays 2016; pokud byste rádi přednášeli na LinuxDays 2016 8. a 9. října v Praze, můžete svůj příspěvek přihlásit, následovat bude veřejné hlasování.
Přidat komentář

9.8.2016 22:56 /Petr Ježek
Zařazení souborového systému reiser4 do jádra 4.7 znamená konečně konec patchování jádra jen kvůli možnosti použít reiser4.
Přidat komentář

12.7.2016 13:14 /František Kučera
Spolek OpenAlt zve na 130. distribuovaný sraz příznivců svobodného softwaru a otevřených technologií (hardware, 3D tisk, SDR, DIY, makers…), který se bude konat ve čtvrtek 21. července od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

17.1.2017 9:57 / Pavel Hrubeš
Re: Externí USB televizní karta

4.1.2017 11:24 / Marcum
extension to house

3.1.2017 10:09 / bolden
country cottages

4.12.2016 22:54 / František Kučera
Dárek

8.11.2016 13:38 / Mira
Konfigurace maldet na Centos serveru

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze