تصنيف دمجي

تصنيف دمجي
معلومات عامة
صنف فرعي من
المكتشف أو المخترع
زمن الاكتشاف أو الاختراع
1945 عدل القيمة على Wikidata
أسوأ حالة تعقيد زمني
عدل القيمة على Wikidata
أفضل حالة تعقيد زمني
عدل القيمة على Wikidata
متوسط التعقيد الزمني
عدل القيمة على Wikidata
أسوأ حالة تعقيد مكاني
عدل القيمة على Wikidata
أفضل حالة تعقيد مكاني
[1] عدل القيمة على Wikidata
مثال للتصنيف الدمجي.

تصنيف دمجي هي إحدى خوارزميات التصنيف أو ترتيب مجموعة من عناصر الرقمية تصاعديا، طورها العالم الألماني فون نيومان، تعتمد هذه الخوارزمية على مبدء «فرق تسد» (بالإنجليزية: divide and conquer)‏، عدد الخطوات اللازمة للخوارزمية لإنجاز المعالجة على مجموعة من مدخلات تقاس بـ N*Log N.[2][3][4]

خطوات الخوارزمية مفهوم خوارزمية التصنيف الدمجي يقوم على خطوات التالية:

  1. إذا كانت المصفوفة تحتوي على عنصر واحد أو أقل فإن المصفوفه مصنفة، لأنها تحتوي على عنصر واحد وبالتالي هو مصنف.
  2. قْسِّم كل مصفوفة غير مصنفة - أي تحتوي على أكثر من عنصر - إلى مصفوفتين.
  3. أعد ترتيب كل مصفوفة بطريقة الاستدعاء الذاتي recursively.
  4. ادمج كل مصفوتين (التي تم تريبها) إلى مصفوفة واحدة.

تعتمد الخوارزمية بشكل أساسي على مفهومين رئيسيين:

  1. المفهوم الأول: هو أن المصفوفات التي تحتوي على أقل عناصر يمكن ترتيبها بشكل أسرع وتحتاج إلى خطوات أقل.
  2. المفهوم الثاني: هو عملية دمج المصفوفات الصغيرة التي تحتوي على عناصر قليلة المرتبة لتشكيل مصفوفات أكبر مرتبة أيضا.

تطبيق من الأعلى إلى الأسفل (Top-down)

function merge_sort(list m)
// if list size is 1, consider it sorted and return it
if length(m) <= 1
 return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m up to middle
 add x to left
for each x in m after or equal middle
 add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)

في هذا المثال، الدالة merge تدمج المجموعتين الجزئيتين اليسرى واليمنى:

function merge(left, right)
var list result
while length(left) > 0 or length(right) > 0
 if length(left) > 0 and length(right) > 0
 if first(left) <= first(right)
  append first(left) to result
  left = rest(left)
 else
  append first(right) to result
  right = rest(right)
 else if length(left) > 0
  append first(left) to result
   left = rest(left)
  else if length(right) > 0
   append first(right) to result
   right = rest(right)
 end while
 return result

تطبيق من الأسفل إلى الأعلى (Bottom-up)

