Ordenatze algoritmo

Konputazioan eta matematiketan ordenazio algoritmoa zerrenda edo bektore baten elementuak ordena-erlazio batek emandako sekuentzia batean jartzen duen algoritmoa da, hau da, irteeraren emaitza sarrerako permutazio bat edo berrantolaketa izan behar da. Ordena erlazio erabilienak orden numerikoa eta orden lexikografikoa dira .Antolamendu eraginkorrak garrantzitsuak dira azkar exekutatzeko, zerrenda ordenatuak behar dituzten beste algoritmo batzuen (hala nola bilaketa- eta fusio-algoritmoen) erabilera optimizatzeko. Datuak kanonikoki jartzeko eta gizakiek irakurtzeko moduko emaitzak sortzeko ere balio du.

Quicksort ekintza ausazko zenbakien zerrenda batean. Lerro horizontalak ardatz- balioak dira.

Informatika hasi zenetik, ordenatzeko arazoak ikerketa asko erakarri ditu, agian, modu erraz eta familiarra izan arren, modu eraginkorrean ebazteko konplexutasuna dela eta. Adibidez, BubbleSort[1] 1956. urteaz geroztik aztertu da. Askok konpondutako arazoa dela uste badute ere, gaur egun ordenatzeko algoritmo erabilgarriak asmatzen jarraitzen dute (adibidez, liburutegi sorta 2004an argitaratu zen lehenengo aldiz). Ordenatzeko algoritmoak informatikako sarrera klaseetan ohikoak dira,non problemarako algoritmoen ugaritasunak sarrera atsegina ematen baitu algoritmoen nukleo-kontzeptuen aniztasunari buruz, esate baterako, O notazioa, zatitu eta konkistatzeko algoritmoak, datu egiturak., txarrena, onena eta batez besteko kasuen azterketa eta muga txikiagoak.

Sailkapena

Ordenatzeko algoritmoak modu hauetan sailka daitezke [2] :

  • Ohikoena ordenazioa egiten den lekuaren arabera sailkatzea da
  • Eskaera egiteko behar den denboraren arabera, dagoeneko ordenatuta edo alderantziz ordenatuak:
    • Ordenatzeko algoritmo naturalak : jada ordenatua dagoenean ahalik eta denbora gutxien hartzen du.
    • Naturarik gabeko ordenako algoritmoak : alderantziz ordenatua dagoenean ahalik eta denbora gutxien hartzen du.
  • Egonkortasuna lortzeko: ordena egonkor batek hasieran gako berdinak zituzten elementuak izan zuten ordena erlatiboa mantentzen du. Adibidez, dataren arabera ordenatutako zerrenda berriz ordenatzen bada ordena egonkorreko algoritmo bat erabilita , gako alfabetikoa berdina duten elementu guztiak data ordenan egongo dira. Beste kasu bat letra larriak eta xeheak interesgarriak ez direnean izango litzateke, baina aBC gako bat AbC baino lehenago egongo balitz, emaitzan bi gakoak batera egotea nahi da eta jatorrizko ordenean horrela: aBC, AbC. Elementuak bereiztezinak direnean (elementu bakoitza gako osoaren bidez ordenatzen delako), egonkortasuna ez da interesatzen. Egonkorrak ez diren antolamendu-algoritmoak egonkor bilaka daitezke. Hori egiteko modu bat, ordenamenduaren gakoa artifizialki aldatzea da, zerrendako jatorrizko kokapenak ordenamenduaren parte har dezan, bat egiten badu.

Algoritmoak ezaugarri hauen arabera bereizten dira:

  • Konplexutasun konputazionala (kasurik okerrena, batez besteko kasua eta kasurik onena) n, zerrenda edo matrize neurriei dagokienez. Horretarako, funtzio baten ordena kontzeptua erabiltzen da eta O ( n ) notazioa erabiltzen da. Sailkapenaren portaera onena (gako egitura ustiatzen ez bada) O ( n log n ) da. Algoritmo errazena koadratikoak dira, O (n ²) da. Ordenatzeko gakoen egitura aprobetxatzen duten algoritmoek (adibidez, bucket sort ) O ( kn ) ordena dezakete non k gako-espazioaren tamaina den. Oro har tamaina aldez aurretik ezaguna denez, algoritmo horiek errendimendu lineala dutela esan daiteke, hau da, O ( n ).
  • Memoria eta bestelako baliabide konputazionalak erabiltzea. O ( n ) notazioa ere erabiltzen da.

Egonkortasuna

Ordenamendu-algoritmo egonkorrek erabateko ordenari eusten diote. Horrek esan nahi du algoritmo bat egonkorra dela soilik gako bera duten bi R eta S erregistro daudenean, eta R jatorrizko zerrendan S baino lehenago agertzen denean.

Elementu berdinak (bata bestearengandik bereizten ez direnean), esate baterako, zenbaki osoak edo, orokorrean, edozein datu mota, elementu osoak gakoa direnean, egonkortasuna ez da arazoa. Nolanahi ere, hurrengo zenbaki bikoteak lehen osagaiaren arabera ordenatuko dira.

 (4, 1) (3, 7) (3, 1) (5, 6)

Kasu honetan bi emaitza posible dira, eta horietako bat erregistroen ordena erlatiboa mantentzen da gako berdinekin, eta bestean ez:

 (3, 7) (3, 1) (4, 1) (5, 6) (ordena gordeta)
(3, 1) (3, 7) (4, 1) (5, 6) (ordena aldatu da)

Ordena gabeko algoritmo ezegonkorrek erregistroen ordena erlatiboa alda dezakete gako berdinekin, baina algoritmo egonkorrak ez dute sekula egiten. Algoritmo ezegonkorrak egonkorrak izan daitezen ezar daitezke. Horretarako modu bat gakoen parekatzea artifizialki zabaltzea da, beraz, gako berdinak dituzten bi objektuen arteko konparazioak jatorrizko sarrerako ordena erabiliz erabaki behar da. Gako berdinak dituzten bi objektuen arteko ordena hau gogoratzea ez da konponbide egokia, oro har biltegiratze osagarriak erabiltzea dakarrelako.

Lehen mailako, bigarren mailako, hirugarren mailako... gakoen arabera ordenatzea edozein ordenazio metodo erabiliz egin daiteke, gako guztiak kontuan hartuta (hau da, gako konposatu bakarra erabiliz). Ordenatzeko metodoa egonkorra bada, posible da hainbat elementu ordenatzea, aldi bakoitzean beste gako batekin. Kasu honetan, gakoak aplikatu behar dira lehentasuna handitzeko.

Adibidea: ordenatu zenbaki bikoteak, bi balioak erabiliz

 (4, 1) (3, 7) (3, 1) (4, 6) (originala) 
 (4, 1) (3, 1) (4, 6) (3, 7) (bigarren balioaren arabera ordenatu ondoren)
(3, 1) (3, 7) (4, 1) (4, 6) (lehenengo balioaren arabera ordenatu ondoren)

Bestalde:

 (3, 7) (3, 1) (4, 1) (4, 6) (lehenengo balioaren arabera ordenatu ondoren)
(3, 1) (4, 1) (4, 6) (3, 7) (bigarren balioaren arabera ordenatu ondoren, lehen balioaren araberako ordena aldatu da)


Erreferentziak
  1. «Bubble Sort: An Archaeological Algorithmic Analysis» users.cs.duke.edu (Noiz kontsultatua: 2020-07-14).
  2. «Ordenación de Vectores I – Numerentur.org» numerentur.org (Noiz kontsultatua: 2020-07-14).

Ikus, gainera

Kanpo estekak
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.