abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 09:55 | Nová verze

Byl vydán Debian 8.11, tj. jedenáctá a současně poslední opravná verze Debianu 8 s kódovým názvem Jessie. Uživatelům je doporučen přechod na Debian 9 Stretch nebo využít LTS (Debian Long Term Support). LTS podpora Debianu 8 je plánována do 30. června 2020. LTS podpora Debianu 7 Wheezy skončila 31. května 2018.

Ladislav Hagara | Komentářů: 0
dnes 09:11 | IT novinky

Hodnota Bitcoinu, decentralizované kryptoměny, klesla pod 6 000 dolarů. Před půl rokem byla hodnota Bitcoinu téměř 20 000 dolarů.

Ladislav Hagara | Komentářů: 12
včera 12:33 | Zajímavý projekt

Kernel.org představil lore.kernel.org, tj. archiv diskusního listu vývojářů linuxového jádra LKML (Linux Kernel Mailing List) s řadou zajímavých funkcí. Archiv běží na softwaru Public Inbox.

Ladislav Hagara | Komentářů: 0
včera 10:55 | Nová verze

Po devíti měsících vývoje od vydání verze 10.0 byla vydána verze 11.0 open source alternativy GitHubu, tj. softwarového nástroje s webovým rozhraním umožňujícího spolupráci na zdrojových kódech, GitLab (Wikipedie). Představení nových vlastností v příspěvku na blogu a na YouTube.

Ladislav Hagara | Komentářů: 1
22.6. 20:44 | Nová verze

Po více než 3 měsících vývoje od vydání verze 238 oznámil Lennart Poettering vydání verze 239 správce systému a služeb systemd (GitHub, NEWS).

Ladislav Hagara | Komentářů: 30
22.6. 15:00 | Nová verze

Bylo oznámeno vydání nové stabilní verze 1.28 a beta verze 1.29 open source textového editoru Atom (Wikipedie). Přehled novinek i s náhledy v příspěvku na blogu. Podrobnosti v poznámkách k vydání. Atom 1.28 je postaven na Electronu 2.0.

Ladislav Hagara | Komentářů: 1
22.6. 14:00 | Nová verze

Byla vydána nová verze 2.3.0 multiplatformního svobodného frameworku pro zpracování obrazu G'MIC (GREYC's Magic for Image Computing, Wikipedie). Přehled novinek i s náhledy na PIXLS.US.

Ladislav Hagara | Komentářů: 0
22.6. 13:00 | Komunita

Akční RPG hra Shadowrun Returns Deluxe, kterou lze hrát i na Linuxu je nyní zdarma na Humble Bundle. Hra vyšla díky kampani na Kickstarteru v roce 2013.

tajny_007 | Komentářů: 0
22.6. 01:00 | Nová verze

Byla vydána verze 1.27 programovacího jazyka Rust (Wikipedie). Z novinek je nutno zmínit podporu SIMD (Single Instruction Multiple Data). Podrobnosti v poznámkách k vydání. Vyzkoušet Rust lze například na stránce Rust by Example.

Ladislav Hagara | Komentářů: 7
21.6. 16:22 | IT novinky

CEO Intelu Brian Krzanich rezignoval (tisková zpráva). Oficiálním důvodem je "vztah na pracovišti". S okamžitou platností se dočasným CEO stal Robert Swan.

Ladislav Hagara | Komentářů: 41
Jak čtete delší texty z webových stránek?
 (77%)
 (22%)
 (4%)
 (7%)
 (2%)
 (11%)
