Gnome sort

Gnome sort
Visualisation of Gnome sort
ClassSorting algorithm
Data structureArray
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity auxiliary

Gnome sort (nicknamed stupid sort) is a variation of the insertion sort sorting algorithm that does not use nested loops. Gnome sort was originally proposed by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Engineering at Sharif University of Technology)[1] in 2000. The sort was first called stupid sort[2] (not to be confused with bogosort), and then later described by Dick Grune and named gnome sort.[3]

Gnome sort performs at least as many comparisons as insertion sort and has the same asymptotic run time characteristics. Gnome sort works by building a sorted list one element at a time, getting each item to the proper place in a series of swaps. The average running time is O(n2) but tends towards O(n) if the list is initially almost sorted.[4][note 1]

Dick Grune described the sorting method with the following story:[3]

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter).
Here is how a garden gnome sorts a line of flower pots.
Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise, he swaps them and steps one pot backward.
Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

— "Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com

Pseudocode

Here is pseudocode for the gnome sort using a zero-based array: 

 procedure gnomeSort(a[]):
   pos := 0
   while pos < length(a):
       if (pos == 0 or a[pos] >= a[pos-1]):
           pos := pos + 1
       else:
           swap a[pos] and a[pos-1]
           pos := pos - 1

Example

Given an unsorted array, a = [5, 3, 2, 4], the gnome sort takes the following steps during the while loop. The current position is highlighted in bold and indicated as a value of the variable pos.

Current array pos Condition in effect Action to take
[5, 3, 2, 4] 0 pos == 0 increment pos
[5, 3, 2, 4] 1 a[pos] < a[pos-1] swap, decrement pos
[3, 5, 2, 4] 0 pos == 0 increment pos
[3, 5, 2, 4] 1 a[pos] ≥ a[pos-1] increment pos
[3, 5, 2, 4] 2 a[pos] < a[pos-1] swap, decrement pos
[3, 2, 5, 4] 1 a[pos] < a[pos-1] swap, decrement pos
[2, 3, 5, 4] 0 pos == 0 increment pos
[2, 3, 5, 4] 1 a[pos] ≥ a[pos-1] increment pos
[2, 3, 5, 4] 2 a[pos] ≥ a[pos-1] increment pos:
[2, 3, 5, 4] 3 a[pos] < a[pos-1] swap, decrement pos
[2, 3, 4, 5] 2 a[pos] ≥ a[pos-1] increment pos
[2, 3, 4, 5] 3 a[pos] ≥ a[pos-1] increment pos
[2, 3, 4, 5] 4 pos == length(a) finished

Notes

  1. ^ Almost sorted means that each item in the list is not far from its proper position (not farther than some small constant distance).

References

  1. ^ Hamid, Sarbazi-Azad. "Hamid Sarbazi-Azad profile page". Archived from the original on 2018-10-16. Retrieved October 16, 2018.
  2. ^ Sarbazi-Azad, Hamid (2 October 2000). "Stupid Sort: A new sorting algorithm" (PDF). Newsletter (599). Computing Science Department, Univ. of Glasgow: 4. Archived (PDF) from the original on 7 March 2012. Retrieved 25 November 2014.
  3. ^ a b "Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com. 2000-10-02. Archived from the original on 2017-08-31. Retrieved 2017-07-20.
  4. ^ Paul E. Black. "gnome sort". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Archived from the original on 2011-08-11. Retrieved 2011-08-20.
The Wikibook Algorithm implementation has a page on the topic of: Gnome sort

Read other articles:

Atlantic Steam Navigation Company

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (February 2016) (Learn how and when to remove this template message) Atlantic Steam Navigation Co LtdHouse flagIndustryTransportationFounded1934FounderFrank BustardDefunct1971SuccessorEuropean FerriesNumber of locationsTilbury, Preston & LowestoftArea servedNorth Sea &am...

 

Auguste Ambroise Tardieu

