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 19:22 | Nová verze

Byla vydána verze 11.3 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í i s náhledy v příspěvku na blogu.

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

Do 30. října se lze přihlásit do dalšího kola programu Outreachy (Wikipedie), jehož cílem je přitáhnout do světa svobodného a otevřeného softwaru lidi ze skupin, jež jsou ve světě svobodného a otevřeného softwaru málo zastoupeny. Za 3 měsíce práce, od 4. prosince 2018 do 4. března 2019, v participujících organizacích lze vydělat 5 500 USD.

Ladislav Hagara | Komentářů: 85
21.9. 22:22 | Komunita

Společnost Purism představila kryptografický token Librem Key. Koupit jej lze za 59 dolarů. Token byl vyvinut ve spolupráci se společností Nitrokey a poskytuje jak OpenPGP čipovou kartu, tak zabezpečení bootování notebooků Librem a také dalších notebooků s open source firmwarem Heads.

Ladislav Hagara | Komentářů: 8
21.9. 20:33 | Nová verze

Společnost NVIDIA oficiálně vydala verzi 10.0 toolkitu CUDA (Wikipedie) umožňujícího vývoj aplikací běžících na jejich grafických kartách. Přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 0
21.9. 20:00 | Upozornění

Příspěvek Jak přežít plánovanou údržbu DNS na blogu zaměstnanců CZ.NIC upozorňuje na historicky poprvé podepsání DNS root zóny novým klíčem dne 11. října 2018 v 18:00. Software, který nebude po tomto okamžiku obsahovat nový DNSSEC root klíč, nebude schopen resolvovat žádná data. Druhým důležitým datem je 1. února 2019, kdy významní výrobci DNS softwaru, také historicky poprvé, přestanou podporovat servery, které porušují DNS standard

… více »
Ladislav Hagara | Komentářů: 11
21.9. 15:55 | Pozvánky

Spolek OpenAlt zve příznivce otevřených řešení a přístupu na 156. brněnský sraz, který proběhne v pátek 21. září od 18:00 v restauraci Na Purkyňce na adrese Purkyňova 80.

Ladislav Hagara | Komentářů: 0
21.9. 13:22 | Nová verze

Alan Griffiths z Canonicalu oznámil vydání verze 1.0.0 display serveru Mir (GitHub, Wikipedie). Mir byl představen v březnu 2013 jako náhrada X serveru a alternativa k Waylandu. Dnes Mir běží nad Waylandem a cílen je na internet věcí (IoT).

Ladislav Hagara | Komentářů: 0
20.9. 22:00 | Nasazení Linuxu
Stabilní aktualizace Chrome OS 69 (resp. Chromium OS), konkrétně 69.0.3497.95, přináší mj. podporu linuxových aplikací. Implementována je pomocí virtualizace, a proto je tato funkce také omezena na zařízení s dostatkem paměti a podporou hardwarové akcelerace, tudíž nejsou podporovány chromebooky s 32bitovými architekturami ARM, či Intel Bay Trail (tzn. bez Intel VT-x).
Fluttershy, yay! | Komentářů: 5
20.9. 21:32 | Zajímavý projekt

Došlo k uvolnění linuxové distribuce CLIP OS, vyvíjené francouzským úřadem pro kybernetickou bezpečnost ANSSI, jako open source. Vznikla za účelem nasazení v úřadech, kde je potřeba omezit přístup k důvěrným datům. Je založená na Gentoo.

Fluttershy, yay! | Komentářů: 1
20.9. 16:00 | Komerce

Zjistěte více o bezpečné a flexibilní architektuře v cloudu! IBM Cloud poskytuje bezpečné úložiště pro Vaše obchodní data s možností škálovatelnosti a flexibilitou ukládání dat. Zároveň nabízí prostředky pro jejich analýzu, vizualizaci, reporting a podporu rozhodování.

… více »
Fluttershy, yay! | Komentářů: 12
Na optické médium (CD, DVD, BD aj.) jsem naposledy vypaloval(a) data před méně než
 (13%)
 (15%)
 (21%)
 (23%)
 (25%)
 (4%)
 (1%)
Celkem 399 hlasů
 Komentářů: 33, poslední 16.9. 11:55
Rozcestník

Insertion a selection sort (seznam)

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