Ik ben erg benieuwd, waarom is stabiliteit wel of niet belangrijk bij sorteeralgoritmen?
Antwoord 1, autoriteit 100%
Er wordt gezegd dat een sorteeralgoritme stabielis als twee objecten met gelijke sleutels in dezelfde volgorde in de gesorteerde uitvoer verschijnen als ze verschijnen in de invoerarray die moet worden gesorteerd. Sommige sorteeralgoritmen zijn van nature stabiel, zoals Insertion Sort, Merge Sort, Bubble Sort, enz. En sommige sorteeralgoritmen zijn dat niet, zoals Heap Sort, Quick Sort, enz.
Achtergrond: een “stabiel” sorteeralgoritme houdt de items met dezelfde sorteersleutel op volgorde. Stel dat we een lijst hebben met woorden van 5 letters:
peach
straw
apple
spork
Als we de lijst sorteren op alleen de eerste letter van elk woord, zou een stabiele sortering het volgende opleveren:
apple
peach
straw
spork
In een instabielsorteeralgoritme kunnen strawof sporkworden verwisseld, maar in een stabiel algoritme blijven ze in dezelfde relatieve posities (dat wil zeggen, aangezien strawvóór sporkin de invoer verschijnt, verschijnt het ook vóór sporkin de uitvoer).
We kunnen de lijst met woorden sorteren met dit algoritme: stabiel sorteren op kolom 5, dan 4, dan 3, dan 2, dan 1.
Uiteindelijk wordt het goed gesorteerd. Overtuig uzelf daarvan. (trouwens, dat algoritme heet radix sort)
Om uw vraag te beantwoorden, stel dat we een lijst met voor- en achternaam hebben. We worden gevraagd om te sorteren op “op achternaam, dan op eerste”. We kunnen eerst sorteren (stabiel of onstabiel) op de voornaam, dan stabiel sorteren op de achternaam. Na deze sorteringen wordt de lijst voornamelijk op achternaam gesorteerd. Als de achternamen echter hetzelfde zijn, worden de voornamen gesorteerd.
U kunt onstabiele soorten niet op dezelfde manier stapelen.
Antwoord 2, Autoriteit 17%
Een stabiel sorteeralgoritme is degene die de identieke elementen in dezelfde volgorde sorteert, omdat ze in de ingang verschijnen, terwijl onstabiele sortering niet voldoet aan de behuizing. – Ik dank mijn algoritme docent Didem Gozupek om inzicht te geven in algoritmen .
Stabiele sorteeralgoritmen:
- Insertion sorteren
- samenvoegen sorteren
- bubble sort
- TIM SORT
- tellende sorteren
- blok sorteren
- quadort
- -bibliotheek Sorteer
- cocktail shaker sort
- GNOME SORT
- oneven-even sorteren
Onstabiele sorteeralgoritmen:
- heap sort
- selectie sorteren
- shell sortive
- Snel sorteren
- introsort (onderworpen aan QuickSort)
- boom sorteren
- Cycle Sortive
- Smoothsort
- Toernooi sorteren (afhankelijk van Hesapsort)
Antwoord 3, Autoriteit 6%
Sorteerstabiliteit betekent dat records met dezelfde toets hun relatieve volgorde behouden vóór en na het soort.
SO STABILITEIT ZITTEN INDIEN EN ALLEEN INDIEN INDIEN HET PROBLEEM DIE U OPLOSSERT DIE ONDERHOUDEN VAN DIE RELATIEVE BESLAG VERPLICHTEN.
Als u geen stabiliteit nodig hebt, kunt u een snel, geheugen-drinkend algoritme uit een bibliotheek gebruiken, zoals Heateport of Quicksort, en het vergeten.
Als je stabiliteit nodig hebt, is het ingewikkelder. Stabiele algoritmen hebben een hoger big-O CPU- en/of geheugengebruik dan onstabiele algoritmen. Dus als je een grote dataset hebt, moet je kiezen tussen het verslaan van de CPU of het geheugen. Als je beperkt bent in zowel CPU als geheugen, heb je een probleem. Een goed compromis stabiel algoritme is een binaire boomsoort; het Wikipedia-artikelheeft een pathetisch eenvoudige C++-implementatie op basis van de STL.
Je kunt van een onstabiel algoritme een stabiel algoritme maken door het originele recordnummer toe te voegen als de laatste plaatssleutel voor elk record.
Antwoord 4, autoriteit 4%
Het hangt af van wat je doet.
Stel je voor dat je een aantal personenrecords hebt met een veld voor de voor- en achternaam. Eerst sorteert u de lijst op voornaam. Als je de lijst vervolgens sorteert met een stabiel algoritme op achternaam, heb je een lijst gesorteerd op voornaam EN achternaam.
Antwoord 5, autoriteit 3%
Er zijn een paar redenen waarom stabiliteit belangrijk kan zijn. Een daarvan is dat, als twee records niet verwisseld hoeven te worden door ze te verwisselen, je een geheugenupdate kunt veroorzaken, een pagina als vuil wordt gemarkeerd en opnieuw naar schijf (of een ander langzaam medium) moet worden geschreven.
Antwoord 6
Er wordt gezegd dat een sorteeralgoritme stabiel is als twee objecten met gelijke sleutels in dezelfde volgorde in de gesorteerde uitvoer verschijnen als in de ongesorteerde invoerarray. Sommige sorteeralgoritmen zijn van nature stabiel, zoals Insertion Sort, Merge Sort, Bubble Sort, enz. En sommige sorteeralgoritmen zijn dat niet, zoals Heap Sort, Quick Sort, enz.
Elke sorteeralgo die niet stabiel is, kan echter worden gewijzigd om stabiel te zijn. Er kunnen sorteeralgoritme-specifieke manieren zijn om het stabiel te maken, maar in het algemeen kan elk op vergelijking gebaseerd sorteeralgoritme dat van nature niet stabiel is, worden gewijzigd om stabiel te zijn door de sleutelvergelijkingsbewerking te wijzigen, zodat de vergelijking van twee sleutels positie als een factor voor objecten met gelijke sleutels.
Referenties:
http://www.math.uic.edu/ ~leon/cs-mcs401-s08/handouts/stability.pdf
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
Antwoord 7
Ik weet dat hier veel antwoorden op zijn, maar voor mij, dit antwoord, door Robert Harvey, vatte het veel duidelijker samen:
Een stabiele sortering is een sortering die de oorspronkelijke volgorde van de invoerset behoudt, waarbij het [onstabiele] algoritme geen onderscheid maakt tussen twee of meer items.
Antwoord 8
Als je aanneemt dat wat je sorteert alleen getallen zijn en alleen hun waarden identificeren/onderscheiden ze (bijv. elementen met dezelfde waarde zijn identiek), dan is het stabiliteitsprobleem van sorteren zinloos.
Objecten met dezelfde prioriteit bij het sorteren kunnen echter verschillend zijn, en soms is hun relatieve volgorde zinvolle informatie. In dit geval levert onstabiele sortering problemen op.
Je hebt bijvoorbeeld een lijst met gegevens die de tijd [T] van alle spelers bevat om een doolhof met niveau [L] in een game schoon te maken.
Stel dat we de spelers moeten rangschikken op hoe snel ze het doolhof opruimen. Er is echter een aanvullende regel van toepassing: spelers die het doolhof met een hoger niveau schoonmaken, hebben altijd een hogere rang, ongeacht hoe lang de tijdskosten zijn.
Natuurlijk kunt u proberen de gepaarde waarde [T,L] toe te wijzen aan een reëel getal [R] met een algoritme dat de regels volgt en vervolgens alle spelers rangschikken met de waarde [R].
Als stabiel sorteren echter mogelijk is, kunt u de hele lijst eenvoudig sorteren op [T] (Sneller spelers eerst) en vervolgens op [L]. In dit geval wordt de relatieve volgorde van spelers (volgens tijdkosten) niet gewijzigd nadat je ze hebt gegroepeerd op niveau van het doolhof dat ze hebben schoongemaakt.
PS: natuurlijk is de aanpak om twee keer te sorteren niet de beste oplossing voor het specifieke probleem, maar om de kwestie van de poster uit te leggen zou het voldoende moeten zijn.
Antwoord 9
Stabiele sortering geeft altijd dezelfde oplossing (permutatie) op dezelfde invoer.
Bijvoorbeeld [2,1,2] wordt gesorteerd met behulp van stabiele sortering als permutatie [2,1,3] (eerst is index 2, dan index 1 en vervolgens index 3 in gesorteerde uitvoer) Dat betekent dat de uitvoer altijd wordt geschud zelfde manier. Andere niet-stabiele, maar nog steeds correcte permutatie is [2,3,1].
Snel sorteren is geen stabiele sortering en permutatieverschillen tussen dezelfde elementen hangen af van het algoritme voor het kiezen van een pivot. Sommige implementaties worden willekeurig opgepakt en dat kan ervoor zorgen dat snel sorteren verschillende permutaties op dezelfde invoer oplevert met hetzelfde algoritme.
Stabiel sorteeralgoritme is noodzakelijk deterministisch.
Antwoord 10
Enkele meer voorbeelden van de reden om stabiele soorten te willen. Databases zijn een bekend voorbeeld. Neem het geval van een transactiedatabase die achternaam|voornaam, datum|tijdstip van aankoop, artikelnummer, prijs bevat. Stel dat de database normaal wordt gesorteerd op datum|tijd. Vervolgens wordt een zoekopdracht uitgevoerd om een gesorteerde kopie van de database te maken op achternaam | in volgorde van gegevens|tijd zijn.
Een soortgelijk voorbeeld is het klassieke Excel, dat de sortering beperkt tot 3 kolommen tegelijk. Om 6 kolommen te sorteren, wordt gesorteerd met de minst significante 3 kolommen, gevolgd door een sortering met de meest significante 3 kolommen.
Een klassiek voorbeeld van een stabiele radix-sortering is een kaartsorteerder, die wordt gebruikt om te sorteren op een veld met numerieke kolommen met grondtal 10. De kaarten zijn gesorteerd van minst significant cijfer naar meest significant cijfer. Bij elke pas wordt een pak kaarten gelezen en verdeeld in 10 verschillende bakken volgens het cijfer in die kolom. Vervolgens worden de 10 bakken met kaarten in volgorde terug in de invoertrechter geplaatst (“0” kaarten eerst, “9” kaarten als laatste). Dan wordt er nog een pas gedaan door de volgende kolom, totdat alle kolommen zijn gesorteerd. Werkelijke kaartsorteerders hebben meer dan 10 bakken aangezien er 12 zones op een kaart zijn, een kolom leeg kan zijn en er een verkeerd gelezen bak is. Om letters te sorteren zijn 2 doorgangen per kolom nodig, 1e doorgang voor cijfer, 2e doorgang voor de 12 11 zone.
Later (1937) waren er machines voor het verzamelen van kaarten (samenvoegen) die twee kaartspellen konden samenvoegen door velden te vergelijken. De input was twee al gesorteerde pakken kaarten, een master deck en een update deck. De vergaarmachine voegde de twee stapels samen in een nieuwe materiaalbak en een archiefbak, die optioneel werd gebruikt voor master-duplicaten, zodat de nieuwe master-bak alleen updatekaarten zou hebben in het geval van duplicaten. Dit was waarschijnlijk de basis voor het idee achter de originele (bottom-up) merge sortering.