Auguste Ambroise TardieuLahir(1818-04-10)10 April 1818Paris, FranceMeninggal12 Januari 1879(1879-01-12) (umur 60)Tempat tinggalParis, PrancisKebangsaanPrancisWarga negaraFrenchDikenal atasTardieu's syndrome, Tardieu's ecchymoses, First forensic studies of child maltreatmentPenghargaanPrize of the French Academy of Science (1875)Karier ilmiahBidangForensic science, Public healthInstitusiFaculté de Médicine de ParisMenginspirasiPaul Brouardel Auguste Ambroise Tardieu (10 April 1818 ...

 

Brevetto software

Un brevetto software, secondo la definizione adottata dalla FFII (Foundation for a Free Information Infrastructure), ci si riferisce a un brevetto applicato «a ogni prestazione di un computer realizzata per mezzo di un programma per elaboratore».[1] Globalmente la situazione è piuttosto complessa. Non esiste, infatti, una definizione legale comune tra i vari Paesi. Per esempio in Europa viene negata la registrazione di «programmi per elaboratore in quanto tali»[2]: per ot...

Колеблющийся штат

Карта колеблющихся штатов на президентских выборах 2024 года, основанная на их результатах 2020 года. Синий представляет кандидата от Демократической партии Джо Байдена, а красный представляет кандидата от Республиканской партии Дональда Трампа. «Колеблющиеся состояния»...

 

List of South African provincial capitals

Map all coordinates using OpenStreetMap Download coordinates as: KML GPX (all coordinates) GPX (primary coordinates) GPX (secondary coordinates) The following is a list of the capitals of the provinces of South Africa. Province Capital Coordinates Eastern Cape Bhisho 32°51′12″S 27°26′10″E / 32.85333°S 27.43611°E / -32.85333; 27.43611 (Bhisho) Free State Bloemfontein 29°06′58″S 26°12′51″E / 29.11611°S 26.21417°E /...

 

WGMZ

Radio station in Glencoe, AlabamaWGMZGlencoe, AlabamaBroadcast areaGadsden, AlabamaFrequency93.1 MHz (HD Radio)BrandingClassic Hits Z93.1ProgrammingFormatClassic hitsOwnershipOwneriHeartMedia(iHM Licenses, LLC)Sister stationsWAAXHistoryFirst air date1994 (1994)Former call signsWZJV (1992–1993)[1]Technical informationFacility ID2465ClassAERP1,650 wattsHAAT189 meters (620 ft)Transmitter coordinates33°57′16″N 85°51′40″W / 33.95444°N 85.86111°W...

Hakeem Olajuwon

Hakeem Abdul Olajuwon -- lahir dengan nama Akeem Abdul Olajuwon -- (lahir 21 Januari 1963) adalah seorang mantan pemain bola basket dari tim Houston Rockets pada kompetisi NBA.Dengan tinggi 2.13 m, Hakeem termasuk dalam lima pemain tengah legendaris NBA, bersama dengan Bill Russell, Wilt Chamberlain, Kareem Abdul-Jabbar, dan Shaquille O'Neal. Hakeem Olajuwon berasal dari Nigeria, Ia ke Amerika hanya dibekali sebuah mimpi dan sebuah kesanggupan yang luar biasa untuk mempelajari Game of Basketb...

 

Natalya Sindeyeva

Dalam nama yang mengikuti kebiasaan penamaan Slavia Timur ini, patronimiknya adalah Vladimirovna. Natalya SindeyevaSindeyeva at the MediaMakers conferenceНаталья Синдеева Lahir11 Juni 1971  (age 52)Michurinsk (Uni Soviet) AlmamaterStockholm School of EconomicsMichurinsk State Pedagogical Institute PekerjaanPublisher, wartawan, media manager Suami/istriAlexander Vinokurov PenghargaanM100 Media Award (Tanit Koch, 2017) Signature Natalya Vladimir...

 

Голубянки

Голубянки Самец голубянки икар Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ПервичноротыеБез ранга:ЛиняющиеБез ранга:PanarthropodaТип:ЧленистоногиеПодтип:ТрахейнодышащиеНадкласс:ШестиногиеКласс...

Mythlore

Academic journalMythloreDisciplineTolkien studies, fantasy, fanzineLanguageEnglishPublication detailsHistory1969-presentPublisherMythopoeic Society (United States)FrequencyBiannuallyStandard abbreviationsISO 4 (alt) · Bluebook (alt1 · alt2)NLM (alt) · MathSciNet (alt )ISO 4MythloreIndexingCODEN (alt · alt2) · JSTOR (alt) · LCCN (alt)MIAR · NLM (alt) · ScopusISSN0146-9339OCLC&#...

 

豪栄道豪太郎

豪栄道 豪太郎 場所入りする豪栄道基礎情報四股名 澤井 豪太郎→豪栄道 豪太郎本名 澤井 豪太郎愛称 ゴウタロウ、豪ちゃん、GAD[1][2]生年月日 (1986-04-06) 1986年4月6日（38歳）出身 大阪府寝屋川市身長 183cm体重 160kgBMI 47.26所属部屋 境川部屋得意技 右四つ・出し投げ・切り返し・外掛け・首投げ・右下手投げ成績現在の番付 引退最高位 東大関生涯戦歴 696勝493敗...

 

西遊記大結局之仙履奇緣

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目需要編修，以確保文法、用詞、语气、格式、標點等使用恰当。 (2013年8月6日)請按照校對指引，幫助编辑這個條目。（幫助、討論） 此條目剧情、虛構用語或人物介紹过长过细，需清理无关故事主轴的细节、用語和角色介紹。 (2020年10月6日)劇情、用語和人物介紹都只是用於了解故事主軸，輔助�...

Bok de Korver

Dutch footballer In this Dutch name, the surname is de Korver, not Korver. 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: Bok de Korver – news · newspapers · books · scholar · JSTOR (April 2024) (Learn how and when to remove this message) Bok de Korver Senior career*Years Team Apps (Gls)1902–1923 Sparta R...

 

Рада (телеканал)

РАДАДП «ПАРЛАМЕНТСЬКИЙ ТЕЛЕКАНАЛ „РАДА“»[1] Країна  УкраїнаЗона мовлення  Україна Європа Близький СхідЧас мовлення Цілодобово (з 2018 року)з 8:00 до 22:00 (1999—2018)Мова мовлення українськаЦентр керування Київ, вул. Садова, 3-AФорматзображення 576i 16:9 (SDTV)1080i (HDTV)Тематика ка...

 

Sociology of religion

Branch of sociology For the book by Max Weber, see Sociology of Religion (book). For the academic journal, see Sociology of Religion (journal). Muslims praying in the streets of Istanbul Part of a series onSociology History Outline Index Key themes Society Globalization Human behavior Human environmental impact Identity Industrial revolutions 3 / 4 / 5 Social complexity Social construct Social environment Social equality Social equity Social power Social stratification Social structure Perspe...

Mike Thompson (California politician)

American politician (born 1951) For other people named Mike Thompson, see Michael Thompson. Mike ThompsonMember of the U.S. House of Representativesfrom CaliforniaIncumbentAssumed office January 3, 1999Preceded byFrank RiggsConstituency1st district (1999–2013)5th district (2013–2023)4th district (2023–present)Member of the California State Senatefrom the 2nd districtIn officeMay 20, 1993 – November 30, 1998Preceded byBarry KeeneSucceeded byWesley ChesbroMember...

 

Línea 1A (Urbanos de Alcalá de Henares)

Circular Alcalá de Henares A Área abastecidaMunicipios Alcalá de HenaresDescripciónTipo AutobúsSistema Urbanos de Alcalá de HenaresZonas tarifarias OperaciónParadas 53Primera expedición 6:00 (L-V I) 6ː15 (L-V V) 6:40 (S) 7:30 (DF)Última expedición 23ː45 (L-J) 3:30 (VSvF) 23:20 (DF)ExplotaciónOperador AlcalaBus (Monbus)Autoridad CRTMNotasPágina web [1] (Ida)[2] (Vuelta)Líneas relacionadas Línea 1B (Urbanos de Alcalá de Henares) Línea 2 (Urbanos de Alcalá de Henares) Línea 3...

 

聖克里斯多福及尼維斯

此條目可参照英語維基百科相應條目来扩充。 (2020年2月23日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 圣基茨和尼维斯联邦Federation of Saint Christopher and Nevis（英語） 国旗 国徽 格言：Country Above Self  (英语)...

Magyar Kosárlabda Nemzeti Bajnokság

Magyar Kosárlabda Nemzeti BajnokságSport Pallacanestro TipoSquadre di club FederazioneMagyar Kosarlabdázók Országos Szövetsége Paese Ungheria OrganizzatoreFederazione cestistica dell'Ungheria TitoloCampione d'Ungheria CadenzaAnnuale Partecipanti14 squadre FormulaStagione regolare A/RPlayoff, finali titolo Sito InternetMagyar Kosárlabda Nemzeti Bajnokság StoriaFondazione1933 Detentore Falco Szombathely Record vittorie Honvéd (33) Modifica dati su Wikidata · Manua...

 

Social stigma of obesity

Type of discrimination based on weight The examples and perspective in this article deal primarily with the United States and do not represent a worldwide view of the subject. You may improve this article, discuss the issue on the talk page, or create a new article, as appropriate. (November 2018) (Learn how and when to remove this message) Part of a series onDiscrimination Forms Institutional Structural Statistical Taste-based Attributes Age Caste Class Dialect Disability Genetic Hair textur...