خوارزمية الاختيار

خَوَارِزمِيَّةُ الاِختِيَارِ (بالإنجليزية: selection algorithm)‏ هي خوارزمية لإيجاد مكان عدد بالترتيب حسب التصنيف، وتعد هذه الخوارزمية من أشهر الخوارزميات لأنه يمكن تطبيقها بزمن خطي ولاستخداماتها المتعددة في علوم الحاسوب والطريقة التي تتم بها عن طريق الاستدعاء الذاتي أو recursion

مقدمة

خوارزمية الاختيار هي طريقة بحث فعّـالة حيث تُعطَى الخوارزمية عدد i, والهدف هو إيجاد العدد ال-i في القائمة بعد التصنيف -SORTING- هناك عدة طرق لإيجاد هذا الهدف وقد تم التوصل إلى خوارزمية فعالة بزمن خطي - linear time algorithm-

حالات خاصة

عندما يكون i=1 عندها على الخوارزمية إيجاد العدد الأول من حيث الترتيب أي اصغر قيمة في القائمة وهذه المهمة بسيطة جدا وإيجاد هذه القيمة يتم عن طريق بحث خطي مع متغيِّر إضافيّ وها هي طريقة لفعل هذا: 

int FindMin(int[] A)
{
int min=A[0];
for(int j=1;j<=A.length;j++)
{ 
  if(A[j]<A[0])
  {
    min=A[j];
  }
}
return min;
}

وحالة أخرى هي i=n وعندها يجب ايجاد القيمة الكبرى وبطريقة مشابهة لايجاد القيمة الصغرى.

اختيار بالتصنيف

نبدأ أولا بالطريقة السهلة وهي تتم عن طريق تحويل الاختيار إلى تصنيف ثم التوجه للعدد المطلوب أي: 

int select(int[] A,int i)
{
return (A.sort())[i]
}

