奇偶転置ソート

奇偶転置ソート
Example of odd-even transposition sort sorting a list of random numbers.
奇偶転置ソートによるランダムな数字のリストのソートの例
クラス ソート
データ構造 配列
最悪計算時間
最良計算時間
最悪空間計算量

奇偶転置ソート（きぐうてんちソート、英: odd-even sort）は、ソートのアルゴリズムの一つで、バブルソートを改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートでは組ごとに行う。

バブルソートと同じく安定な内部ソートで、最悪の場合で時間計算量はO(n2)である。

組の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。 そのため、ハードウェアで隣り合う組の比較を同時に処理すれば、常に (n-1) ステップで処理が完了する。 ただし、ソートの対象が多いと必要とするリソースが大きくなり、実用的ではない。

アルゴリズム

奇偶置換ソートは、奇数番目とその次の偶数番目を組 (組1) にして比較／交換した後、偶数番目とその次の奇数番目を組 (組2) にして比較／交換することを繰り返すアルゴリズムである。

組1
（1番目と2番目を比較、3番目と4番目を比較、5番目と6番目を比較、…）の後に
組2
（2番目と3番目を比較、4番目と5番目を比較、6番目と7番目を比較、…）を行う。

これを繰り返す。

実装例

1番目の位置を表す添字が 0 になっているのはC言語の仕様である。 

double data[N] = {値1, 値2, 値3, ..., 値N} ;
bool changed ;
do
  {
  changed = false ;
  for (int i=0 ; i<N-1 ; i+=2)　/* 組1 */
    if (data[i] > data[i+1])
      {
      swap (&data[i], &data[i+1]) ;
      changed = true ;
      }
  for (int i=1 ; i<N-1 ; i+=2) /* 組2 */
    if (data[i] > data[i+1])
      {
      swap (&data[i], &data[i+1]) ;
      changed = true ;
      }
  }
  while (changed) ;

動作例

のような表記は比較されるデータの組を示す。

初期データ:

時間 置換前の状態 組 置換個数 置換後の状態
1 組1 3
2 組2 3
3 組1 4
4 組2 2
5 組1 3
6 組2 3
7 組1 3
8 組2 1

交換回数:（バブルソートと同じ）

外部リンク

理論
交換ソート
選択ソート
挿入ソート
マージソート
非比較ソート
並行ソート
混成ソート
その他
非効率的/
ユーモラスソート
カテゴリ カテゴリ
スタブアイコン

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

Read other articles:

SMA Negeri 1 Bitung

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Maret 2016. SMA Negeri 1 BITUNGInformasiDidirikan1 Agustus 1965Jurusan atau peminatanBHS, IPS, MIPARentang kelasX, XI, XIIKurikulumKurikulum 2013AlamatLokasiJl. Wolter Monginsidi, Girian Weru Satu, Kec Girian,, Bitung, Sulawesi UtaraMoto SMA Negeri 1 Bitung (SMANSA)...

 

Rigobert Bonne

Carte hydro-geo-graphique des Indes Orientales en deca et au dela du Gange avec leur archipel, Paris 1771 Rigobert Bonne (1727-1794) adalah seorang ahli geografi, rekayasawan hidrografi dan kartografi Prancis, master matematika abad ke-XVIII. Biografi Lahir di Ardennes, Raucourt pada 6 Oktober 1727. Dia belajar matematika tanpa guru dan menjadi rekayasawan pada usia delapan belas tahun. Dia bertugas dalam kapasitas itu dalam Perang Flandria, di mana dia berada di pengepungan Bergen op Zoom pa...

 

Friedrich IV dari Austria

Friedrich IV, Adipati Austria Selanjutnya (1382 – 24 Juni 1439), juga dikenal sebagai Friedrich yang Berkantong Kosong, merupakan seorang adipati Habsburg Austria Selanjutnya dari tahun 1402, dan Provinsi Tirol dari tahun 1406, sampai kematiannya. Ia adalah putra Leopold III, Adipati Austria Dalam. Pemerintahan Friedrich atas Tirol dan wilayah Habsburg yang tersebar di Jerman barat daya dan di Alsace ditujukan kolektif sebagai Vorderösterreich (antara lain, Austria Selanjutnya) disahkan p...

