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ů

18.6.2018 0:43 /František Kučera

Červnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 21. 6. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: F-Droid, aneb svobodný software do vašeho mobilu. Kromě toho budou k vidění i vývojové desky HiFive1 se svobodným/otevřeným čipem RISC-V.


Přidat komentář

23.5.2018 20:55 /Ondřej Čečák
Od pátku 25.5. proběhne na Fakultě informačních technologií ČVUT v Praze openSUSE Conference. Můžete se těšit na spostu zajímavých přednášek, workshopů a také na Release Party nového openSUSE leap 15.0. V na stejném místě proběhne v sobotu 26.5. i seminář o bezpečnosti CryptoFest.
Přidat komentář

20.5.2018 17:45 /Redakce Linuxsoft.cz
Ve čtvrtek 31. května 2018 připravuje webový magazín BusinessIT ve spolupráci s Best Online Média s.r.o. pátý ročník odborné konference Firemní informační systémy 2018. Akce proběhne v kongresovém centru Vavruška (palác Charitas), Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00 hod. dopoledne do cca 15 hod. odpoledne. Konference je zaměřena na efektivní využití firemních informačních systémů a na to, jak plně využít jejich potenciál. Podrobnější informace na webových stránkách konfrence.
Přidat komentář

14.5.2018 7:28 /František Kučera
Květnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 17. 5. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: Audio – zvuk v GNU/Linuxu.
Přidat komentář

7.5.2018 16:20 /František Kučera
Na stránkách spolku OpenAlt vyšla fotoreportáž Pražské srazy 2017 dokumentující srazy za uplynulý rok. Květnový pražský sraz na téma audio se bude konat 17. 5. 2018 (místo a čas ještě upřesníme).
Přidat komentář

17.4.2018 0:46 /František Kučera
Dubnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 4. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tématem tohoto srazu bude OpenStreetMap (OSM) aneb svobodné mapy.
Přidat komentář

16.3.2018 22:01 /František Kučera
Kulatý OpenAlt sraz v Praze oslavíme klasicky: u limonády a piva! Přijďte si posedět, dát si dobré jídlo a vybrat z mnoha piv do restaurace Kulový blesk, který najdete v centru Prahy nedaleko metra I. P. Pavlova na adrese Sokolská 13, Praha 2. Sraz se koná ve čtvrtek 22. března a začínáme v 18:00. Heslo: OpenAlt. Vezměte s sebou svoje hračky! Uvítáme, když si s sebou na sraz vezmete svoje oblíbené hračky. Jestli máte nějaký drobný projekt postavený na Arduinu, nějakou zajímavou elektronickou součástku, či třeba i pěkný úlovek z crowdfundingové akce, neváhejte. Oslníte ostatní a o zábavu bude postaráno.
Přidat komentář

13.2.2018 0:41 /František Kučera
Únorový pražský sraz OpenAltu se koná 15. 2. 2018 a tentokrát se vydáme na návštěvu do jednoho pražského datacentra. Sejdeme se v 17:50 v severovýchodní části nástupiště tramvajové zastávky Koh-I-Noor. Po exkurzi se přesuneme do restaurace U Pštrosa (Moskevská 49), kde probereme tradiční témata (svobodný software a hardware, DIY, CNC, SDR, 3D tisk…) a tentokrát bude k vidění i IoT brána od The Things Network.
Přidat komentář

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

> Poslední diskuze

20.2.2018 18:48 / Ivan Majer
portal

20.2.2018 15:57 / Jan Havel
Jak využíváte služby cloudu v podnikání?

16.1.2018 1:08 / Ivan Pittner
verejna ip od o2 ubuntu

15.1.2018 17:26 / Mira Harvalik
Re: Jak udělat HTML/Javascript swiping gallery do mobilu?

30.12.2017 20:16 / Michal Knoll
odmocnina

Více ...

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