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

    Byl vydán Nextcloud Hub 8. Představení novinek tohoto open source cloudového řešení také na YouTube. Vypíchnout lze Nextcloud AI Assistant 2.0.

    Ladislav Hagara | Komentářů: 0
    dnes 13:33 | Nová verze

    Vyšlo Pharo 12.0, programovací jazyk a vývojové prostředí s řadou pokročilých vlastností. Krom tradiční nadílky oprav přináší nový systém správy ladících bodů, nový způsob definice tříd, prostor pro objekty, které nemusí procházet GC a mnoho dalšího.

    Pavel Křivánek | Komentářů: 4
    dnes 04:55 | Zajímavý software

    Microsoft zveřejnil na GitHubu zdrojové kódy MS-DOSu 4.0 pod licencí MIT. Ve stejném repozitáři se nacházejí i před lety zveřejněné zdrojové k kódy MS-DOSu 1.25 a 2.0.

    Ladislav Hagara | Komentářů: 30
    včera 17:33 | Nová verze

    Canonical vydal (email, blog, YouTube) Ubuntu 24.04 LTS Noble Numbat. Přehled novinek v poznámkách k vydání a také příspěvcích na blogu: novinky v desktopu a novinky v bezpečnosti. Vydány byly také oficiální deriváty Edubuntu, Kubuntu, Lubuntu, Ubuntu Budgie, Ubuntu Cinnamon, Ubuntu Kylin, Ubuntu MATE, Ubuntu Studio, Ubuntu Unity a Xubuntu. Jedná se o 10. LTS verzi.

    Ladislav Hagara | Komentářů: 13
    včera 14:22 | Komunita

    Na YouTube je k dispozici videozáznam z včerejšího Czech Open Source Policy Forum 2024.

    Ladislav Hagara | Komentářů: 2
    včera 13:22 | Nová verze

    Fossil (Wikipedie) byl vydán ve verzi 2.24. Jedná se o distribuovaný systém správy verzí propojený se správou chyb, wiki stránek a blogů s integrovaným webovým rozhraním. Vše běží z jednoho jediného spustitelného souboru a uloženo je v SQLite databázi.

    Ladislav Hagara | Komentářů: 0
    včera 12:44 | Nová verze

    Byla vydána nová stabilní verze 6.7 webového prohlížeče Vivaldi (Wikipedie). Postavena je na Chromiu 124. Přehled novinek i s náhledy v příspěvku na blogu. Vypíchnout lze Spořič paměti (Memory Saver) automaticky hibernující karty, které nebyly nějakou dobu používány nebo vylepšené Odběry (Feed Reader).

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

    OpenJS Foundation, oficiální projekt konsorcia Linux Foundation, oznámila vydání verze 22 otevřeného multiplatformního prostředí pro vývoj a běh síťových aplikací napsaných v JavaScriptu Node.js (Wikipedie). V říjnu se verze 22 stane novou aktivní LTS verzí. Podpora je plánována do dubna 2027.

    Ladislav Hagara | Komentářů: 0
    včera 04:22 | Nová verze

    Byla vydána verze 8.2 open source virtualizační platformy Proxmox VE (Proxmox Virtual Environment, Wikipedie) založené na Debianu. Přehled novinek v poznámkách k vydání a v informačním videu. Zdůrazněn je průvodce migrací hostů z VMware ESXi do Proxmoxu.

    Ladislav Hagara | Komentářů: 0
    včera 04:11 | Nová verze

    R (Wikipedie), programovací jazyk a prostředí určené pro statistickou analýzu dat a jejich grafické zobrazení, bylo vydáno ve verzi 4.4.0. Její kódové jméno je Puppy Cup.

    Ladislav Hagara | Komentářů: 0
    KDE Plasma 6
     (73%)
     (9%)
     (2%)
     (16%)
    Celkem 796 hlasů
     Komentářů: 4, poslední 6.4. 15:51
    Rozcestník

    Insertion a selection sort (seznam)

    7.5.2017 14:16 | Přečteno: 1070× | 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: 38 | 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.