/* array A[] has the items to sort; array B[] is a work array */
BottomUpSort(int n, array A[n], array B[n])
{
  int width;

  /* each 1-element run in A is already "sorted". */

  /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted */
  for (width = 1; width < n; width = 2 * width)
    {
      int i;

      /* array A is full of runs of length width */
      for (i = 0; i < n; i = i + 2 * width)
        {
          /* merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
          /*  or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
          BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }

      /* now work array B is full of runs of length 2*width */
      /* copy array B to array A for next iteration */
      /*   a more efficient implementation would swap the roles of A and B */
      CopyArray(A, B, n);
      /* now array A is full of runs of length 2*width */
    }
}

BottomUpMerge(array A[], int iLeft, int iRight, int iEnd, array B[])
{
  int i0 = iLeft;
  int i1 = iRight;
  int j;

  /* while there are elements in the left or right lists */
  for (j = iLeft; j < iEnd; j++)
    {
      /* if left list head exists and is <= existing right list head */
      if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
        {
          B[j] = A[i0];
          i0 = i0 + 1;
        }
      else
        {
          B[j] = A[i1];
          i1 = i1 + 1;
        }
    }
}

مراجع

  1. ^ مذكور في: The Algorithm Design Manual. الصفحة: 122. الفصل: 4.5: Mergesort: Sorting by Divide-and-Conquer. المُؤَلِّف: Steven Skiena. تاريخ النشر: 2008. الناشر: شبرينغر.
  2. ^ "liboctave/util/oct-sort.cc". Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. مؤرشف من الأصل في 2019-02-06. اطلع عليه بتاريخ 2013-02-18. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.
  3. ^ Geffert، Viliam؛ Katajainen، Jyrki؛ Pasanen، Tomi (2000). "Asymptotically efficient in-place merging". Theoretical Computer Science. ج. 237: 159–181. DOI:10.1016/S0304-3975(98)00162-5.
  4. ^ V. J. Duvanenko, "Parallel Merge Sort", Dr. Dobb's Journal, March 2011 نسخة محفوظة 14 سبتمبر 2011 على موقع واي باك مشين.

Read other articles:

Negara Indonesia TimurNegara bagian RIS1946–1950 Panji daerah Coat of arms Wilayah N.I.T ditunjukkan pada warna merahIbu kotaMakassarLuas • 1946349.088 km2 (134.784 sq mi)Populasi • 1946 10.290.000 SejarahPemerintahan • JenisNegara bagianPresiden • 1946–1950 Tjokorda Gde Raka Soekawati Perdana Menteri • 1947 Nadjamuddin Daeng Malewa• 1947 Semuel Jusof Warouw• 1947–1949 Ida Anak Agung Gde Agung•...

 

 

Este artigo não cita fontes confiáveis. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: ABW  • CAPES  • Google (N • L • A) (Novembro de 2011) Angelo Secchi Angelo Secchi Nascimento 18 de junho de 1818Reggio Emilia Morte 26 de fevereiro de 1878 (59 anos) Nacionalidade Italiano Campo(s) Astronomia O Padre Angelo Secchi (Reggio Emilia, 18 de junho de 1818 — 26 de fevereiro ...

 

 

Cidade de BelizeBelize • Belize City Bandeira Apelido: The old capital, Belize Coordenadas 17° 29' 55 N 88° 11' 19 E País  Belize Distrito Belize Fundação 1638 Prefeito Darrell Bradley (UDP) Área     Total 35.667 km² População     Cidade (2015) 60.963    -Densidade metropolitana   488,42/km² Fuso horário   Verão (DST) UTC-6 (UTC-6) +1 (UTC) Website: http://www.belizecitycouncil.org A Ci...

South Korean Olympic judoka For the taekwondo practitioner, see Kim Jan-di (taekwondo). In this Korean name, the family name is Kim. Kim Jan-diPersonal informationBorn (1991-06-15) 15 June 1991 (age 32)OccupationJudokaSportCountrySouth KoreaSportJudoWeight class–57 kgCoached byLee Won-heeAchievements and titlesOlympic GamesR16 (2012, 2016)World Champ.R16 (2015, 2021)Asian Champ. (2010, 2011, 2013,( 2014, 2016) Medal record Women's judo Representing  South Korea Asian Games 2010 Gu...

 

 

GOLGA4 Наявні структури PDBПошук ортологів: PDBe RCSB Список кодів PDB 1R4A, 1UPT Ідентифікатори Символи GOLGA4, CRPF46, GCP2, GOLG, MU-RMS-40.18, golgin A4, Trans-GolgiI p230, Golgin 245, p230 Зовнішні ІД OMIM: 602509 MGI: 1859646 HomoloGene: 68224 GeneCards: GOLGA4 Онтологія гена Молекулярна функція • GTPase binding• GO:0001948, GO:0016582 protein binding Клітинна компонен

 

 

← 1964 •  • 1989 → Elección presidencial de Chile de 1970Presidente para el período 1970-1976 Fecha Viernes 4 de septiembre de 1970 Tipo Presidencial, nivel nacional Período 3 de noviembre de 1970 al 3 de noviembre de 1976 Demografía electoral Población 8 884 768 (c. 1970) Hab. registrados 3 539 747[1]​ Votantes 2 962 748 Participación    83.70 %  3.1 % Votos válidos 2 936 ...

Sporting event delegationTrinidad and Tobago at the1968 Summer OlympicsIOC codeTTO(TRT used at these Games)NOCTrinidad and Tobago Olympic CommitteeWebsitewww.ttoc.orgin Mexico CityCompetitors19 in 5 sportsFlag bearerRoger GibbonMedals Gold 0 Silver 0 Bronze 0 Total 0 Summer Olympics appearances (overview)19481952195619601964196819721976198019841988199219962000200420082012201620202024Other related appearances British West Indies (1960 S) Trinidad and Tobago competed at the 1968 Summe...

 

 

2008 studio album by Eli Young BandJet Black & JealousStudio album by Eli Young BandReleasedSeptember 16, 2008 (2008-09-16)GenreCountryLength45:54LabelUniversal SouthProducer Erik Herbst Mike Wrucke Eli Young Band chronology Live at the Jolly Fox(2006) Jet Black & Jealous(2008) Life at Best(2011) Singles from Jet Black & Jealous When It RainsReleased: October 22, 2007 Always the Love SongsReleased: September 29, 2008 Radio WavesReleased: June 29, 2009 Guinev...

 

 

2006 single by Kate RyanAll For YouSingle by Kate Ryanfrom the album Alive B-sideJe Donnerais ToutReleasedNovember 24, 2006Recorded2006GenreElectronic, houseLength3:09LabelARSSongwriter(s)Ashley Cadell, Bj Caruana, Kate Ryan, Niklas Bergwall, Niclas KingsProducer(s)2NKate Ryan singles chronology Alive (2006) All For You (2006) Voyage Voyage (2007) Audio videoAll for You on YouTube All For You was the third and last single of Kate Ryan's third album Alive. Formats and track listings CD Single&...

Shape note sheet music for What Wondrous Love Is This in the 1854 edition of The Southern Harmony. The melody is in the middle staff. What Wondrous Love Is This (often just referred to as Wondrous Love) is a Christian folk hymn from the American South.[1] Its text was first published in 1811, during the Second Great Awakening, and its melody derived from a popular English ballad (Roud number 5089).[2] Today it is a widely known hymn included in hymnals of many Christian denomi...

 

 

Railway station in Tokyo, Japan KS51 Keisei Kanamachi Station京成金町駅The station entrance in January 2016General informationLocationKanamachi, Katsushika-ku, TokyoJapanOperated by Keisei Electric RailwayLine(s)KS Keisei Kanamachi LineDistance2.5 km from Keisei TakasagoPlatforms1 side platformTracks1Connections JL21 Kanamachi Station Bus stop ConstructionStructure typeGround-levelOther informationStation codeKS51HistoryOpened21 October 1913Previous namesKanamachi (until 1931)Servic...

 

 

Українці Північної Македонії — одна з національних меншин на території Північної Македонії, яка сформувалась в цій країні під впливом історико-політичних причин. Більшість українців в Македонії — нащадки емігрантів з минулих Російської та Австро-Угорської імпер...

Pemilihan umum Bupati Bangka 201320082018Kandidat Peta persebaran suara Peta lokasi Bangka Bupati petahanaH. Yusroni Yazid , SE PPP Bupati terpilih belum diketahui Sunting kotak info • L • BBantuan penggunaan templat ini Pemilihan umum Bupati Bangka 2013 akan dilaksanakan pada 26 Juni 2013 untuk memilih Bupati dan Wakil Bupati Bangka periode 2013-2018. Kandidat KPUD Bangka telah menetapkan empat pasang kandidat peserta Pilbup Bangka 2013.[1] Pada 1 Mei lalu, KPUD telah m...

 

 

Padang UtaraKecamatanKantor Camat Padang UtaraPeta lokasi Kecamatan Padang UtaraNegara IndonesiaProvinsiSumatera BaratKotaPadangPemerintahan • CamatPagara, S.STP., M.M.[1]Populasi • Total69,479 jiwaKode Kemendagri13.71.04 Kode BPS1371070 Nagari/kelurahan7 Padang Utara adalah sebuah kecamatan di Kota Padang, Sumatera Barat, Indonesia. Kecamatan ini terdiri dari tujuh kelurahan, yakni Gunung Pangilun, Ulak Karang Utara, Ulak Karang Selatan, Air Tawar Timur, ...

 

 

Family of fungi Steccherinaceae Steccherinum ochraceum Scientific classification Kingdom: Fungi Division: Basidiomycota Class: Agaricomycetes Order: Polyporales Family: SteccherinaceaeParmasto (1968) Type genus SteccherinumGray (1821) Synonyms[1] Mycorrhaphiaceae Jülich (1982) The Steccherinaceae are a family of about 200 species of fungi in the order Polyporales. It includes crust-like, toothed, and poroid species that cause a white rot in dead wood. Taxonomy The family was circumsc...

Joshua SuhermanLahir3 November 1992 (umur 31)Surabaya, Jawa Timur, IndonesiaPekerjaanPemeranpenyanyipresenterkomedianTahun aktif1996—sekarangSuami/istriClairine Clay ​(m. 2021)​Keluarga Natasha Mannuela (ipar) Giovanni Vergio (ipar) Novita Sari (mertua) Karier musikGenre Pop anak Pop LabelHarpa Records Joshua Suherman (lahir 3 November 1992) adalah pemeran, penyanyi, presenter, dan komedian Indonesia. Kehidupan awal Joshua lahir di Surabaya pada tangga...

 

 

Mahane IsraelLingkunganNegara IsraelProvinsiYerusalemKotaYerusalemZona waktuUTC+3 (EAT) • Musim panas (DST)UTC+3 (EAT) Mahane Israel adalah sebuah lingkungan di kota suci Yerusalem di Provinsi Yerusalem, tepatnya di sebelah timur Israel.[1] Referensi ^ National Geospatial-Intelligence Agency. GeoNames database entry. (search Diarsipkan 2017-03-18 di Wayback Machine.) Accessed 12 May 2011. lbsLingkungan di YerusalemLingkungan-lingkungan Yerusalem sebelah timur garis ge...

 

 

Запрос «Cosworth DFV» перенаправляется сюда. На эту тему нужно создать отдельную статью. Cosworth Group Тип Публичная компания Основание 1958 Основатели Майк Костин[d] и Кейт Дакворт[d] Расположение  Великобритания: Нортгемптон Ключевые фигуры Джеральд Форсайт Кевин Калховен От...

PlayStation emulator Virtual Game StationWindows GUI of Virtual Game StationOriginal author(s)Aaron GilesDeveloper(s)ConnectixInitial releaseJanuary 5, 1999; 24 years ago (1999-01-05) [1]Stable release1.4.1 / October 11, 2000; 23 years ago (2000-10-11) Operating systemClassic Mac OS, Microsoft WindowsTypeEmulatorLicenseProprietaryWebsiteVirtual Game Station at the Wayback Machine (archive index) The Virtual Game Station (VGS, code named Bonestor...

 

 

Historical region in south-central Turkey BinbirkiliseThe ruins of Binbirkilise are located in and around the modern village Madenşehri.Shown within TurkeyLocationMadenşehri, Karaman Province, TurkeyRegionLycaoniaCoordinates37°26′14″N 33°08′39″E / 37.43722°N 33.14417°E / 37.43722; 33.14417HistoryFoundedApproximately 3rd centuryAbandonedApproximately 8th century Church ruins in Madenşehri Binbirkilise (literally: Thousand and One Churches) is a district i...

 

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!