Insertion a selection sort (seznam)

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

Komentáře

[Radovan]

typedef struct elem {
	char name[MAX];	
	struct elem *next1;
	struct elem *next2;
        ... 
} ELEM;

?

[sad]

Jestli je to narážka na jiný způsob, tak ten neznám.

[Jardík]

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.

[pc2005]

Jo struktura co má sama sebe v sobě a ještě je z ní typedef je zajímavá . 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 ).

[sad]

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.