Gnome sort

El algoritmo de ordenación conocido como gNome_sort tiene una historia de invención cuasi paralela. Durante un tiempo existió la polémica sobre su invención, finalmente atribuida a Hamid Sarbazi-Azad quien lo desarrolló en el año 2000 y al que llamó Stupid sort (Ordenamiento estúpido).

Cuando Dick Grune lo inventó (más apropiadamente, lo reinventó) y documentó,^[1] no halló evidencias de que existiera y en palabras suyas, dijo de él "the simplest sort algorithm"^[2] (es el algoritmo más simple) y quizás tenga razón, pues lo describió en sólo cuatro líneas de código. Dick Grune se basó en los gnomos de jardín holandés y la manera en que se colocan dentro de los maceteros (ver la referencia anterior) y de ahí también el nombre que le dio.

Netamente es un algoritmo de burbuja con una clara particularidad: recorre el array a ordenar como una cremallera, en un vaivén, o bien puede ser definido como un ordenamiento de burbuja bidireccional, que a su vez son llamados también cocktail shaker (agitador de cócteles), por la forma en que trabaja...

Cumple estrictamente hablando con la complejidad O(n²).

Descripción

El algoritmo empieza comparando la primera pareja de valores. Si están en orden incrementa el puntero y vuelve a realizar la comparación: si no están en orden, se pasa el menor a la izquierda y el mayor a la derecha, y se reduce el puntero. Ahora la comparación es con el elemento anterior, y si no hay un elemento anterior se pasa al siguiente elemento. Cuando el puntero alcanza el extremo superior del array, ya está totalmente ordenado.

Cuando compara hacia arriba va sin hacer intercambios, es que el par bajo examen está ordenado entre sí, y cuando compara hacia abajo, va haciendo intercambios. El proceso aparece como un zigzagueo continuo a un lado y otro.

La operación empieza por el puntero en el punto más bajo y cuando llega al extremo superior ha terminado de ordenar el array.

Para realizar un ordenamiento inverso basta cambiar la decisión de intercambio de los elementos, es decir, dejar los mayores abajo y los menores arriba.

Pseudocódigo

  i ← 1
  Mientras i ≤ len- 1
    Si a[i-1] ≤ a[i]
        i ← i+1
    Sino
        temp ← a[i-1]
        a[i-1] ← a[i]
        a[i] ← temp
        i ← i-1
        Si i = 0
          i ← 1
        Finsi
    Finsi
  FinMientras

Referencias

Enlaces externos

Datos: Q936797

Read other articles:

Taruk

Artikel ini memiliki beberapa masalah. Tolong bantu memperbaikinya atau diskusikan masalah-masalah ini di halaman pembicaraannya. (Pelajari bagaimana dan kapan saat yang tepat untuk menghapus templat pesan ini) Topik artikel ini mungkin tidak memenuhi kriteria kelayakan umum. Harap penuhi kelayakan artikel dengan: menyertakan sumber-sumber tepercaya yang independen terhadap subjek dan sebaiknya hindari sumber-sumber trivial. Jika tidak dipenuhi, artikel ini harus digabungkan, dialihkan ke cak...

Dancing with the Stars (Amerika Serikat)

Dancing with the StarsGenreReality competitionBerdasarkanStrictly Come DancingSutradaraAlex RudzinskiPresenterTom BergeronLisa Canning (2005)Samantha Harris (2006–09)Drew Lachey (2007)Brooke Burke-Charvet (2010–)JuriCarrie Ann InabaLen GoodmanBruno TonioliNaratorAlan DedicoatNegara asalUnited StatesBahasa asliEnglishJmlh. musim17Jmlh. episode320 (per 26 November, 2013)ProduksiProduser eksekutifAshley Edens-ShafferConrad GreenJoe SungkurDurasi40–80 menitRumah produksiBBC Worldwide Produ...

Tawangsari, Sukoharjo

