Pramenové třídění - Strand sort

Animace třídění pramenů

Pramenové třídění je rekurzivní třídicí algoritmus který třídí položky seznamu do rostoucího pořadí. Má to Ó (č²) nejhorší časová složitost, ke které dochází, když je vstupní seznam obrácen.^[1] Má to nejlepší případ časová složitost O (n), ke kterému dochází, když je vstupem seznam, který je již seřazen.^[2] Strand druh není na místě protože jeho prostorová složitost je O (n).^[1]

Algoritmus nejprve přesune první prvek seznamu do dílčího seznamu.^[1] Poté porovná poslední prvek v podřízeném seznamu s každým následujícím prvkem v původním seznamu.^[1] Jakmile je v původním seznamu prvek, který je větší než poslední prvek v podřízeném seznamu, je prvek odebrán z původního seznamu a přidán do podřízeného seznamu.^[1] Tento proces pokračuje, dokud se poslední prvek v podřízeném seznamu neporovná se zbývajícími prvky v původním seznamu.^[1] Dílčí seznam je poté sloučen do nového seznamu.^[1] Tento postup opakujte a slučujte všechny dílčí seznamy, dokud nebudou tříděny všechny prvky.^[1] Tento algoritmus se nazývá třídění pramenů, protože v netříděných prvcích jsou prameny seřazených prvků, které se odstraňují jeden po druhém.^[1] Tento algoritmus se také používá v J Třídit pro méně než 40 prvků.^[3]

Příklad

Tento příklad je založen na popisu algoritmu uvedeného v knize, Postupy IT a vznikající paradigmata správy.^[1]

Krok 1: Začněte seznamem čísel: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7}

Krok 2: Dále přesuňte první prvek seznamu do nového podřízeného seznamu: podřízený seznam obsahuje {5}

Krok 3: Pak iterujte původním seznamem a porovnejte každé číslo s 5, dokud nebude číslo větší než 5.

1 <5, takže 1 se nepřidá do podřízeného seznamu.
4 <5, takže 4 není přidán do dílčího seznamu.
2 <5, takže 2 se nepřidá do podřízeného seznamu.
0 <5, takže 0 se nepřidá do podřízeného seznamu.
9> 5, takže 9 je přidán do podřízeného seznamu a odstraněn z původního seznamu.

Krok 4: Nyní porovnejte 9 se zbývajícími prvky v původním seznamu, dokud nebude číslo větší než 9.

6 <9, takže 6 není přidán do dílčího seznamu.
3 <9, takže 3 není přidán do podřízeného seznamu.
8 <9, takže 8 se nepřidá do podřízeného seznamu.
7 <9, takže 7 se nepřidá do podřízeného seznamu.

Krok 5: Nyní neexistují žádné další prvky k porovnání 9, aby se sloučil podřízený seznam do nového seznamu, který se nazývá seznam řešení.

Po kroku 5 původní seznam obsahuje {1, 4, 2, 0, 6, 3, 8, 7}

Dílčí seznam je prázdný a seznam řešení obsahuje {5, 9}

Krok 6: Přesunout první prvek původního seznamu do dílčího seznamu: dílčí seznam obsahuje {1}

Krok 7: Iterujte původním seznamem a porovnávejte každé číslo s 1, dokud nebude číslo větší než 1.

4> 1, takže 4 je přidán do podřízeného seznamu a 4 je odstraněn z původního seznamu.

Krok 8: Nyní porovnejte 4 se zbývajícími prvky v původním seznamu, dokud nebude číslo větší než 4.

2 <4, takže 2 se nepřidá do podřízeného seznamu.
0 <4, takže 0 se nepřidá do podřízeného seznamu.
6> 4, takže 6 se přidá do podřízeného seznamu a odstraní se z původního seznamu.

Krok 9: Nyní porovnejte 6 se zbývajícími prvky v původním seznamu, dokud nebude číslo větší než 6.

3 <6, takže 3 není přidán do dílčího seznamu.
8> 6, takže 8 se přidá do podřízeného seznamu a odstraní se z původního seznamu.