هذه الطريقة صحيحة ولكن الوقت الذي تحتاجه هو: ((O(nlog(n ونريد ان نصل لخوارزمية فعالة بوقت خطي بالنسبة للمدخل!

الخوارزمية الخطية

هذه الخوارزمية تستخدم طريقة الاستدعاء الذاتي (العودية) وهي كالتالي: اسم هذه الخوارزمية سيكون: اختيار

  • إذا n=1 نرجع القيمة الوحيدة الموجودة وهو بمثابة العدد ال -i
  • إذا n>1 حينها:
  1. - قسم ال-n أعداد في القائمة ل- حيث كل قائمة تحوي 5 أعداد وقائمة أخيرة تحوي البواقي وهي بكبر:n mod 5
  2. - جِد القيمة الوسطى للقوائم (تستطيع ان تصنف ثم تجد لكل قائمة القيمة الوسطى)
  3. - استدعي اختيار لايجاد القيمة الوسطى،x, ل الاعداد التي وجدتها في 2
  4. - قسم القائمة حول x بواسطة partition ولنقل أن الأعداد في القائمة السفلى عددها k والقائمة العليا هي n-k
  5. - استدعي اختيار بشكل ذاتي لايجاد العدد ال-i في القائمة السفلى إذا: i≤k أو العدد ال- i-k الأصغر إذا i>k

تحليل زمن الخوارزمية

  • معادلة الاستدعاء الذاتي:

  • وحلها كالتالي:

وصلات خارجية

Read other articles:

Windows Server 2016

Windows Server 2016Versi dari sistem operasi Windows NTPembangunMicrosoftModel sumberperangkat lunak peroranganDirilis kemanufaktur26 September 2016; 7 tahun lalu (2016-09-26)Ketersediaanuntuk umum12 Oktober 2016; 7 tahun lalu (2016-10-12)Rilis terbaru10.0.14393.3866 / 11 Agustus 2020; 3 tahun lalu (2020-08-11)Metode updateWindows Update, Windows Store, Windows Server Update Services, SCCMPlatformx64Tipe KernelHibrida (Windows NT)Didahului olehWindows 10 MobileDigantikan olehWi...

 

History of Michigan

For the magazine, see Michigan History (magazine). The Great Seal of the State of Michigan History of Michigan By year Pre-statehood U.S. Civil War Since 1900 Topics: Cities - Politics  Michigan portalvteThe history of human activity in Michigan, a U.S. state in the Great Lakes, began with settlement of the western Great Lakes region by Paleo-Indians perhaps as early as 11,000 B.C.E. One early technology they developed was the use of native copper, which they would fashion into tool...

 

Tōshō-gū

Shinto shrine dedicated to Tokugawa Ieyasu Yomeimon at Nikkō Tōshō-gū Tōshō-gū (東照宮) is any Shinto shrine in which Tokugawa Ieyasu (1543–1616) is enshrined.[1] Ieyasu was the founder of the Tokugawa shogunate (1603–1868), which is the third and last of the shogunal governments in Japanese history. He was deified with the name Tōshō Daigongen (東照大権現), the Great Gongen, Light of the East[2] (A Gongen is believed to be a buddha who has appeared on Ear...

2005 Quebec student protests

2005 Quebec student protestsDateFebruary 24, 2005 – April 14, 2005LocationQuebec, CanadaMethods Street protesters Occupations Picketing Student strikes Hunger strike Barricades Online activism The 2005 Quebec student protests were a series of student strikes and student protests in opposition to budget cuts of C$103 million in the Grants and Loans program by the Charest government. It occurred between February 24 and April 2005 and involved thousands of CEGEP and universities students from ...

 

Rizki Yanu Kresnayandi

Rizki Yanu KresnayandiInformasi pribadiKebangsaan IndonesiaLahir25 Januari 1989 (umur 35)Magelang, IndonesiaPeganganKananGanda PutraPeringkat tertinggi115 (5 Juli 2011)Peringkat saat ini154 Albert Saputra (4 Oktober 2011) Albert Saputra (lahir 25 Januari 1989) adalah salah satu pemain bulu tangkis Ganda Putra Indonesia. Prestasi 2007 Perempat final Waikato International 2007 (bersama Komala Dewi) 2008 Runner - up Laos Future Series 2008 (bersama Albert Saputra) Perrmpat fi...

 

WBRN (AM)

Radio station in Big Rapids, MichiganWBRNBig Rapids, MichiganBroadcast area[1] (Daytime)[2] (Nighttime)Frequency1460 kHzBrandingNewsradio 1460 & 107.7 FM WBRNProgrammingFormatNews/TalkAffiliationsMichigan Radio NetworkDetroit LionsOwnershipOwnerMentor PartnersHistoryFirst air date1953Call sign meaningBig Rapids, MichigaNTechnical informationFacility ID70506ClassBPower5,000 watts (Daytime)2,500 watts (Nighttime)Translator(s)96.5 MHz W243EN (Big Rapids)LinksWebcastListen LiveWebsitewbr...

Marcantonio Raimondi

Questa voce o sezione sull'argomento arte ha problemi di struttura e di organizzazione delle informazioni. Motivo: Metà della voce è praticamente la citazione dal Vasari, che andrebbe riformulata e abbreviata. Risistema la struttura espositiva, logica e/o bibliografica dei contenuti. Nella discussione puoi collaborare con altri utenti alla risistemazione. Segui i suggerimenti del progetto di riferimento. Ritratto di Marcantonio Raimondi,dalle Vite del Vasari Marcantonio Raimondi (Moli...

 

俄亥俄州

  「俄亥俄」重定向至此。关于其他用法，请见「俄亥俄 (消歧义)」。 俄亥俄州 美國联邦州State of Ohio 州旗州徽綽號：七葉果之州地图中高亮部分为俄亥俄州坐标：38°27'N－41°58'N, 80°32'W－84°49'W国家 美國加入聯邦1803年3月1日，在1953年8月7日追溯頒定（第17个加入联邦）首府哥倫布（及最大城市）政府 • 州长（英语：List of Governors of {{{Name}}}]]） •&...

 

Vigala-Vanamõisa

Village in Estonia Village in Rapla County, EstoniaVigala-VanamõisaVillageCountry EstoniaCountyRapla CountyParishMärjamaa ParishTime zoneUTC+2 (EET) • Summer (DST)UTC+3 (EEST) Vigala-Vanamõisa (Vanamõisa until 2017) is a village in Märjamaa Parish, Rapla County in western Estonia.[1] References ^ Classification of Estonian administrative units and settlements 2014[dead link] (retrieved 28 July 2021) vteSettlements in Märjamaa ParishBorough Märjamaa Vill...

2022 K League 1

40th season of the top division of professional football in South Korea Football league seasonHana 1QK League 1Season2022Dates19 February – 29 October 2022ChampionsUlsan Hyundai(3rd title)RelegatedGimcheon SangmuSeongnam FCChampions LeagueUlsan HyundaiJeonbuk Hyundai MotorsPohang SteelersIncheon UnitedMatches played228Best PlayerLee Chung-yongTop goalscorerCho Gue-sung Joo Min-kyu (17 goals each)← 2021 2023 → The 2022 K League 1, also known as the Hana 1Q K League 1 for sponsorship reas...

 

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

 

SS Exodus

United States packet steamship Exodus 1947 derelict in Haifa in 1952 History Name 1927: Florida (intended) 1927–44, 1945–47: President Warfield 1944–45: USS President Warfield 1947: Exodus 1947 Namesake 1927: S. Davies Warfield 1947: The Exodus Owner 1928–42: Baltimore Steam Packet Co 1942–43: Ministry of War Transport 1943–47: War Shipping Administration 1947: Haganah Operator 1928–42: Baltimore Steam Packet Co 1942–43: Coast Lines, Ltd 1944–45: United States Navy 1947: Mos...

قاتل متسلسل

لا يزال النص الموجود في هذه الصفحة في مرحلة الترجمة من الإنجليزية إلى العربية. إذا كنت تعرف اللغة الإنجليزية، لا تتردد في الترجمة. جزء من سلسلة حولالقتل القتل العمد الاغتيال قتل الأطفال القتل الرضائي القتل المأجور القتل بسبب الشرف التضحية البشرية القتل الشهواني الإعدام ب�...

 

Margaret of Anjou

Queen of England (1445–61), (1470–71) For the 13th-century French countess, see Margaret, Countess of Anjou. Margaret of AnjouDetail from the Talbot Shrewsbury BookQueen consort of EnglandTenure23 April 1445 – 4 March 14613 October 1470 – 11 April 1471Coronation30 May 1445Queen consort of France (disputed) Tenure23 April 1445 – 19 October 1453Born23 March 1430Pont-à-Mousson, Duchy of Bar, Holy Roman EmpireDied25 August 1482 (aged 52)Dampierre-sur-Loire, Anjou, France...

 

Bandha (Jainism)

Interaction of soul and matter in Jainism (Indian religion) Part of a series onJainism Jains History Timeline Index Philosophy Anekantavada Cosmology Ahimsa Karma Dharma Mokṣa Kevala Jnana Dravya Tattva Brahmacarya Aparigraha Gunasthana Saṃsāra EthicsEthics of Jainism Mahavratas (major vows) Ahiṃsā (non-violence) Satya (truth) Asteya (non-stealing) Brahmacarya (chastity) Aparigraha (non-possession) Anuvratas (further vows) Sāmāyika Sallekhana Jain prayers Bhaktamara Stotra Micchami ...

بوجا

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها. بوجا (حسب الأبجدية العالمية للنقحرة السنسكريتية: pūjā، بالديوناكري: पूजा، وحسب الجمعية الصوتية الدولية: [pu:d͡ʒɑ:]) هي شعيرة صلاة يؤديها الهندوس عند الصلاح ليتعبّدوا إلهًا أو �...

 

Chongpyong station

Railway station in North Korea This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Chongpyong station – news · newspapers · books · scholar · JSTOR (April 2016) For the station in South Korea, see Jeongpyeong station. Chŏngp'yŏng정평Korean nameHangul정평역Hanja定平驛Revised RomanizationJeongp...

 

County Aransas, Texas

Aransas County, TexasLokasi di negara bagian TexasLokasi negara bagian Texas di Amerika SerikatDidirikan1871Asal namaThe Rio Nuestra Senora de Aranzazu, a Spanish outpost in early TexasSeatRockportKota terbesarRockportWilayah • Keseluruhan528 sq mi (1.367 km2) • Daratan252 sq mi (652 km2) • Perairan276 sq mi (715 km2), 52.29%Populasi • (2000)22.497 • Kepadatan89/sq mi (34/km²)Zona wa...

User talk:Vchimpanzee

Archives 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 Commons talk Mediawiki talk Books & Bytes – Issue 60 The Wikipedia Library: Books & Bytes Issue 60, November – December 2023 Three new partners Google Scholar integration How to track partner suggestions Read the full newsletter Sent by MediaWiki message delivery on behalf of The Wikipedia Library team --13:36, 24 January 2024 (UTC)[reply] Books & Bytes – Issue 61 The Wikipedi...

 

Extended Play (Austin Mahone EP)

2013 EP by Austin MahoneExtended PlayEP by Austin MahoneReleasedMay 29, 2013 (2013-05-29)Recorded2012–2013GenreTeen popLength20:42Label Chase Republic Producer DJ Frank E Mike Fresh Trent Mazur Bei Maejor Austin Mahone Bruce Robinson Steve Mac Matt Mahaffey Austin Mahone chronology Extended Play(2013) The Secret(2014) Singles from Extended Play Say SomethinReleased: June 5, 2012 Say You're Just a FriendReleased: December 3, 2012 Deluxe editionThe deluxe edition artwor...