Celkem 253 hlasů
 Komentářů: 39, poslední 21.6. 17:44
    Rozcestník

    Insertion a selection sort (seznam)

    7.5.2017 14:16 | Přečteno: 857× | Ostatní | poslední úprava: 7.5.2017 14:14

    Srovnání prvků v jednosměrném spojovém seznamu.

    Insertion sort - nový seznam nezačíná z ukazatele na strukturu, ale z adresy lokální struktury (dummy head). Pokud je prvek ze starého seznamu menší než poslední prvek z nového seznamu, je připojen před poslední prvek z nového seznamu, jinak je připojen jako poslední. Funkce vrací ukazatel na strukturu newl->next, který ukazuje na začátek nového seznamu.
    typedef struct elem {
    	char name[MAX];	
    	struct elem *next;
    } ELEM;
    
    ELEM *insertionsort(ELEM *oldl)
    {
    	struct elem head;
    	
    	ELEM *newl, *n, *t, *u;
    	
    	newl = &head; 
    	newl->next = NULL;
    	
    	if (oldl == NULL)
    		return NULL;	
    	
    	for (t = oldl; t != NULL; t = u) {
    		u = t->next;
    		for (n = newl; n->next != NULL; n = n->next)			
    			if (strcmp(n->next->name, t->name) > 0) 
    				break;
    		t->next = n->next;
    		n->next = t;
    	}
    	
    	return newl->next;
    }
    
    Selection sort - hledá se uzel, jehož ukazatel next ukazuje na největší prvek. Největší prvek je vypuštěn (prev->next = t->next) a následně připojen na začátek nového seznamu. Pokud je ve starém seznamu největší prvek na začátku, je přesunut na konec, přičemž je třeba posunout začátek. Funkce vrací adresu starého seznamu.
    typedef struct e {
    	int x;	
    	struct e *next;
    } E;
    
    E *selectionsort(E *oldl)
    {
    	E *newl, *prev, *p, *t;
    	
    	newl = NULL;	
    	
    	if (oldl == NULL)
    		return NULL;
    	
    	while (oldl->next != NULL) {
    	
    		t = p = prev = oldl;
    	
    		for (; p->next != NULL; p = p->next)			 
    			if (p->next->x > prev->next->x)				
    				prev = p;		
    		
    		if (t->x > prev->next->x) {		
    			oldl = oldl->next;	
    			prev = p;
    			p->next = t;		
    			t->next = NULL;		
    		}
    				
    		t = prev->next;
    		prev->next = t->next;
    		t->next = newl;
    		newl = t;			
    	}
    	
    	oldl->next = newl;		
    	
    	return oldl;
    }
    
    Z hlediska rychlosti jsou obě funkce vhodné maximálně pro deset tisíc prvků.

    Základ funkcí jsem převzal z knihy Algorithms in C od Roberta Sedgewicka.        

    Hodnocení: 33 %

            špatnédobré        

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    Komentáře

    Vložit další komentář

    7.5.2017 14:42 Radovan
    Rozbalit Rozbalit vše Re: Insertion a selection sort (seznam)
    typedef struct elem {
    	char name[MAX];	
    	struct elem *next1;
    	struct elem *next2;
            ... 
    } ELEM;
    
    ?
    7.5.2017 15:21 sad
    Rozbalit Rozbalit vše Re: Insertion a selection sort (seznam)
    Jestli je to narážka na jiný způsob, tak ten neznám.
    8.5.2017 02:28 Jardík
    Rozbalit Rozbalit vše Re: Insertion a selection sort (seznam)
    Když někde vidím konstantu MAX, tuším, že je to nějaká spatlanina, co má umělá omezení. Jinak pole by vyšlo určitě lépe, než linked list, hlavně kvůli cache.
    8.5.2017 04:33 pc2005 | skóre: 36 | blog: GardenOfEdenConfiguration | liberec
    Rozbalit Rozbalit vše Re: Insertion a selection sort (seznam)
    Jo struktura co má sama sebe v sobě a ještě je z ní typedef je zajímavá :-D. Předpokládám že kompilátoru to pak nevadí že je definováno struct elem a používáno ELEM. Já bych se asi na to ELEM vykašlal je to jen o ušetření 7 bajtů.

    Případné další syntaktické odchylky nejsem schopnej posoudit (aneb pokud to projde checkpatchem a lkml tak pohoda :-D).
    8.5.2017 08:49 sad
    Rozbalit Rozbalit vše Re: Insertion a selection sort (seznam)
    Jo tak v tomhle vidíte problém. A já myslel, že je to narážka na nějaký lepší způsob řazení.

    typedef používám, protože nechci pořád psát struct v hlavičkách funkcí a tenhle zápis mi přijde docela elegantní, i když tohle je asi čistější:
    struct elem {
    	char name[MAX];	
    	struct elem *next;
    };
    
    typedef struct elem ELEM;
    
    Ve velkých projektech je asi lepší typedef nepoužívat (jak radí Linus), ale já jsem si zkoušel naprogramovat jen takovou kravinku.

    Založit nové vláknoNahoru

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.