Krok 10: Nyní porovnejte 8 se zbývajícími prvky v původním seznamu, dokud nebude číslo větší než 8.

7 <8, takže 7 není přidán do dílčího seznamu.

Krok 11: Vzhledem k tomu, že v původním seznamu nejsou žádné další prvky, s nimiž by bylo možné porovnávat {8}, je podřízený seznam sloučen se seznamem řešení. Nyní původní seznam obsahuje {2, 0, 3, 7}, podseznam je prázdný a seznam řešení obsahuje: {1, 4, 5, 6, 8, 9}.

Krok 12: Přesuňte první prvek původního seznamu do dílčího seznamu. Dílčí seznam obsahuje {2}

Krok 13: Procházejte původním seznamem a porovnejte každé číslo s 2, dokud nebude číslo větší než 2.

0 <2, takže 0 se nepřidá do podřízeného seznamu.
3> 2, takže 3 se přidá do podřízeného seznamu a odstraní se z původního seznamu.

Krok 14: Nyní porovnejte 3 se zbývajícími prvky v původním seznamu, dokud nebude číslo větší než 3.

7> 3, takže 7 je přidán do podřízeného seznamu a je odstraněn z původního seznamu.

Krok 15: Vzhledem k tomu, že v původním seznamu nejsou žádné další prvky, s nimiž by bylo možné porovnávat {7}, je podřízený seznam sloučen se seznamem řešení. Původní seznam nyní obsahuje {0}, podřízený seznam je prázdný a seznam řešení obsahuje: {1, 2, 3, 4, 5, 6, 7, 8, 9}.

Krok 16: Přesuňte první prvek původního seznamu do dílčího seznamu. Dílčí seznam obsahuje {0}.

Krok 17: Protože původní seznam je nyní prázdný, je podřízený seznam sloučen se seznamem řešení. Seznam řešení nyní obsahuje: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. V původním seznamu již nejsou žádné další prvky a všechny prvky v seznamu řešení byly úspěšně seřazeny do rostoucího číselného pořadí.

Implementace

