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

Do aplikace pro instant messaging Telegram (Wikipedie) lze nově nahrát češtinu. Více v příspěvku na blogu Telegramu.

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

Jean-Baptiste Kempf, prezident neziskové organizace VideoLAN stojící za svobodným multiplatformním multimediálním přehrávačem a frameworkem VLC, oznámil v příspěvku na svém blogu vydání první oficiální verze 0.1.0 v říjnu představeného dekodéru svobodného videoformátu AV1 (AOMedia Video 1) s názvem dav1d (Dav1d is an AV1 Decoder). Jedná se o alternativu k referenčnímu dekodéru libaom. Kódový název dav1da verze 0.1.0 je Gazelle.

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

Po více než dvou letech od vydání verze 11.0 byla vydána nová major verze 12.0 svobodného unixového operačního systému FreeBSD. Podrobný přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 4
11.12. 19:55 | Nová verze

Byla vydána verze 3.11 živé linuxové distribuce Tails (The Amnesic Incognito Live System), jež klade důraz na ochranu soukromí uživatelů a anonymitu. Přehled změn v příslušném seznamu. Řešena je řada bezpečnostních chyb.

Ladislav Hagara | Komentářů: 0
11.12. 15:22 | Nová verze

Byl vydán Mozilla Firefox 64.0. Přehled novinek v poznámkách k vydání a na stránce věnované vývojářům. Nejnovější verze tohoto webového prohlížeče přináší například ovládání více panelů, nebo správce úloh, který lze otevřít v nabídce Firefoxu > Více > Správce úloh, nebo napsáním about:performance do adresního řádku.

Ladislav Hagara | Komentářů: 8
11.12. 13:00 | Zajímavý článek Ladislav Hagara | Komentářů: 0
10.12. 22:33 | Nová verze

Po 3 měsících vývoje od vydání verze 14 byla vydána nová stabilní verze 15 open source systému Nextcloud, forku ownCloudu, umožňujícího provoz vlastního cloudového úložiště. Přehled novinek i s náhledy v příspěvku na blogu. Pro vyzkoušení Nextcloudu je k dispozici demo.

Ladislav Hagara | Komentářů: 6
10.12. 18:00 | IT novinky

Počítačová hra Doom slaví 25 let. Společností id Software ji vydala 10. prosince 1993. Zahrát si ji lze například na Internet Archive.

Ladislav Hagara | Komentářů: 17
9.12. 23:55 | Zajímavý článek

Nakladatelství Raspberry Pi vydalo 244 stránkového průvodce pro úplné začátečníky s jednodeskovým počítačem Raspberry Pi The Official Raspberry Pi Beginner’s Guide (pdf). Programování ve visuálním programovacím jazyce Scratch je věnována nová příručka Code Club Book of Scratch Volume 1 (pdf). Vydáno bylo také třetí číslo časopisu věnovaného počítačovým hrám Wireframe (pdf).

Ladislav Hagara | Komentářů: 0
9.12. 23:44 | Nová verze

U příležitosti oslav jednoho roku prací na debianím balíčku, vyšlo GPXSee 7.0. Nová verze přináší zejména podporu vektorových map (Mapbox PBF) pomocí nově vzniklého Qt pluginu.

Martin Tůma | Komentářů: 8
Chystáte se přejít na Wayland na „desktopu“?
 (25%)
 (6%)
 (12%)
 (30%)
 (27%)
Celkem 111 hlasů
 Komentářů: 14, poslední 10.12. 12:19
Rozcestník

Insertion a selection sort (seznam)

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