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í
×
včera 15:44 | Nová verze

Byla vydána nová major verze open source komunikačního softwaru Jami (Wikipedie, GitLab). Její název je Free as in Freedom. Dřívější názvy projektu Jami byly SFLphone a následně Ring.

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

Společnost MNT Research má v plánu na Crowd Supply spustit kampaň na podporu open source notebooku MNT Reform. Vývoj notebooku lze sledovat na Mastodonu.

Ladislav Hagara | Komentářů: 16
včera 00:11 | Zajímavý software

Chcete si zahrát víceuživatelský tetris v terminálu? Stačí spustit ssh netris.rocketnine.space. Na straně serveru běží netris. Zdrojové kódy v programovacím jazyce Go jsou k dispozici pod licencí GPLv3.

Ladislav Hagara | Komentářů: 0
19.11. 19:44 | Nová verze

Po čtyřech měsících vývoje od vydání verze 4.10 byla vydána nová verze 4.11 svobodné náhrady proprietárních BIOSů a UEFI coreboot (Wikipedie). Na vývoji se podílelo 130 vývojářů. Provedli 1630 změn. Přidána byla podpora pro 25 mainboardů.

Ladislav Hagara | Komentářů: 0
19.11. 16:22 | Nová verze

Byla vydána verze 1.6.0 emulátoru terminálu Terminology (GitHub) postaveného nad EFL (Enlightenment Foundation Libraries). Přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 0
19.11. 14:22 | Komunita

Vydání verze 1.0 svobodného multiplatformního vektorového grafického editoru Inkscape se blíží. Registrovaní uživatelé mají možnost hlasovat o obrázku, který bude zobrazován v okně O Inkscapu. Vybírá se ze 124 návrhů.

Ladislav Hagara | Komentářů: 8
19.11. 10:55 | Nová verze

Byl aktualizován seznam 500 nejvýkonnějších superpočítačů na světě TOP500. V první desítce se nic nezměnilo. Nejvýkonnějším superpočítačem zůstává superpočítač Summit. Nejvíce superpočítačů v TOP500 má Čína (228). Český superpočítač Salomon klesl na 375. místo. Další přehledy a statistiky na stránkách projektu. V aktuálním žebříčku GREEN500 (GFlops/watts) superpočítač Summit klesl na 5. místo.

Ladislav Hagara | Komentářů: 3
19.11. 02:00 | Zajímavý článek

V novém příspěvku na blogu Purismu se můžete dočíst, jak pokračoval vývoj softwaru Librem 5 v říjnu. Vývojáři optimalizovali linuxové jádro a ovladače pro snížení spotřeby telefonu. Mezi další změny patří lepší integrace mezi aplikacemi pomocí knihovny libfolks, byly přidány nové funkce klávesnice, nastavení, shellu, kompozitoru a opraveno plno chyb.

okias | Komentářů: 3
19.11. 01:55 | Nová verze

Na Humble Bundle byla spuštěna akce Humble Book Bundle: Cybersecurity 2019 by Packt. Všech 22 videokurzů a elektronických knih věnovaných kybernetické bezpečnosti od nakladatelství Packt lze koupit za 15 dolarů. Peníze lze libovolně rozdělit mezi nakladatelství Packt, neziskovou organizaci Arthritis Foundation a Humble Bundle.

Ladislav Hagara | Komentářů: 0
18.11. 23:22 | Zajímavý článek

Ben Cox v článku Jak psát ovladače nepodporovaných USB zařízení pro uživatelský prostor ukazuje, jak reverzním inženýrstvím dospěl k vlastnímu ovladači userspace-vga2usb pro převodník a frame grabber Epiphan VGA2USB LR s již nepodporovaným linuxovým ovladačem od výrobce.

Fluttershy, yay! | Komentářů: 0
Jaké hodinky nosíte (nejčastěji)?
 (24%)
 (5%)
 (15%)
 (55%)
Celkem 276 hlasů
 Komentářů: 28, poslední včera 20:38
Rozcestník

Insertion a selection sort (seznam)

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