Protože Strand Sort vyžaduje mnoho vkládání a mazání, je nejlepší při implementaci algoritmu použít propojený seznam.^[2] Propojené seznamy vyžadují konstantní čas pro vkládání i odebírání prvků pomocí iterátorů. Čas procházení propojeným seznamem přímo souvisí se vstupní velikostí seznamu.^[4] Následující implementace se provádí v prostředí Java 8 a je založena na popisu algoritmu z knihy, Postupy IT a vznikající paradigmata správy.^[1]

  1 balík strandSort;  2   3 import java.util. *;  4   5 veřejnost třída strandSort {  6 	statický Spojový seznam<Celé číslo> solList = Nový Spojový seznam<Celé číslo>();  7 	statický int k = 0;  8   9 	/** 10 * Toto je rekurzivní metoda Strand Sort. Trvá v propojeném seznamu 11 * celá čísla jako jeho parametr. Nejprve zkontroluje základní případ, aby zjistil, zda 12 * propojený seznam je prázdný. Poté pokračuje algoritmus třídění Strand až do 13 * propojený seznam je prázdný. 14 	 *  15 * @param origList: 16 * propojený seznam celých čísel 17 	 */ 18 	veřejnost statický prázdnota strandSortIterative(Spojový seznam<Celé číslo> origList) { 19  20 		// Základní pouzdro 21 		-li (origList.je prázdný()) { 22 			vrátit se; 23 		} 24  25 		jiný { 26 			// Vytvořte subList a přidejte první prvek z 27 			// Původní propojený seznam k podřízenému seznamu. 28 			// Poté odeberte první prvek z původního seznamu. 29 			Spojový seznam<Celé číslo> subList = Nový Spojový seznam<Celé číslo>(); 30 			subList.přidat(origList.getFirst()); 31 			origList.removeFirst(); 32  33 			// Iterace původním seznamem a kontrola, zda jsou nějaké prvky 34 			// Větší než prvek v dílčím seznamu. 35 			int index = 0; 36 			pro (int j = 0; j < origList.velikost(); j++) { 37 				-li (origList.dostat(j) > subList.dostat(index)) { 38 					subList.přidat(origList.dostat(j)); 39 					origList.odstranit(j); 40 					j = j - 1; 41 					index = index + 1; 42 				} 43 			} 44 			// Sloučit dílčí seznam do seznamu řešení. 45 			// Pro tento krok existují dva případy / 46 			// Případ 1: První rekurzivní volání, přidejte všechny prvky do 47 			// seznam řešení v postupném pořadí 48 			-li (k == 0) { 49 				pro (int i = 0; i < subList.velikost(); i++) { 50  51 					solList.přidat(subList.dostat(i)); 52 					k = k + 1; 53 				} 54  55 			} 56  57 			// Případ 2: Po prvním rekurzivním volání  58 			// sloučí dílčí seznam se seznamem řešení. 59 			// Funguje to porovnáním největšího prvku v podřízeném seznamu (který je vždy posledním prvkem) 60 			// s prvním prvkem v seznamu řešení.  61 			jiný { 62 				int subEnd = subList.velikost() - 1; 63 				int solStart = 0; 64 				zatímco (!subList.je prázdný()) { 65  66 					-li (subList.dostat(subEnd) > solList.dostat(solStart)) { 67 						solStart++; 68  69 					} jiný { 70 						solList.přidat(solStart, subList.dostat(subEnd)); 71 						subList.odstranit(subEnd); 72 						subEnd--; 73 						solStart = 0; 74 					} 75  76 				} 77  78 			} 79  80 			strandSortIterative(origList); 81 		} 82  83 	} 84  85 	veřejnost statický prázdnota hlavní(Tětiva[] args) { 86 		// Vytvořit nový propojený seznam celých čísel 87 		Spojový seznam<Celé číslo> origList = Nový Spojový seznam<Celé číslo>(); 88  89 		// Přidejte následující celá čísla do propojeného seznamu: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7} 90  91 		origList.přidat(5); 92 		origList.přidat(1); 93 		origList.přidat(4); 94 		origList.přidat(2); 95 		origList.přidat(0); 96 		origList.přidat(9); 97 		origList.přidat(6); 98 		origList.přidat(3); 99 		origList.přidat(8);100 		origList.přidat(7);101 102 		strandSortIterative(origList);103 		// Vytiskněte seznam řešení104 		pro (int i = 0; i < solList.velikost(); i++) {105 			Systém.ven.tisk(solList.dostat(i));106 		}107 108 	}109 110 }

Reference

^ ^A ^b ^C ^d ^E ^F ^G ^h ⁱ ^j ^k Postupy s podporou IT a vznikající paradigmata správy. Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research. (1. vyd.). Indore: Prestige Institute of Management and Research. 2008. ISBN 9788174466761. OCLC 641462443.CS1 maint: ostatní (odkaz)
^ ^A ^b "třídění pramenů". xlinux.nist.gov. Citováno 2018-11-06.
^ Sudipta., Mukherjee (2008). Datové struktury využívající problémy a řešení C: 1000. Nové Dillí: Tata McGraw-Hill. ISBN 9780070667655. OCLC 311311576.
^ „LinkedLists“. www.cs.cmu.edu. Citováno 2018-11-06.

[:0-1] A ^b ^C ^d ^E ^F ^G ^h ⁱ ^j ^k Postupy s podporou IT a vznikající paradigmata správy. Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research. (1. vyd.). Indore: Prestige Institute of Management and Research. 2008. ISBN 9788174466761. OCLC 641462443.CS1 maint: ostatní (odkaz)

[:1-2] A ^b "třídění pramenů". xlinux.nist.gov. Citováno 2018-11-06.

[3] Sudipta., Mukherjee (2008). Datové struktury využívající problémy a řešení C: 1000. Nové Dillí: Tata McGraw-Hill. ISBN 9780070667655. OCLC 311311576.

[4] „LinkedLists“. www.cs.cmu.edu. Citováno 2018-11-06.

[1]

[2]

[3]

[4]