Медленная сортировка

Медленная сортировка (англ. Slowsort) — непрактичный и юмористический алгоритм сортировки. Он основан на принципе размножай и сдавайся (англ. multiply and surrender), пародии на разделяй и властвуй. Его опубликовали Андрей Бродер и Йорге Столфи в 1986 году в своей статье Pessimal Algorithms and Simplexity Analysis[1] (Пессимальные алгоритмы и анализ простоты, пародия на оптимальные алгоритмы и анализ сложности).

Алгоритм

Медленная сортировка — рекурсивный алгоритм.

Он может быть описан следующим образом:

1.1. Рекурсивно отсортировать первую половину.
1.2. Рекурсивно отсортировать вторую половину.
1.3. Найти максимум всего массива, сравнивая результаты 1.1 и 1.2, и поместить его в конец массива.
2. Рекурсивно отсортировать весь массив, кроме максимума.

На псевдокоде он реализуется следующим образом: 

подпрограмма slowsort(A, i, j)                      // сортирует массив A[i], ..., A[j]
    если (i >= j) то вернуться
    m := floor((i+j)/2)
    slowsort(A, i, m)                               // (1.1)
    slowsort(A, m+1, j)                             // (1.2)
    если (A[j] < A[m]) то поменять A[j] и A[m]      // (1.3)
    slowsort(A, i, j-1)                             // (2)

Возможная реализация на Haskell: 

slowsort :: Ord a => [a] -> [a]
slowsort xs
    | length xs <= 1 = xs
    | otherwise      = slowsort xsnew ++ [max llast rlast]  -- (2)
    where
        l     = slowsort $ take m xs  -- (1.1)
        r     = slowsort $ drop m xs  -- (1.2)
        llast = last l
        rlast = last r
        xsnew = init l ++ min llast rlast : init r
        m     = fst (divMod (length xs) 2)

Сложность

Время выполнения медленной сортировки равно . Медленная сортировка не в полиномиальном времени. Даже в лучшем случае она хуже сортировки пузырьком.

Источники

  1. ↑ CiteSeerX — Pessimal Algorithms and Simplexity Analysis. Citeseerx.ist.psu.edu. Дата обращения: 26 июля 2017. Архивировано 30 января 2017 года.

Read other articles:

Roman Shishkin

Roman Shishkin Bersama Lokomotiv pada 2012Informasi pribadiNama lengkap Roman Aleksandrovich ShishkinTanggal lahir 27 Januari 1987 (umur 37)Tempat lahir Voronezh, Uni SovietTinggi 1,78 m (5 ft 10 in)Posisi bermain BekInformasi klubKlub saat ini Lokomotiv MoscowNomor 49Karier junior Fakel Voronezh Spartak MoscowKarier senior*Tahun Tim Tampil (Gol)2004–2010 Spartak Moscow 54 (1)2009 → Krylia Sovetov Samara (pinjaman) 25 (0)2010– Lokomotiv Moscow 56 (3)Tim nasional‡2...

 

Ceará

Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus. Ceará adalah satu dari dua puluh tujuh negara bagian (estado) di Brasil. Ibu kotanya adalah Fortaleza. Ceara berbatasan dengan Piaui, Pernambuco, Paraiba, Rio Grande do Norte, dan Samudra Atlantik. Pranala luar (Portugis) Situs resmi lbsNegara bagian di Brasil Distrik Federal: Distrik Federal Brasil Acre · ...

 

Ali Ar-Ramitani

Ali ar-Ramitani Ali ar-Ramitani atau Azizan Ali ar-Ramitani Quddasallahu Sirruhu adalah seorang guru sufi yang terkenal sebagai salah satu Mursyid Thoriqoh Naqsyabandiyah. Beliau salah satu Khwajagan (Master) dari tatanan Naqsyabandi dan juga terkenal sebagai salah satu Wali 7 di Uzbekistan. Syekh Ali ar-Ramitani q.s yang lahir di daerah Ramitan di sekitar Bukhara. Azizan adalah gelar yang disematkan kepadanya. Karena keahliaannya dalam menenun, Syekh Ali Ramitani q.s sering dipanggil Syekh N...

2019 European Parliament election

Election to the European Parliament 2019 European Parliament election ← 2014 23–26 May 2019[1] 2024 → ← outgoing memberselected members →All 751 seats to the European Parliament376 seats needed for a majorityTurnout198,352,638 (50.66%[2] 8.01 pp)   Leader Manfred Weber Frans Timmermans Margrethe Vestager Alliance EPP S&D Renew Leader's seat Germany Netherlands Denmark[a] Last election 221 seats, 23.8% 191...

 