Coppa del Belgio 2016-2017

Disambiguazione – Se stai cercando l'omonima edizione per altri sport, vedi Coppa del Belgio 2016-2017 (disambigua). Questa voce sugli argomenti edizioni di competizioni calcistiche e sport in Belgio è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Coppa del Belgio 2016-2017Croky Cup 2016-2017 Competizione Coppa del Belgio Sport Calcio Edizione 62ª Organizzatore URBSFA/KBVB Date dal 31 luglio 201...

 

Bataille de Hollabrunn (1809)

Bataille de Hollabrunn (1809) Combat d'Hollabrünn le 9 juillet 1809 par Siméon Fort, 1837 Informations générales Date 9 juillet 1809 Lieu Hollabrunn Issue Victoire autrichienne Belligérants Empire français  Empire d'Autriche Commandants André Masséna Johann von Klenau Forces en présence 11 000 hommes (IVe Corps français de la Grande Armée d'Allemagne) 17 000 hommes Pertes Inconnues Inconnues Cinquième CoalitionBatailles Campagne d'Allemagne et d'Autriche Sacil...

 

Royal Caledonian School

New Caledonian Asylum, 1828. The Royal Caledonian School was a residential home and school for Scottish orphans, initially in London and subsequently in Bushey, Hertfordshire. History The Caledonian Asylum was launched by members of the Highland Society of London in 1815 to provide a home and education for Scottish children in London who had been orphaned in the Napoleonic Wars. John Galt, the novelist, became secretary to the Asylum in 1815. The first Asylum was at 16 Cross Street,[1 ...

List of Newcastle Jets FC records and statistics

This article is about all-time records. For a season-by-season statistical breakdown, see List of Newcastle Jets FC seasons. Newcastle's starting lineup for the 2008 A-League Grand Final Newcastle Jets Football Club is an Australian professional association football club based in Speers Point, Newcastle. The club was formed in 2000 as Newcastle United before being renamed as Newcastle Jets in 2005. After spending their first four seasons participating in the National Soccer League, Newcastle...

 

ヨハネス12世 (ローマ教皇)

ヨハネス12世 第130代 ローマ教皇 教皇就任 955年12月16日教皇離任 964年5月14日先代 アガペトゥス2世次代 レオ8世個人情報出生 937年スポレート公国（中部イタリア）スポレート死去 964年5月14日 教皇領、ローマ原国籍 スポレート公国親 父アルベリーコ2世（スポレート公）、母アルダその他のヨハネステンプレートを表示 ヨハネス12世（Ioannes XII、937年 - 964年5月14日）は、ロ...

 

Antigua dan Barbuda

Antigua dan BarbudaAntigua and Barbuda (Inggris) Bendera Lambang Semboyan: Each Endeavouring, All Achieving(Inggris: Masing-masing Berusaha, Semuanya Berprestasi)Lagu kebangsaan: Fair Antigua, We Salute Thee(Inggris: Antigua yang Adil, Kami Menghormatimu) Lagu kerajaan: God Save the King(Inggris: Tuhan Menjaga sang Raja)aIbu kota(dan kota terbesar)Saint John's17°7′N 61°51′W / 17.117°N 61.850°W / 17.117; -61.850Bahasa resmiInggrisPemerintahanMonar...

Alla Tarasova

Soviet and Russian actress (1898–1973) Alla TarasovaBornAlla Konstantinovna Tarasova6 February [O.S. 25 January] 1898Kyiv, Russian EmpireDied5 April 1973(1973-04-05) (aged 75)Moscow, RSFSR, Soviet UnionOccupation(s)Actress, pedagogueYears active1916–1973 Alla Konstantinovna Tarasova (Russian: А́лла Константи́новна Тара́сова; 6 February [O.S. 25 January] 1898 – 5 April 1973) was a Soviet and Russian stage and film...

 

Strato of Lampsacus

Ancient Greek philosopher Strato of LampsacusStrato, depicted as a medieval scholar in the Nuremberg ChronicleBornc. 335 BCELampsacus(now Lapseki, Çanakkale, Turkey)Diedc. 269 BCE (aged c. 66)AthensEraAncient philosophyRegionWestern philosophySchoolPeripateticismMain interestsNatural philosophy, Physics Strato of Lampsacus (/ˈstreɪtoʊ/; Greek: Στράτων ὁ Λαμψακηνός, translit. Strátōn ho Lampsakēnós, c. 335 – c. 269 BCE) was a Peri...

 

Andrea Vendrame

Questa voce sull'argomento ciclisti italiani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Andrea VendrameNazionalità Italia Altezza168 cm Peso60 kg Ciclismo SpecialitàStrada Squadra Decathlon AG2R CarrieraGiovanili 2009-2010V.C. San Vendemiano2011-2012V.C. Bianchin-Marchiol Squadre di club 2013-2014 Marchiol2015-2016 Zalf Fior2017-2019 Androni2020 AG2R La Mondiale2021...

Sivaganga Assembly constituency

One of the 234 State Legislative Assembly Constituencies in Tamil Nadu, in India SivagangaConstituency No. 186 for the Tamil Nadu Legislative AssemblyConstituency detailsCountryIndiaRegionSouth IndiaStateTamil NaduDistrictSivagangaLS constituencySivagangaEstablished1952Total electors3,01,163[1]ReservationNoneMember of Legislative Assembly16th Tamil Nadu Legislative AssemblyIncumbent P. R. Senthilnathan Party  AIADMKElected year2021 Sivagangai is a state assembly constituency...

 

Jules Brame

Pour les articles homonymes, voir Brame. Cet article est une ébauche concernant un homme politique français et le Nord. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Jules Brame Fonctions Ministre de l'Instruction publique, Cultes et Beaux-Arts 10 août 1870 – 4 septembre 1870(25 jours) Gouvernement Cousin-Montauban Prédécesseur Jacques Mège Successeur Jules Simon Sénateur français 30 janvier 187...

 

Aline Terry

Questa voce o sezione sull'argomento tennisti statunitensi 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. Questa voce sull'argomento tennisti statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Aline TerryNazionalità Stati Uniti Tennis Carriera Singolare1 Vittorie/sconfitte 1 Titoli vinti Miglior r...

Virginia Slims of Houston

Virginia Slims of HoustonSport Tennis CategoriaTier III (1988-1990)Tier II (1991-1995) FederazioneWomen's Tennis Association Paese Stati Uniti LuogoHouston SuperficieSintetico indoor (1970-1984) Terra rossa (1985-1995) OrganizzatoreUSTA CadenzaAnnuale StoriaFondazione1970 Soppressione1995 Numero edizioni25 Record vittorie Martina Navrátilová (6, singolare; 7, doppio) Modifica dati su Wikidata · Manuale Il Virginia Slims of Houston è stato un torneo femminile di tennis giocato da...

 

William Carries On

Book by Richmal Crompton This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: William Carries On – news · newspapers · books · scholar · JSTOR (May 2015) (Learn how and when to remove this message) William Carries On First edition (second impression)AuthorRichmal CromptonIllustratorThomas HenryLanguageEnglishGenreChildren's litera...

 

Office

Room where administrative work is performed For other uses, see Office (disambiguation). 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: Office – news · newspapers · books · scholar · JSTOR (May 2024) (Learn how and when to remove this message) Midtown Manhattan in New York City is the largest central busine...

The Great Escape Festival

Annual music festival in Brighton and Hove, England This article is about the UK music festival. For the Australian music festival, see The Great Escape (festival). The Great EscapeGenreRock, alternative rock, indie rock, punk rock, hard rock, dance, techno, electronic, acoustic, hip hopLocation(s)Brighton and Hove, EnglandYears active18 yearsMost recent2023Next event15–18 May 2024Websitegreatescapefestival.com The Great Escape Festival is a four-day music festival held in Brighton and Hove...

 

Mike Mogis

American multi-instrumentalist This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Mike Mogis – news · newspapers · books · scholar · JSTOR (March 2020) (Learn how and when to remove this message) M...