Untuk tempat lain yang bernama sama, lihat Tawangsari. TawangsariKecamatanPeta lokasi Kecamatan TawangsariNegara IndonesiaProvinsiJawa TengahKabupatenSukoharjoPopulasi (2021)[1] • Total52.750 jiwaKode pos-Kode Kemendagri33.11.03 Kode BPS3311030 Luas39,98 km²Desa/kelurahan12 Tawangsari (Hanacaraka: ꦠꦮꦁꦱꦫꦶ, Jawa: Tawangsari) adalah sebuah kecamatan di Kabupaten Sukoharjo, Jawa Tengah. Selayang Pandang Beberapa fasilitas umum yang ada di Tawangsari ...

Human-centered design

Approach to design that considers human needs at every step of development Not to be confused with User-centered design or Design thinking. Human-centered design (HCD, also human-centred design, as used in ISO standards) is an approach to problem-solving commonly used in process, product, service and system design, management, and engineering frameworks that develops solutions to problems by involving the human perspective in all steps of the problem-solving process. Human involvement typical...

العلاقات الكوبية المالية

العلاقات الكوبية المالية كوبا مالي كوبا مالي تعديل مصدري - تعديل العلاقات الكوبية المالية هي العلاقات الثنائية التي تجمع بين كوبا ومالي.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة كوبا مالي المساحة (كم2...

Williams FW41

Williams FW41FW41 dikemudikan oleh Lance Stroll pada Grand Prix Austria 2018KategoriFormula SatuKonstruktorWilliams–MercedesPerancangPaddy Lowe (Direktur Teknis)[1]Ed Wood (Kepala Perancang)Dirk de Beer (Kepala Aerodinamika)[2]PendahuluWilliams FW40PenerusWilliams FW42Spesifikasi teknis[3][4][5]SasisMonocoque serat karbon, dilaminasi dari epoksi karbon berbentuk sarang lebahSuspensi (depan)Wishbone atas dan bawah, pegas dalam dan peredam yang dige...

Maizerets

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Maizerets – news · newspapers · books · scholar · JSTOR (December 2016) (Learn how and when to remove this template message) Church in Québec ville, Québec, Cánada Maizerets is a neighbourhood of the la Cité-Limoilou borough of Quebec City, Quebec, Canada t...

Ceretani

The Iberian Peninsula in the 3rd century BC. The Cerretani or Ceretani were ancient pre-Roman people of the Iberian Peninsula who occupied what became the modern-day Cerdanya, in the valley Segre and part of Aragon. Their neighbours from the east were Ausetani and from the south Ilergetes. Their capital was Julia libyca, modern Llívia.[1] They are noted in Greek and Roman geographical treatises.[2] References ^ Spain, Encyclopaedia Britannica (5 ed.), 1815, p. 492 ^...

IRAS 13224-3809

Galaxy containing well-studied supermassive black hole IRAS 13224-3809Observation data (J2000[1] epoch)ConstellationCentaurus[2]Right ascension13h 25m 19.38s[1]Declination−38° 24′ 52.61″[1]Redshift0.06580 ± 0.00018Distance1 billion light-years[3]Apparent magnitude (V)13.80[4]Other designations2MASX J13251937-3824524; 2MASS J13251937-3824526; GSC 07787-00931; IRAS F13224-3809; 1RXS J132519.4-382445; WISE J132519...

Kian Kok Middle School

Chinese independent high school in Kota Kinabalu, Malaysia, Sabah, MalaysiaKian Kok Middle School沙巴建国中学Jiàn Guó Zhōng XuéSekolah Menengah Kian KokAddressKian Kok Middle School, Jalan Tuaran, 88450 Kota KinabaluKota Kinabalu, Malaysia, Sabah, 88450MalaysiaInformationTypeChinese Independent High SchoolEstablished1963[1]ChairmanDatuk Clement Yeh[2]PrincipalGoh Teck SengFacultyScience ,Commerce, IGCSE and CulinaryNumber of students1,371 (2010)[3]Senior UEC...

Godland (film)

2022 film by Hlynur Pálmason GodlandInternational posterIcelandicVolaða landDanishVanskabte Land Directed byHlynur PálmasonWritten byHlynur PálmasonProduced by Eva Jakobsen Mikkel Jersin Katrin Pors Anton Máni Svansson Starring Elliott Crosset Hove [da] Ingvar Eggert Sigurðsson CinematographyMaria von Hausswolff [de]Edited byJulius Krebs DamsboMusic byAlex Zhang HungtaiProductioncompaniesSnowglobe FilmsGaragefilm InternationalDistributed by Sena (Iceland) Scanb...

哈萨克斯坦总统

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言，清晰概述条目所有重點。请在条目的讨论页讨论此问题。哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日（哈薩克蘇維埃社會主義共和國總統）哈萨克斯坦哈萨克斯坦政府...

Christian Menn

Swiss civil engineer and bridge designer ETH Library: Christian Menn (circa 1970) Christian Menn (March 3, 1927 – July 16, 2018) was a renowned Swiss civil engineer and bridge designer. He was involved in the construction of around 100 bridges worldwide, but the focus of his work was in eastern Switzerland, especially in canton Graubünden. He continued the tradition of and had a decisive influence on Swiss bridge building.[1] The technical and aesthetic possibilities of prestressed...

Moa-nalo

Extinct tribe of birds For the unrelated extinct birds from New Zealand, see Moa. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Moa-nalo – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message) Moa-naloTemporal range: Holocene Artist's conception of Chelyche...