Torigni-sur-Vire

Pour les articles homonymes, voir Thorigny. Torigny-sur-Vire redirige ici. Torigni-sur-Vire Le château des Matignon Administration Pays France Région Normandie Département Manche Arrondissement Saint-Lô Commune Torigny-les-Villes Intercommunalité Saint-Lô Agglo Statut commune déléguée Maire délégué Mandat Claude Gallier 2020-2026 Code postal 50160 Code commune 50601 Démographie Gentilé Torignais Population 2 339 hab. (2021) Densité 777 hab./km2 Géographie Coord...

 

Provinsi Tokat

Tokat province Tokat iliProvince of TurkeyLocation of Tokat Province in TurkeyCountryTurkeyRegionBlack SeaLuas • Total9.959 km2 (3,845 sq mi)Populasi (2010-12-31)[1] • Total617.802 • Kepadatan62/km2 (160/sq mi)Kode area telepon0356Pelat kendaraan60Situs webtokat.gov.tr Tokat (Turki: Tokat ili) adalah sebuah provinsi Turki. Galeri Tokat Gök Medrese in Tokat Polychrome tiles from Gök Medrese Maşat Höyük, a Hittite arc...

Devlet Bahçeli

Devlet BahçeliMP Wakil Perdana Menteri TurkiMasa jabatan28 Mei 1999 – 18 November 2002Perdana MenteriBülent EcevitServed withHüsamettin ÖzkanŞükrü Sina GürelCumhur ErsümerMesut YılmazPendahuluHikmet UluğbayPenggantiAbdüllatif ŞenerPemimpin Partai Gerakan NasionalisPetahanaMulai menjabat 6 Juli 1997PendahuluAlparslan TürkeşPenggantiPetahanaAnggota Majelis Nasional BesarPetahanaMulai menjabat 22 Juli 2007Daerah pemilihanOsmaniye (2007, 2011, June 2015, Nov 2015...

 

انكسار (فيزياء)

  لمعانٍ أخرى، طالع انكسار (توضيح). انكسار موجات الضوء في الماء. المستطيل الغامق يمثل الوضع الحقيقي لقلم رصاص بوعاء مائي. المستطيل الفاتح يمثل الصورة المرئية نتيجة للأنكسار. ضع في الاعتبار أن علامة(X) تظهر كما هي علامة (Y),وهو وضع سطحي نسبيا بالنسبة ل(X). تظهر الشفاطة وكأنه�...

 

Zack Snyder

American filmmaker (born 1966) Zack SnyderSnyder at the 2016 San Diego Comic-ConBornZachary Edward Snyder (1966-03-01) March 1, 1966 (age 58)Green Bay, Wisconsin, U.S.EducationArt Center College of Design (BFA)OccupationsFilm directorfilm producerscreenwritercinematographerYears active1990–presentSpousesDenise Weber (divorced) Deborah Johnson ​(m. 2004)​Children8[1] Zachary Edward Snyder (born March 1, 1966) is an American film director, produc...

Al Fattan Marine Towers

Residential (Tower 1), Hotel (Tower 2) in Dubai, U.A.E.Al Fattan Marine TowersFattan Marine Towers in Jumeirah Beach Residences (blue glass buildings)General informationTypeResidential (Tower 1)Hotel (Tower 2)LocationDubai, U.A.E.Coordinates25°04′45.99″N 55°08′11.02″E / 25.0794417°N 55.1363944°E / 25.0794417; 55.1363944Construction started2004Completed2006HeightAntenna spire245 m (804 ft)Roof230 m (755 ft)Technical detailsFloor count51Fl...

 

Tour des Flandres 2017

Tour des Flandres 2017 GénéralitésCourse101e Tour des FlandresCompétitionUCI World Tour 2017 1.UWTDate2 avril 2017Distance260 kmPays BelgiqueLieu de départAnversLieu d'arrivéeAudenardeÉquipes25Partants198Arrivants121Vitesse moyenne40,651 km/hSite officielSite officielRésultatsVainqueur Philippe Gilbert (Quick-Step Floors)Deuxième Greg Van Avermaet (BMC Racing Team)Troisième Niki Terpstra (Quick-Step Floors) ◀20162018▶Documentation La 101e édition du Tour des Flandres ...

 

2017 British Grand Prix

2017 British Grand Prix Race 10 of 20 in the 2017 Formula One World Championship← Previous raceNext race → Layout of the Silverstone CircuitRace detailsDate 16 July 2017Official name 2017 Formula 1 Rolex British Grand Prix[1][2][3]Location Silverstone CircuitSilverstone, United KingdomCourse Permanent racing facilityCourse length 5.891 km (3.660 miles)Distance 51 laps, 300.307 km (186.602 miles)Scheduled distance 52 laps, 306.198 km (190.262 mi...

Associazione Calcio Imola 1971-1972

Questa voce sull'argomento stagioni delle società calcistiche italiane è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Voce principale: Imolese Calcio 1919. Associazione Calcio ImolaStagione 1971-1972Sport calcio Squadra Imola Allenatore Leo Zavatti poi Walter Gardelli Presidente Franco Resta Serie C19º posto nel girone B. Retrocesso in Serie D. Maggiori presenzeCampionato: Amadori, Mazzoli (37)...

 

Tour de Bretagne (cyclisme)

Pour les articles homonymes, voir Tour de Bretagne. Cet article est une ébauche concernant le cyclisme. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Tour de Bretagne Logo de la courseGénéralités Sport cyclisme sur route Création 1967 Éditions 57 (en 2024) Catégorie UCI Europe Tour 2.2 Type / Format course à étapes Périodicité annuelle (25 avril - 1er mai) Lieu(x) France Bretagne Participants 150 Di...

 

Red Sparks

Daejoen CheongKwanJang Red SparksNama lengkapDaejeon CheongKwanJang Red Sparks Pro Volleyball Club정관장 레드스파크스 프로 배구단Nama pendekRed SparksDidirikan1988; 36 tahun lalu (1988)ArenaChungmu Gymnasium Daejeon, Korea Selatan(Kapasitas: 6,000)PemilikKorea Ginseng CorporationManajer Bang Hyung-bongPelatih Ko Hee-jinKapten yeom hye seonLigaV-League2023−24Musim reguler: ke-3Pasca musim: PlayoffSitus webSitus resmi klubSeragam Kandang Tandang Daejeon CheongKwanJang Red S...

Madlib

American record producer (born 1973) For the word game, see Mad Libs. MadlibMadlib performing in 2014Background informationBirth nameOtis Jackson, Jr.Also known asQuasimotoYesterdays New QuintetDJ RelsBeat KonductaThe Loop DiggaBorn (1973-10-24) October 24, 1973 (age 50)Oxnard, California, U.S.GenresWest Coast hip hopinstrumental hip hopsouljazz fusionfunkelectronicjazzpsychedeliaOccupation(s)Record producerrappersongwriterdisc jockeyInstrument(s)Turntablessamplervocalsdrumskeyboardssynt...

 

アレルギー

この項目では、ヒトまたは動物における抗原に対する過剰な免疫反応について説明しています。日本のロック・バンドについては「ALLERGY」を、嵐の曲「アレルギー」については「ARASHI No.1〜嵐は嵐を呼ぶ〜#収録曲」を、植物における感染拡大防止機構については「過敏感反応」をご覧ください。 この記事は検証可能な参考文献や出典が全く示されていないか、不十分�...

 

Jewish Publication Society

The oldest nonprofit, nondenominational publisher of Jewish works in English Jewish Publication SocietyFounded1888Country of originUnited StatesHeadquarters locationPhiladelphiaPublication typesBooksNonfiction topicsJudaicaOfficial websitejps.org The Jewish Publication Society (JPS), originally known as the Jewish Publication Society of America, is the oldest nonprofit, nondenominational publisher of Jewish works in English. Founded in Philadelphia in 1888, by Reform Rabbi Joseph Krauskopf am...

Lord Elibank

Lordship of Elibank Blazon Quarterly: 1st and 4th, Or a Fetterlock Azure on a chief of the second three Mullets Argent (Murray of Blackbarony); 2nd and 3rd, Azure three Mullets within a Double Tressure flory counterflory Argent in the centre a Martlet Or (Murray of Elibank) Creation date18 March 1643PeeragePeerage of ScotlandFirst holderPatrick Murray, 1st Lord ElibankPresent holderRobert Francis Alan Erskine-Murray, 15th Lord ElibankHeir apparentthe Hon. Timothy Alexander Elibank Erskine-Mu...

 

Factorial

Product of numbers from 1 to n For other uses, see Factorial (disambiguation). Selected factorials; values in scientific notation are rounded n {\displaystyle n} n ! {\displaystyle n!} 0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 11 39916800 12 479001600 13 6227020800 14 87178291200 15 1307674368000 16 20922789888000 17 355687428096000 18 6402373705728000 19 121645100408832000 20 2432902008176640000 25 1.551121004×1025 50 3.041409320×1064 70 1.197857167×10100 100 9.3...