Tsakhur people

Lezgin sub-ethnic group Ethnic group Tsakhurйыхъбы (Yiqby), цIаIхбыTsakhur child from Qum, AzerbaijanTotal populationc. 30,000Regions with significant populations Russia Dagestan 10,32012,796[1] Azerbaijan12,289[2] Ukraine83[3]LanguagesTsakhur, Lezgian, Azerbaijani, RussianReligionSunni Islam[4]Related ethnic groupsOther Northeast Caucasian-speaking peoplesEspecially Rutuls The Tsakhur or Saxur (Lezgian: ЦIахурар, Azerbaij...

UML

Запрос «Язык моделирования»[d] перенаправляется сюда. На эту тему нужно создать отдельную статью. UML Создатель Object Management Group Создан 1995 Официальный сайт uml.org (англ.) Медиафайлы на Викискладе UML (англ. Unified Modeling Language — унифицированный язык моделирования) — ...

Atomkern

Schematische Darstellung des Atoms (nicht maßstäblich, sonst wäre der untere Pfeil ca. 100 m lang). Der Atomkern ist der innerste, positiv geladene Teil eines Atoms. Die Unterteilung eines Atoms in Atomkern und Atomhülle geht auf Ernest Rutherford zurück, der 1911 in Streuexperimenten zeigte, dass Atome aus einem winzigen, kompakten Kern in einer leichten Hülle bestehen müssen. Dabei hat der Atomkern zwar einen 20.000 bis 150.000 Mal kleineren Durchmesser als die Atomhülle, beher...

Comunità europee

Questa voce o sezione sugli argomenti diritto internazionale e Unione europea non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Le comunità europee sono state tre organizzazioni internazionali distinte ma governate dalle medesime istituzioni: la Comunità europea del carbone e dell'acciaio (nata nel 1951),...

Trionfo

Disambiguazione – Se stai cercando altri significati, vedi Trionfo (disambigua). Rilievo della processione trionfale sull'Arco di Tito. Il trionfo era il massimo onore che nell'antica Roma veniva tributato con una cerimonia solenne al generale che avesse conseguito un'importante vittoria. Il primo a ottenerlo fu Romolo, il quale, dopo aver ucciso il re dei Ceninensi, poté celebrarlo percorrendo la via Sacra nel foro romano e salire sul Campidoglio, deponendo nel tempio di Giove Feretrio g...

Festival di Cannes 1997

Pur non essendo la maîtresse de cérémonie dell'edizione, Chiara Mastroianni ha aperto il Festival. La 50ª edizione del Festival di Cannes si è svolta a Cannes dal 7 al 18 maggio 1997.[1] Il film d'apertura dell'edizione è stato Il quinto elemento di Luc Besson, mentre Potere assoluto di Clint Eastwood è stato quello di chiusura.[1][2] Bruce Willis e Chiara Mastroianni hanno ufficialmente aperto l'edizione, mentre Jeanne Moreau ne ha presentato le cerimonie d'ina...