طیف الکترومغناطیس — به زبان ساده

الکتریسیته ساکن — به زبان ساده

هنگامی که صاعقه با شدت به سمت زمین حرکت می‌‌کند، نمایش بسیار واضحی از قدرت الکتریسیته ساکن (انرژی الکتریکی جمع شده در یک جا) را می‌بینیم. در واقع، صاعقه یک نمونه قابل مشاهده از الکتریسیته ساکن است که تحت کنترل ما نیست. اما در موارد دیگر، از چاپگرهای لیزری و دستگاه‌‌های فتوکپی گرفته تا در نیروگاه‌‌ها برای از بین بردن آلودگی، الکتریسیته ساکن بسیار مفید است. در این آموزش، نگاهی دقیق‌‌تر به الکتریسیته ساکن و کاربرد آن می‌اندازیم.

تصویر بالا صاعقه را نشان می‌دهد. صاعقه حجم بسیار زیادی از الکتریسیته ساکن است که در آن، انرژی پتانسیل الکتریکی انباشته شده و به صورت یک جریان الکتریکی ناگهانی و سریع از آسمان به سوی زمین رها می‌‌شود.

الکتریسیته ساکن و جاری

هنگامی که یک بادکنک را روی پیراهن خود مالش می‌‌دهیم، در واقع الکتریسیته ساکن ایجاد می‌‌کنیم و به همین دلیل است که بادکنک به پیراهن می‌‌چسبد. مالش، الکترون‌‌ها را از روی پیراهن – که به صورت مثبت باردار می‌‌شود – به روی لاستیک بادکنک – که به صورت منفی باردار می‌‌شود – انتقال می‌‌دهد. بارهای مخالف باعث می‌‌شود که این دو شیء به هم بچسبند.

در قرن نوزدهم میلادی، پیشگامانی همچون «آلساندرو ولتا» (Alessandro Volta)، «مایکل فارادی» (Michael Faraday)، «جوزف هنری» (Joseph Henry) و «توماس ادیسون» (Thomas Alva Edison)، به اسرار الکتریسیته، چگونگی تولید و کاربردهای آن پی بردند. پیش از آن، الکتریسیته بیشتر یک موضوع عجیب بود. در آن روزها، مردم با استفاده از هیزم یا اجاق‌‌های زغال سنگ غذا می‌‌پختند و خانه‌‌های خود را گرم می‌‌کردند و اتاق‌‌هایشان را با شمع یا چراغ‌‌های نفتی روشن می‌‌کردند و وسایلی مثل رادیو یا تلویزیون، تلفن همراه یا کامپیوتر وجود نداشت.

«الکتریسیته مدرن» که ما آن را الکتریسیته جاری (یا جریان الکتریکی) می‌‌نامیم، نیروی هر چیزی از تلفن همراه جیبی شما گرفته تا مترویی که برای رفتن به مدرسه یا سر کار سوار آن می‌‌شوید را تأمین می‌‌کند. الکتریسیته جاری، یک انرژی‌‌‌ است که در طول یک سیم فلزی از جایی که تولید می‌‌شود (مثل یک نیروگاه برق بسیار بزرگ یا یک باتری بسیار کوچک) به جایی که مصرف می‌‌شود (اغلب یک موتور الکتریکی، المنت حرارتی یا لامپ) حرکت می‌‌کند. در حقیقت، الکتریسیته جاری با حمل انرژی از جایی به جای دیگر همیشه در حال حرکت است.

یک نمایش کلاسیک دیگر از الکتریسیته ساکن، این است که یک شانه پلاستیکی را روی پیراهن خود مالش دهیم و آن را نزدیک تکه‌‌های کوچک کاغذ ببریم. خواهیم دید که شانه می‌‌تواند تکه‌‌های کاغذ را جذب کند. جذب یک تکه کاغذ توسط شانه شبیه برداشتن یک گیره کاغذ به وسیله آهنربا است. هنگامی که آهنربا یک گیره کاغذ را جذب می‌‌کند، گیره کاغذ جذب‌شده نیز می‌‌تواند گیره‌های دیگری را به صورت زنجیروار بلند کند، اما یک خط‌‌کش با بار ساکن نمی‌‌تواند این کار را انجام دهد.

پیش از قرن نوزدهم، مردم فقط الکتریسیته ساکن را می‌‌شناختند. یونانیان باستان دریافتند که مالش اشیاء به همدیگر می‌‌تواند به راحتی بار الکتریکی ساکن (انبوهی از الکتریسیته ساکن) ایجاد کند، اما تصور نمی‌‌کردند که همین انرژی می‌‌تواند برای تولید نور یا دستگاه‌‌های برقی مورد استفاده قرار گیرد. یکی از افرادی که به ایجاد ارتباط بین الکتریسیته ساکن و الکتریسیته جاری کمک کرد، سیاستمدار، ناشر و دانشمند آمریکایی، «بنجامین فرانکلین» (Benjamin Franklin) بود.

در سال 1752، فرانکلین سعی کرد اسرار الکتریسیته را کشف کند و این کار را خیلی خوب انجام داد. او یک بادبادک را در هوای طوفانی همراه با رعد و برق به پرواز در آورد تا خودش مقداری انرژی الکتریکی دریافت کند (یک کار بسیار خطرناک). صاعقه به سرعت به پایین بادبادک و به زمین اصابت ‌‌کرد، در حالی که فرانکلین خودش را عایق نکرده بود و امکان داشت به راحتی بمیرد. فرانکین پی برد هنگامی که صاعقه الکتریسیته ساکن جمع شده در آسمان را به سمت پایین تا سطح زمین حمل می‌‌کند، به الکتریسیته جاری تبدیل می‌‌شود. از طریق چنین تحقیقاتی بود که یکی از معروف‌‌ترین اختراعاتش، میله برق‌‌گیر (رسانای برق) را به ثبت رساند. کار فرانکلین راه را برای انقلاب الکتریکی قرن نوزدهم باز کرد و در حقیقت، زمانی جهان دگرگون شد که افرادی همچون ولتا و فارادی، با اتکا بر کشفیات فرانکلین، به چگونگی تولید الکتریسیته و کارایی آن پی بردند.

انرژی پتانسیل و جنبشی

یک راه دیگر برای بررسی الکتریسیته ساکن و جاری، مرتبط کردن آن‌ها با انرژی است. الکتریسیته را می‌‌توان نوعی انرژی پتانسیل در نظر گرفت: یک انرژی‌‌ که ذخیره می‌‌شود تا به کاری مفید تبدیل شود. به همین ترتیب، الکتریسیته جاری نیز تقریباً مشابه انرژی جنبشی خواهد بود: انرژی هنگام حرکت، هرچند از نوع الکتریکی باشد. درست همان‌گونه که می‌‌توان انرژی پتانسیل را به انرژی جنبشی تبدیل کرد (مثلاً با رها کردن یک تخته سنگ از بالای یک تپه و غلتیدن آن به سمت پایین)، می‌‌توان الکتریسیته ساکن را نیز به الکتریسیته جاری (همان چیزی که در صاعقه اتفاق می‌‌افتد) و بالعکس، الکتریسیته جاری را به الکتریسیته ساکن تبدیل کرد (همان کاری که مولد واندوگراف انجام می‌‌دهد).

 الکتریسیته ساکن چگونه ایجاد می‌شود؟

ما نیز مانند یونانیان باستان، تصور می‌‌کنیم که الکتریسیته ساکن از مالش اشیاء به یکدیگر به وجود می‌‌آید. برای مثال، حتماً تا به حال تجربه کرده‌‌اید که وقتی روی یک فرش نایلونی راه می‌‌روید و پس از آن، یک دستگیره فلزی را لمس می‌‌کنید، با یک شوک الکتریکی کوچک مواجه می‌‌شوید. این اتفاق به این دلیل روی می‌‌دهد که هنگام راه رفتن روی فرش، بدن شما بار ساکن جمع می‌‌کند و با لمس دستگیره این بار تخلیه می‌‌شود. سؤالی که در اینجا به وجود می‌‌آید این است که یک شیء مثلاً یک بادکنک را روی کدام قسمت لباس مالش دهیم تا به آن بچسبد؟ ممکن است پاسخ شما این باشد که الکتریسیته ساکن به نوعی مرتبط با اصطکاک است که همان عمل مالش دادن شدید چیزی است که انبوهی از انرژی الکتریکی تولید می‌‌کند (درست به همان روشی که اصطکاک می‌‌تواند گرما و حتی آتش تولید کند). اما پاسخ صحیح چیز دیگری است.

اثر الکتریکی مالشی

همان‌طور که گفته شد، برای ایجاد الکتریسیته ساکن، باید دو شیء (دو ماده مختلف) را در تماس با یکدیگر قرار داده و آن‌ها را به شدت به یکدیگر مالش دهیم، به گونه‌‌ای که به طور پیوسته با هم تماس داشته باشند. تولید الکتریسیته ساکن با این روش را الکتریسیته مالشی (یا اثر الکتریکی مالشی) می‌‌نامند. پرسشی که ممکن است برای شما به وجود آید این است که چرا مالش دادن دو ماده مختلف، الکتریسیته ساکن تولید می‌‌کند؟ پاسخ این پرسش به ساختار مواد بر می‌‌گردد. همان‌طور که می‌‌دانیم تمام مواد از اتم‌‌ها ساخته می‌‌شوند. این اتم‌‌ها یک هسته مرکزی مثبت دارند که توسط ابر الکترونی (حاوی الکترون‌‌های متحرک) محصور شده است.

بسته به نوع ماده، ممکن است اتم‌‌های برخی از مواد نسبت به اتم‌‌های مواد دیگر کشش قوی‌‌تری روی الکترون‌‌ها داشته باشند. بنابراین، اگر دو ماده مختلف که یکی از آن‌ها الکترون‌‌های بیشتری نسبت به دیگری جذب می‌‌کند را در تماس با یکدیگر قرار دهیم، این امکان وجود دارد که الکترون‌های یکی از مواد به طرف دیگری جذب شوند. در واقع، هنگامی که دو ماده را از یکدیگر جدا می‌‌کنیم، الکترون‌ها به سمت ماده‌‌ای جهش می‌‌یابند که آن‌ها را قوی‌‌تر جذب می‌‌کند. در نتیجه، یکی از مواد تعدادی الکترون اضافه به دست می‌‌آورد (به صورت منفی باردار می‌‌شود) و ماده دیگر تعدادی الکترون از دست می‌‌دهد (به صورت مثبت باردار می‌‌شود). هنگامی که اشیاء را پیوسته به همدیگر مالش می‌‌دهیم، در حقیقت احتمال اینکه اتم‌‌های بیشتری در مبادله الکترونی شرکت کنند را افزایش می‌‌دهیم و به همین دلیل است که بار ساکن جمع می‌‌شود.

ٰتصویر بالا اثر الکتریکی مالشی را نشان می‌دهد. در (1)، ابونیت (لاستیک سیاه و سخت که در اینجا به صورت یک میله سیاه نشان داده شده است) و پشم (که به رنگ خاکستری نشان داده شده است) در حالت عادی هیچ گونه بار الکتریکی ندارند. در (2) آن‌ها را در تماس با یکدیگر قرار می‌‌دهیم. ابونیت، الکترون‌‌های پشم را جذب می‌‌کند. و در نهایت، در (3) آن‌ها را از یکدیگر جدا می‌‌کنیم. الکترون‌ها پشم را رها کرده و روی ابونیت باقی می‌‌مانند که باعث می‌‌شود ابونیت به صورت منفی و پشم به صورت مثبت باردار شود. مالش این دو جسم به یکدیگر، تماس بین آن‌ها افزایش داده و احتمال انتقال الکترون‌ها از پشم به ابونیت را بیشتر می‌‌کند. بار منفی روی ابونیت دقیقاً هم‌‌اندازه بار مثبت روی پشم است؛ به عبارت دیگر، هیچ بار خالصی ایجاد نمی‌‌شود.

مجموعه الکتریکی مالشی

اگر تولید الکتریسیته ساکن را با مواد گوناگون آزمایش کنیم، خواهیم دید که هنگام مالش دادن، بعضی از آن‌ها بار مثبت و بعضی دیگر بار منفی به دست می‌‌آورند. برخی مواد نیز بار بیشتری نسبت به سایر مواد جذب خواهند کرد. بنابراین، می‌‌توان مواد را بر اساس بار به دست آمده، به ترتیب از مثبت تا منفی دسته‌‌بندی کرد. لازم به ذکر است که ترتیب این فهرست به هر دلیلی ممکن است تغییر کند. برای مثال، نوع تغییر مواد تشکیل‌‌دهنده در لاستیک می‌‌تواند ماهیت آن را تغییر دهد.

ماده	بار الکتریکی
هوا	+
پوست	+
چرم	+
پنبه نسوز	+
شیشه	+
میکا	+
کوارتز	+
نایلون	+
پشم	+
مو	+
سرب	+
ابریشم	+
آلومینیوم	+
کاغذ	0
پنبه	0
فولاد	0
چوب	0
کهربا	–
لاستیک	–
لاستیک سخت	–
نیکل	–
مس	–
برنج	–
نقره	–
طلا	–
پلاتینیوم	–
پلی استر	–
پلی استیرن	–
نئوپرین	–
ساران (فیلم چسبان)	–
پلی اتیلن	–
پلی پروپیلن	–
پلی وینیل کلراید (PVC)	–
سلنیم	–
تفلون	–
لاستیک سیلیکون	–
ابونیت (لاستیک خیلی سخت)	–

این فهرست، مجموعه الکتریکی مالشی نامیده می‌‌شود. اگر در این مجموعه دو ماده‌‌ای را به هم مالش دهیم که در جدول فاصله زیادی از هم دارند، الکتریسیته ساکن بیشتری را انباشته خواهند کرد، اما در صورتی که این دو ماده خیلی به هم نزدیک باشند، به سختی می‌‌توان آن‌ها را وادار به تجمع هر باری کرد؛ حتی اگر به شدت به یکدیگر مالش داده شوند. این مسئله تأیید می‌‌کند که الکتریسیته ساکن صرفاً ناشی از مالش دادن اشیاء نیست، بلکه به ماهیت موادی بر می‌گردد که ما آن‌ها را در تماس با یکدیگر قرار می‌‌دهیم.

کاربرد الکتریسیته ساکن

شاید فکر کنید که الکتریسیته ساکن با وجود اینکه پدیده بسیار جالبی است، هیچ کاربرد مفیدی ندارد. اما این تصور اشتباه است، چرا که الکتریسیته ساکن در هر نوع تکنولوژی امروزی به صورت روزمره مورد استفاده قرار می‌‌گیرد. برای مثال، چاپگرهای لیزری و دستگاه‌‌های فتوکپی از الکتریسیته ساکن برای جمع کردن جوهر روی درام و انتقال آن روی کاغذ استفاده می‌‌کنند. سم‌‌پاشی محصولات کشاورزی نیز متکی به الکتریسیته ساکن است، زیرا کمک می‌‌کند آفت‌‌کش‌‌ها به شاخ و برگ گیاهان بچسبند و به صورت یکنواخت روی برگ‌‌ها توزیع شوند. دستگاه‌‌های خودکار اسپری رنگ کارخانه نیز از روشی مشابه استفاده می‌‌کنند تا قطرات کوچک رنگ را جذب بدنه فلزی اتومبیل کنند، نه ماشین‌‌آلات اطراف آن. در بسیاری از نیروگاه‌‌ها و کارخانه‌‌های شیمیایی نیز، الکتریسیته ساکن در دودکش‌‌ها برای پاکسازی آلودگی به کار می‌‌رود.

تصویر بالا جلوگیری از رهاسازی آلودگی هوا به بیرون از دودکش‌‌ها توسط الکتریسیته ساکن را نشان می‌دهد. در این روش، ابتدا بار الکتریکی ساکن به دود می‌‌دهند، سپس آن را از طریق یک توری فلزی با بار مخالف جمع می‌‌کنند که باعث می‌‌شود ذرات کثیف دوده از بین برود.

منبع: فرادرس

الگوریتم پریم — به زبان ساده

الگوریتم دایجسترا (Dijkstra) — از صفر تا صد

«الگوریتم دایجسترا» (Dijkstra’s Algorithm) یا «اولین الگوریتم کوتاه‌ترین مسیر دایجسترا» (Dijkstra’s Shortest Path First Algorithm | SPF) (البته تلفظ صحیح این نام، الگوریتم دایجسترا است که ب صورت متداول به آن دایجسترا گفته می‌شود)، الگوریتمی است که برای پیدا کردن کوتاه‌ترین مسیر بین دو «گره» (Node | راس) در گراف به کار می‌رود. این گراف، ممکن است نشان‌گر شبکه جاده‌ها یا موارد دیگری باشد. الگوریتم دایجسترا در سال 1۹۵۶، توسط دانشمند کامپیوتری با نام «ادسخر ویبه دیکسترا» (Edsger Wybe Dijkstra) مطرح و سه سال بعد، منتشر شد. الگوریتم دایجسترا دارای انواع گوناگونی است. الگوریتم اصلی، کوتاه‌ترین مسیر بین دو گره را پیدا می‌کند؛ اما نوع متداول‌تر این الگوریتم، یک گره یکتا را به عنوان گره مبدا (آغازین) در نظر می‌گیرد و کوتاه‌ترین مسیر از مبدا به دیگر گره‌ها در گراف را با ساختن درخت کوتاه‌ترین مسیر پیدا می‌کند.

برای یک گره مبدا داده شده، الگوریتم، کوتاه‌ترین مسیر بین آن گره و دیگر گره‌ها را پیدا می‌کند. همچنین، الگوریتم دایجسترا برای پیدا کردن کوتاه‌ترین مسیر از یک گره یکتا به گره مقصد یکتای دیگری به کار می‌رود؛ برای انجام این کار، الگوریتم هنگامی که کوتاه‌ترین مسیر از مبدا به مقصد را پیدا کند، متوقف می‌شود. برای مثال، اگر گره‌های گراف نشان‌گر شهرها و یال‌ها هزینه سفر بین شهرهایی باشند که با جاده‌های مستقیم به هم متصل شده‌اند، از الگوریتم دایجسترا می‌توان برای پیدا کردن کوتاه‌ترین راه بین یک شهر و همه شهرهای دیگر استفاده کرد. یکی از کاربردهای اصلی الگوریتم دایجسترا، پروتکل‌های مسیریابی شبکه است که از جمله آن‌ها می‌توان به IS-IS (سیستم میانی به سیستم میانی | Intermediate System to Intermediate System) و «ابتدا کوتاه‌ترین مسیر باز» (Open Shortest Path First | OSPF) اشاره کرد.

از الگوریتم دایجسترا، به عنوان یک زیر روال نیز در برخی از دیگر الگوریتم‌ها مانند «الگوریتم جانسون» (Johnson’s Algorithm) استفاده می‌شود. الگوریتم دایجسترا از برچسب‌هایی استفاده می‌کند که اعداد صحیح یا حقیقی مثبت هستند. جالب توجه است که الگوریتم دایجسترا می‌تواند برای استفاده از برچسب‌های تعریف شده به هر شکلی، تعمیم پیدا کند. چنین تعمیمی، «تعمیم الگوریتم کوتاه‌ترین مسیر دایجسترا» نامیده می‌شود.

الگوریتم دایجسترا (Dijkstra) برای یافتن کوتاه‌ترین مسیر

فرض می‌شود که یک گراف به همراه یک راس مبدا داده شده و هدف پیدا کردن کوتاه‌ترین مسیر به همه راس‌های موجود در گراف مذکور است. الگوریتم دایجسترا شباهت زیادی به «الگوریتم پریم» (Prim’s Algorithm) برای «درخت پوشای کمینه» (Minimum Spanning Tree) دارد. در الگوریتم دایجسترا نیز درخت کوتاه‌ترین مسیر با استفاده از مبدا داده شده به عنوان ریشه، ساخته می‌شود. در هر مرحله از الگوریتم، راسی پیدا می‌شود که در مجموعه دیگر (مجموعه راس‌های در نظر گرفته نشده) قرار دارد و دارای کمترین فاصله از ریشه است. در ادامه، گام‌های مورد استفاده در الگوریتم دایجسترا به منظور یافتن کوتاه‌ترین مسیر از یک راس مبدا مجرد به دیگر راس‌ها در گراف داده شده به صورت مشروح بیان شده‌اند.

1. ساخت مجموعه sptSet (مجموعه درخت کوتاه‌ترین مسیر | Shortest Path Tree Set) که به دنبال راس‌های قرار گرفته در درخت کوتاه‌ترین مسیر می‌گردد؛ یعنی، راسی که حداقل فاصله آن از مبدا محاسبه و نهایی شده است. به طور مقدماتی، این مجموعه خالی است.
2. تخصیص یک مقدار فاصله به همه راس‌ها در گراف ورودی. مقداردهی اولیه همه مقادیر فاصله‌ها به عنوان INFINITE. تخصیص مقدار فاصله صفر به راس مبدا که موجب می‌شود این راس در ابتدا انتخاب شود.
3. تا هنگامی که sptSet شامل همه راس‌ها نشده است، اقدامات زیر انجام می‌شود:
   • راس u انتخاب می‌شود که در sptSet نیست و دارای حداقل مقدار فاصله است.
   • u در sptSet قرار می‌گیرد.
   • مقدار فاصله از همه راس‌های مجاور u به روز رسانی می‌شود. برای به روز رسانی مقادیر فاصله، در همه راس‌های مجاور تکرار انجام می‌شود. برای هر راس مجاور v، اگر مجموع فاصله u (از کد منبع) و وزن یال u-v کمتر از مقدار فاصله v باشد، مقدار فاصله از v به روز رسانی می‌شود.

برای درک بهتر موضوع، مثال زیر مورد بررسی قرار خواهد گرفت.

مجموعه sptSet در ابتدا خالی است و فاصله تخصیص پیدا کرده به راس‌ها برابر با {0, INF, INF, INF, INF, INF, INF, INF} هستند که در آن INF نشان‌گر بی‌نهایت (Infinite) است. اکنون، باید راسی که دارای کم‌ترین مقدار فاصله است انتخاب شود. راس ۰ انتخاب می‌شود و در sptSet قرار می‌گیرد. بنابراین، sptSet به صورت {0} می‌شود. پس از قرار دادن ۰ در sptSet، مقدار فاصله‌ها از راس‌های مجاور آن به روز رسانی می‌شوند. راس‌های مجاور ۰، راس‌های 1 و ۷ هستند. مقدار فاصله برای 1 و ۷، برابر با 4 و ۸ است. زیرگراف زیر، راس‌ها و مقدار فاصله آن‌ها را نشان می‌دهد. در این گراف، تنها راس‌هایی با مقدار فاصله متناهی نشان داده شده‌اند. راس‌های موجود در SPT به رنگ سبز نمایش داده شده‌اند.

راسی که حداقل فاصله را از مبدا دارد و تاکنون انتخاب نشده است، یعنی در sptSET قرار ندارد، انتخاب می‌شود. راس 1 انتخاب و به sptSet اضافه می‌شود. بنابراین، اکنون sptSet به صورت {1 ,۰} خواهد بود. مقدار فاصله راس‌های مجاور 1 به روز رسانی می‌شود. مقدار فاصله از راس 2 برابر با 12 خواهد بود.

راسی با کمترین مقدار فاصله که در حال حاضر در SPT قرار ندارد باید انتخاب شود. راس ۷ انتخاب می‌شود. بنابراین، sptSet اکنون به صورت {۷ , 1 , ۰} خواهد بود. مقدار فاصله از راس‌های مجاور ۷ محاسبه می‌شود. مقدار فاصله از راس ۶ و ۸ متناهی است (به ترتیب، 1۵ و ۹).

راسی با حداقل مقدار فاصله که در SPT نیز قرار ندارد باید انتخاب شود. راس ۶ انتخاب می‌شود. بنابراین، sptSet اکنون برابر با {۶ ,۷ ,1 ,۰} است. مقدار فاصله‌ها از راس‌های مجاور ۶ باید به روز رسانی شود. مقدار فاصله برای راس‌های ۵ و ۸ به روز رسانی می‌شود.

مراحل بیان شده تا جایی تکرار می‌شوند که sptSet شامل همه راس‌های گراف داده شده نباشد. در نهایت، درخت کوتاه‌ترین مسیر (SPT) زیر حاصل می‌شود.

برای پیاده‌سازی الگوریتم بالا، از آرایه بولین []sptSet برای ارائه مجموعه‌ای از راس‌های قرار گرفته در SPT استفاده می‌شود. اگر مقدار [sptSet[v «درست» (True) باشد، راس v در SPT قرار می‌گیرد، در غیر این صورت، یعنی اگر [sptSet[v «غلط» (False) باشد، راس v در SPT قرار نمی‌گیرد. آرایه []dist برای ذخیره‌سازی کوتاه‌ترین مقدار فاصله از همه راس‌ها مورد استفاده قرار می‌گیرد.

کد الگوریتم دایجسترا در ++C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

// A C++ program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph    #include <stdio.h> #include <limits.h>    // Number of vertices in the graph #define V 9    // A utility function to find the vertex with minimum distance value, from // the set of vertices not yet included in shortest path tree int minDistance(int dist[], bool sptSet[]) {    // Initialize min value    int min = INT_MAX, min_index;       for (int v = 0; v < V; v++)      if (sptSet[v] == false && dist[v] <= min)          min = dist[v], min_index = v;       return min_index; }    // A utility function to print the constructed distance array int printSolution(int dist[], int n) {    printf("Vertex   Distance from Source\n");    for (int i = 0; i < V; i++)       printf("%d tt %d\n", i, dist[i]); }    // Function that implements Dijkstra's single source shortest path algorithm // for a graph represented using adjacency matrix representation void dijkstra(int graph[V][V], int src) {      int dist[V];     // The output array.  dist[i] will hold the shortest                       // distance from src to i         bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest                      // path tree or shortest distance from src to i is finalized         // Initialize all distances as INFINITE and stpSet[] as false      for (int i = 0; i < V; i++)         dist[i] = INT_MAX, sptSet[i] = false;         // Distance of source vertex from itself is always 0      dist[src] = 0;         // Find shortest path for all vertices      for (int count = 0; count < V-1; count++)      {        // Pick the minimum distance vertex from the set of vertices not        // yet processed. u is always equal to src in the first iteration.        int u = minDistance(dist, sptSet);           // Mark the picked vertex as processed        sptSet[u] = true;           // Update dist value of the adjacent vertices of the picked vertex.        for (int v = 0; v < V; v++)             // Update dist[v] only if is not in sptSet, there is an edge from            // u to v, and total weight of path from src to  v through u is            // smaller than current value of dist[v]          if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX                                          && dist[u]+graph[u][v] < dist[v])             dist[v] = dist[u] + graph[u][v];      }         // print the constructed distance array      printSolution(dist, V); }    // driver program to test above function int main() {    /* Let us create the example graph discussed above */    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},                       {4, 0, 8, 0, 0, 0, 0, 11, 0},                       {0, 8, 0, 7, 0, 4, 0, 0, 2},                       {0, 0, 7, 0, 9, 14, 0, 0, 0},                       {0, 0, 0, 9, 0, 10, 0, 0, 0},                       {0, 0, 4, 14, 10, 0, 2, 0, 0},                       {0, 0, 0, 0, 0, 2, 0, 1, 6},                       {8, 11, 0, 0, 0, 0, 1, 0, 7},                       {0, 0, 2, 0, 0, 0, 6, 7, 0}                      };        dijkstra(graph, 0);        return 0; }

کد الگوریتم دایجسترا در جاوا

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103

// A Java program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph import java.util.*; import java.lang.*; import java.io.*;    class ShortestPath {     // A utility function to find the vertex with minimum distance value,     // from the set of vertices not yet included in shortest path tree     static final int V=9;     int minDistance(int dist[], Boolean sptSet[])     {         // Initialize min value         int min = Integer.MAX_VALUE, min_index=-1;            for (int v = 0; v < V; v++)             if (sptSet[v] == false && dist[v] <= min)             {                 min = dist[v];                 min_index = v;             }            return min_index;     }        // A utility function to print the constructed distance array     void printSolution(int dist[], int n)     {         System.out.println("Vertex   Distance from Source");         for (int i = 0; i < V; i++)             System.out.println(i+" tt "+dist[i]);     }        // Funtion that implements Dijkstra's single source shortest path     // algorithm for a graph represented using adjacency matrix     // representation     void dijkstra(int graph[][], int src)     {         int dist[] = new int[V]; // The output array. dist[i] will hold                                  // the shortest distance from src to i            // sptSet[i] will true if vertex i is included in shortest         // path tree or shortest distance from src to i is finalized         Boolean sptSet[] = new Boolean[V];            // Initialize all distances as INFINITE and stpSet[] as false         for (int i = 0; i < V; i++)         {             dist[i] = Integer.MAX_VALUE;             sptSet[i] = false;         }            // Distance of source vertex from itself is always 0         dist[src] = 0;            // Find shortest path for all vertices         for (int count = 0; count < V-1; count++)         {             // Pick the minimum distance vertex from the set of vertices             // not yet processed. u is always equal to src in first             // iteration.             int u = minDistance(dist, sptSet);                // Mark the picked vertex as processed             sptSet[u] = true;                // Update dist value of the adjacent vertices of the             // picked vertex.             for (int v = 0; v < V; v++)                    // Update dist[v] only if is not in sptSet, there is an                 // edge from u to v, and total weight of path from src to                 // v through u is smaller than current value of dist[v]                 if (!sptSet[v] && graph[u][v]!=0 &&                         dist[u] != Integer.MAX_VALUE &&                         dist[u]+graph[u][v] < dist[v])                     dist[v] = dist[u] + graph[u][v];         }            // print the constructed distance array         printSolution(dist, V);     }        // Driver method     public static void main (String[] args)     {         /* Let us create the example graph discussed above */        int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},                                   {4, 0, 8, 0, 0, 0, 0, 11, 0},                                   {0, 8, 0, 7, 0, 4, 0, 0, 2},                                   {0, 0, 7, 0, 9, 14, 0, 0, 0},                                   {0, 0, 0, 9, 0, 10, 0, 0, 0},                                   {0, 0, 4, 14, 10, 0, 2, 0, 0},                                   {0, 0, 0, 0, 0, 2, 0, 1, 6},                                   {8, 11, 0, 0, 0, 0, 1, 0, 7},                                   {0, 0, 2, 0, 0, 0, 6, 7, 0}                                  };         ShortestPath t = new ShortestPath();         t.dijkstra(graph, 0);     } } //This code is contributed by Aakash Hasija

کد الگوریتم دایجسترا در #C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121

// A C# program for Dijkstra's single   // source shortest path algorithm. // The program is for adjacency matrix // representation of the graph using System;      class GFG { // A utility function to find the   // vertex with minimum distance // value, from the set of vertices // not yet included in shortest   // path tree static int V = 9; int minDistance(int[] dist,                   bool[] sptSet) {     // Initialize min value     int min = int.MaxValue, min_index = -1;        for (int v = 0; v < V; v++)         if (sptSet[v] == false &&                 dist[v] <= min)         {             min = dist[v];             min_index = v;         }        return min_index; }    // A utility function to print // the constructed distance array void printSolution(int[] dist, int n) {     Console.Write("Vertex     Distance " +                           "from Source\n");     for (int i = 0; i < V; i++)         Console.Write(i + " \t\t " +                       dist[i] + "\n"); }    // Funtion that implements Dijkstra's   // single source shortest path algorithm // for a graph represented using adjacency   // matrix representation void dijkstra(int[,] graph, int src) {     int[] dist = new int[V]; // The output array. dist[i]                              // will hold the shortest                                // distance from src to i        // sptSet[i] will true if vertex     // i is included in shortest path       // tree or shortest distance from       // src to i is finalized     bool[] sptSet = new bool[V];        // Initialize all distances as       // INFINITE and stpSet[] as false     for (int i = 0; i < V; i++)     {         dist[i] = int.MaxValue;         sptSet[i] = false;     }        // Distance of source vertex     // from itself is always 0     dist[src] = 0;        // Find shortest path for all vertices     for (int count = 0; count < V - 1; count++)     {         // Pick the minimum distance vertex           // from the set of vertices not yet           // processed. u is always equal to           // src in first iteration.         int u = minDistance(dist, sptSet);            // Mark the picked vertex as processed         sptSet[u] = true;            // Update dist value of the adjacent           // vertices of the picked vertex.         for (int v = 0; v < V; v++)                // Update dist[v] only if is not in               // sptSet, there is an edge from u               // to v, and total weight of path               // from src to v through u is smaller               // than current value of dist[v]             if (!sptSet[v] && graph[u, v] != 0 &&                        dist[u] != int.MaxValue &&                  dist[u] + graph[u, v] < dist[v])                 dist[v] = dist[u] + graph[u, v];     }        // print the constructed distance array     printSolution(dist, V); }    // Driver Code public static void Main () { /* Let us create the example   graph discussed above */ int[,] graph = new int[,]{{0, 4, 0, 0, 0, 0, 0, 8, 0},                           {4, 0, 8, 0, 0, 0, 0, 11, 0},                           {0, 8, 0, 7, 0, 4, 0, 0, 2},                           {0, 0, 7, 0, 9, 14, 0, 0, 0},                           {0, 0, 0, 9, 0, 10, 0, 0, 0},                           {0, 0, 4, 14, 10, 0, 2, 0, 0},                           {0, 0, 0, 0, 0, 2, 0, 1, 6},                           {8, 11, 0, 0, 0, 0, 1, 0, 7},                           {0, 0, 2, 0, 0, 0, 6, 7, 0}};     GFG t = new GFG();     t.dijkstra(graph, 0); } }    // This code is contributed by ChitraNayal

کد الگوریتم دایجسترا در پایتون

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

# Python program for Dijkstra's single   # source shortest path algorithm. The program is   # for adjacency matrix representation of the graph    # Library for INT_MAX import sys    class Graph():        def __init__(self, vertices):         self.V = vertices         self.graph = [[0 for column in range(vertices)]                         for row in range(vertices)]        def printSolution(self, dist):         print "Vertex tDistance from Source"         for node in range(self.V):             print node,"t",dist[node]        # A utility function to find the vertex with       # minimum distance value, from the set of vertices       # not yet included in shortest path tree     def minDistance(self, dist, sptSet):            # Initilaize minimum distance for next node         min = sys.maxint            # Search not nearest vertex not in the           # shortest path tree         for v in range(self.V):             if dist[v] < min and sptSet[v] == False:                 min = dist[v]                 min_index = v            return min_index        # Funtion that implements Dijkstra's single source       # shortest path algorithm for a graph represented       # using adjacency matrix representation     def dijkstra(self, src):            dist = [sys.maxint] * self.V         dist[src] = 0         sptSet = [False] * self.V            for cout in range(self.V):                # Pick the minimum distance vertex from               # the set of vertices not yet processed.               # u is always equal to src in first iteration             u = self.minDistance(dist, sptSet)                # Put the minimum distance vertex in the               # shotest path tree             sptSet[u] = True                # Update dist value of the adjacent vertices               # of the picked vertex only if the current               # distance is greater than new distance and             # the vertex in not in the shotest path tree             for v in range(self.V):                 if self.graph[u][v] > 0 and sptSet[v] == False and                    dist[v] > dist[u] + self.graph[u][v]:                         dist[v] = dist[u] + self.graph[u][v]            self.printSolution(dist)    # Driver program g  = Graph(9) g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],            [4, 0, 8, 0, 0, 0, 0, 11, 0],            [0, 8, 0, 7, 0, 4, 0, 0, 2],            [0, 0, 7, 0, 9, 14, 0, 0, 0],            [0, 0, 0, 9, 0, 10, 0, 0, 0],            [0, 0, 4, 14, 10, 0, 2, 0, 0],            [0, 0, 0, 0, 0, 2, 0, 1, 6],            [8, 11, 0, 0, 0, 0, 1, 0, 7],            [0, 0, 2, 0, 0, 0, 6, 7, 0]           ];    g.dijkstra(0);    # This code is contributed by Divyanshu Mehta

منبع: فرادرس

مرتب سازی درجی (Insertion Sort) — به زبان ساده

«مرتب سازی درجی» (Insertion Sort) یک الگوریتم مرتب‌سازی ساده است که روش عملکرد آن مشابه روشی است که افراد کارت‌های بازی را در دست خود مرتب می‌کنند. در این مطلب، به الگوریتم مرتب سازی درجی پرداخته شده و سپس، پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون، شامل «سی‌پلاس‌پلاس» (++C ،(C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است.

الگوریتم مرتب سازی درجی

//مرتب‌سازی آرایه []arr با سایز n

1. (insertionSort(arr, n
2. از  i = 1 تا n-1 حلقه بزن
   • عنصر [arr[i را انتخاب کن و آن را در توالی مرتب شده [arr[0…i-1 درج کن

مثال اول از مرتب سازی درجی

مثال دوم از مرتب سازی درجی

12, 11, 13, 5, 6

از i = 1 (دومین عنصر از آرایه) تا 4 (آخرین عنصر از آرایه) حلقه بزن.

i = 1. به دلیل آنکه 11 از 12 کوچک‌تر است، 12 را جا به جا کن و 11 را پیش از 12 درج کن.

i = 2. عدد 13 در جای خود باقی می‌ماند، زیرا همه عناصر [A[0..I-1 کوچک‌تر از 13 هستند.

11, 12, 13, 5, 6

i = 3. عدد ۵ به آغاز منتقل می‌شود و همه عناصر دیگر، از 11 تا 13 یک خانه از خانه کنونی خود رو  به جلو، جا به جا می‌شوند.

5, 11, 12, 13, 6

i = 4. عدد ۶ به خانه پس از ۵ منتقل می‌شود و عناصر از 11 تا 13 به اندازه یک خانه از خانه کنونی‌شان، به جلو می‌روند.

5, 6, 11, 12, 13

کد مرتب سازی درجی در ++C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

// C++ program for insertion sort   #include <bits/stdc++.h> using namespace std;    /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n)   {       int i, key, j;       for (i = 1; i < n; i++)     {           key = arr[i];           j = i - 1;              /* Move elements of arr[0..i-1], that are           greater than key, to one position ahead           of their current position */         while (j >= 0 && arr[j] > key)         {               arr[j + 1] = arr[j];               j = j - 1;           }           arr[j + 1] = key;       }   }      // A utility function to print an array of size n   void printArray(int arr[], int n)   {       int i;       for (i = 0; i < n; i++)           cout << arr[i] << " ";       cout << endl; }      /* Driver code */ int main()   {       int arr[] = { 12, 11, 13, 5, 6 };       int n = sizeof(arr) / sizeof(arr[0]);          insertionSort(arr, n);       printArray(arr, n);          return 0;   }      // This is code is contributed by rathbhupendra

کد مرتب سازی درجی در C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

// C program for insertion sort #include <math.h> #include <stdio.h>    /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) {     int i, key, j;     for (i = 1; i < n; i++) {         key = arr[i];         j = i - 1;            /* Move elements of arr[0..i-1], that are           greater than key, to one position ahead           of their current position */         while (j >= 0 && arr[j] > key) {             arr[j + 1] = arr[j];             j = j - 1;         }         arr[j + 1] = key;     } }    // A utility function to print an array of size n void printArray(int arr[], int n) {     int i;     for (i = 0; i < n; i++)         printf("%d ", arr[i]);     printf("\n"); }    /* Driver program to test insertion sort */ int main() {     int arr[] = { 12, 11, 13, 5, 6 };     int n = sizeof(arr) / sizeof(arr[0]);        insertionSort(arr, n);     printArray(arr, n);        return 0; }

کد مرتب سازی درجی در جاوا

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

// Java program for implementation of Insertion Sort class InsertionSort {     /*Function to sort array using insertion sort*/     void sort(int arr[])     {         int n = arr.length;         for (int i = 1; i < n; ++i) {             int key = arr[i];             int j = i - 1;                /* Move elements of arr[0..i-1], that are                greater than key, to one position ahead                of their current position */             while (j >= 0 && arr[j] > key) {                 arr[j + 1] = arr[j];                 j = j - 1;             }             arr[j + 1] = key;         }     }        /* A utility function to print array of size n*/     static void printArray(int arr[])     {         int n = arr.length;         for (int i = 0; i < n; ++i)             System.out.print(arr[i] + " ");            System.out.println();     }        // Driver method     public static void main(String args[])     {         int arr[] = { 12, 11, 13, 5, 6 };            InsertionSort ob = new InsertionSort();         ob.sort(arr);            printArray(arr);     } } /* This code is contributed by Rajat Mishra. */

کد مرتب سازی درجی در پایتون

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

# Python program for implementation of Insertion Sort    # Function to do insertion sort def insertionSort(arr):        # Traverse through 1 to len(arr)     for i in range(1, len(arr)):            key = arr[i]            # Move elements of arr[0..i-1], that are         # greater than key, to one position ahead         # of their current position         j = i-1         while j >= 0 and key < arr[j] :                 arr[j + 1] = arr[j]                 j -= 1         arr[j + 1] = key       # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)):     print ("% d" % arr[i])    # This code is contributed by Mohit Kumra

کد مرتب سازی درجی در #C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

// C# program for implementation of Insertion Sort using System;    class InsertionSort {        // Function to sort array     // using insertion sort     void sort(int[] arr)     {         int n = arr.Length;         for (int i = 1; i < n; ++i) {             int key = arr[i];             int j = i - 1;                // Move elements of arr[0..i-1],             // that are greater than key,             // to one position ahead of             // their current position             while (j >= 0 && arr[j] > key) {                 arr[j + 1] = arr[j];                 j = j - 1;             }             arr[j + 1] = key;         }     }        // A utility function to print     // array of size n     static void printArray(int[] arr)     {         int n = arr.Length;         for (int i = 0; i < n; ++i)             Console.Write(arr[i] + " ");            Console.Write("\n");     }        // Driver Code     public static void Main()     {         int[] arr = { 12, 11, 13, 5, 6 };         InsertionSort ob = new InsertionSort();         ob.sort(arr);         printArray(arr);     } }    // This code is contributed by ChitraNayal.

کد مرتب سازی درجی در PHP

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

<?php   // PHP program for insertion sort    // Function to sort an array // using insertion sort function insertionSort(&$arr, $n) {     for ($i = 1; $i < $n; $i++)     {         $key = $arr[$i];         $j = $i-1;                // Move elements of arr[0..i-1],         // that are    greater than key, to           // one position ahead of their           // current position         while ($j >= 0 && $arr[$j] > $key)         {             $arr[$j + 1] = $arr[$j];             $j = $j - 1;         }                    $arr[$j + 1] = $key;     } }    // A utility function to // print an array of size n function printArray(&$arr, $n) {     for ($i = 0; $i < $n; $i++)         echo $arr[$i]." ";     echo "\n"; }    // Driver Code $arr = array(12, 11, 13, 5, 6); $n = sizeof($arr); insertionSort($arr, $n); printArray($arr, $n);    // This code is contributed by ChitraNayal. ?>

خروجی

خروجی قطعه کدهای بالا، برای آرایه [6, 5, 13, 11, 12] به صورت زیر است.

5 6 11 12 13

پیچیدگی زمانی: (O(n*2

فضای کمکی: (O(1

موارد مرزی (Boundary Cases): مرتب سازی درجی، در صورتی که عناصر دارای ترتیب برعکس باشند، بیشترین زمان اجرا را می‌برد. همچنین، در صورتی که عناصر مرتب شده باشند، کمترین زمان اجرا (از درجه n) را خواهد داشت.

مرتب‌سازی درجا: بله

پایدار: بله

آنلاین: بله

کاربردها: مرتب‌سازی درجی، هنگامی مورد استفاده قرار می‌گیرد که تعداد عناصر کم باشد. همچنین، هنگامی که آرایه ورودی تقریبا مرتب شده باشد و تنها چند عنصر در یک آرایه بزرگ در جای نادرست قرار داشته باشند، مرتب سازی درجی گزینه مناسبی خواهد بود.

مرتب سازی درجی دودویی

هنگامی که از جستجوی دودویی برای کاهش تعداد مقایسه‌ها در مرتب سازی درجی استفاده می‌شود، به آن مرتب سازی درجی دودویی گفته می‌شود. مرتب سازی درجی دودویی از جستجوی دودویی به منظور پیدا کردن موقعیت مناسب برای درج عناصر انتخاب شده در هر تکرار استفاده می‌شود. در درج نرمال، مرتب‌سازی در بدترین حالت (O(i به طور می‌انجامد (در iاُمین تکرار). این مقدار را می‌توان با استفاده از جستجوی دودویی به (O(logi کاهش داد. به طور کلی،‌ الگوریتم همچنان دارای زمان اجرای (O(n2 است، زیرا مجموعه‌ای از جا به جایی‌ها برای هر درج مورد نیاز است.

پیاده‌سازی مرتب سازی درجی برای لیست‌های پیوندی

در ادامه، پیاده‌سازی ساده‌ای از مرتب سازی درجی برای لیست‌های پیوندی ارائه شده است.

1. یک لیست خالی «مرتب شده» (Sorted) (یا «نتیجه» (Result)) بساز.
2. لیست داده شده را معکوس کن و اقدامات زیر را برای هر گره انجام بده:
   • گره کنونی را به صورت مرتب شده، در لیست «مرتب شده» (Sorted) یا «نتیجه» (Result) قرار بده.
3. سر لیست پیوندی داده شده را به سر لیست مرتب شده (یا نتیجه) تغییر بده.

کد مرتب سازی درجی در لیست‌های پیوندی در ++C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

/* C program for insertion sort on a linked list */ #include<stdio.h> #include<stdlib.h>    /* Link list node */ struct Node {     int data;     struct Node* next; };    // Function to insert a given node in a sorted linked list void sortedInsert(struct Node**, struct Node*);    // function to sort a singly linked list using insertion sort void insertionSort(struct Node **head_ref) {     // Initialize sorted linked list     struct Node *sorted = NULL;        // Traverse the given linked list and insert every     // node to sorted     struct Node *current = *head_ref;     while (current != NULL)     {         // Store next for next iteration         struct Node *next = current->next;            // insert current in sorted linked list         sortedInsert(&sorted, current);            // Update current         current = next;     }        // Update head_ref to point to sorted linked list     *head_ref = sorted; }    /* function to insert a new_node in a list. Note that this   function expects a pointer to head_ref as this can modify the   head of the input linked list (similar to push())*/ void sortedInsert(struct Node** head_ref, struct Node* new_node) {     struct Node* current;     /* Special case for the head end */     if (*head_ref == NULL || (*head_ref)->data >= new_node->data)     {         new_node->next = *head_ref;         *head_ref = new_node;     }     else     {         /* Locate the node before the point of insertion */         current = *head_ref;         while (current->next!=NULL &&                current->next->data < new_node->data)         {             current = current->next;         }         new_node->next = current->next;         current->next = new_node;     } }    /* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */    /* Function to print linked list */ void printList(struct Node *head) {     struct Node *temp = head;     while(temp != NULL)     {         printf("%d  ", temp->data);         temp = temp->next;     } }    /* A utility function to insert a node at the beginning of linked list */ void push(struct Node** head_ref, int new_data) {     /* allocate node */     struct Node* new_node = new Node;        /* put in the data  */     new_node->data  = new_data;        /* link the old list off the new node */     new_node->next = (*head_ref);        /* move the head to point to the new node */     (*head_ref)    = new_node; }       // Driver program to test above functions int main() {     struct Node *a = NULL;     push(&a, 5);     push(&a, 20);     push(&a, 4);     push(&a, 3);     push(&a, 30);        printf("Linked List before sorting \n");     printList(a);        insertionSort(&a);        printf("\nLinked List after sorting \n");     printList(a);        return 0; }

کد مرتب سازی درجی در لیست‌های پیوندی در جاوا

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105

// Java program to sort link list // using insertion sort    public class LinkedlistIS   {     node head;     node sorted;        class node       {         int val;         node next;            public node(int val)           {             this.val = val;         }     }        void push(int val)       {         /* allocate node */         node newnode = new node(val);         /* link the old list off the new node */         newnode.next = head;         /* move the head to point to the new node */         head = newnode;     }        // function to sort a singly linked list using insertion sort     void insertionSort(node headref)       {         // Initialize sorted linked list         sorted = null;         node current = headref;         // Traverse the given linked list and insert every         // node to sorted         while (current != null)           {             // Store next for next iteration             node next = current.next;             // insert current in sorted linked list             sortedInsert(current);             // Update current             current = next;         }         // Update head_ref to point to sorted linked list         head = sorted;     }        /*      * function to insert a new_node in a list. Note that        * this function expects a pointer to head_ref as this      * can modify the head of the input linked list        * (similar to push())      */     void sortedInsert(node newnode)       {         /* Special case for the head end */         if (sorted == null || sorted.val >= newnode.val)           {             newnode.next = sorted;             sorted = newnode;         }         else         {             node current = sorted;             /* Locate the node before the point of insertion */             while (current.next != null && current.next.val < newnode.val)               {                 current = current.next;             }             newnode.next = current.next;             current.next = newnode;         }     }        /* Function to print linked list */     void printlist(node head)       {         while (head != null)           {             System.out.print(head.val + " ");             head = head.next;         }     }            // Driver program to test above functions     public static void main(String[] args)       {         LinkedlistIS list = new LinkedlistIS();         list.push(5);         list.push(20);         list.push(4);         list.push(3);         list.push(30);         System.out.println("Linked List before Sorting..");         list.printlist(list.head);         list.insertionSort(list.head);         System.out.println("\nLinkedList After sorting");         list.printlist(list.head);     } }    // This code is contributed by Rishabh Mahrsee

کد مرتب سازی درجی در لیست‌های پیوندی در #C

منبع: فرادرس

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116

// C# program to sort link list // using insertion sort using System;    public class LinkedlistIS   {     public node head;     public node sorted;        public class node       {         public int val;         public node next;            public node(int val)           {             this.val = val;         }     }        void push(int val)       {         /* allocate node */         node newnode = new node(val);                    /* link the old list off the new node */         newnode.next = head;                    /* move the head to point to the new node */         head = newnode;     }        // function to sort a singly       // linked list using insertion sort     void insertionSort(node headref)       {         // Initialize sorted linked list         sorted = null;         node current = headref;                    // Traverse the given           // linked list and insert every         // node to sorted         while (current != null)           {             // Store next for next iteration             node next = current.next;                            // insert current in sorted linked list             sortedInsert(current);                            // Update current             current = next;         }                    // Update head_ref to point to sorted linked list         head = sorted;     }        /*     * function to insert a new_node in a list. Note that       * this function expects a pointer to head_ref as this     * can modify the head of the input linked list       * (similar to push())     */     void sortedInsert(node newnode)       {         /* Special case for the head end */         if (sorted == null || sorted.val >= newnode.val)           {             newnode.next = sorted;             sorted = newnode;         }         else         {             node current = sorted;                            /* Locate the node before the point of insertion */             while (current.next != null &&                       current.next.val < newnode.val)               {                 current = current.next;             }             newnode.next = current.next;             current.next = newnode;         }     }        /* Function to print linked list */     void printlist(node head)       {         while (head != null)           {             Console.Write(head.val + " ");             head = head.next;         }     }            // Driver code     public static void Main(String[] args)       {         LinkedlistIS list = new LinkedlistIS();         list.push(5);         list.push(20);         list.push(4);         list.push(3);         list.push(30);         Console.WriteLine("Linked List before Sorting..");         list.printlist(list.head);         list.insertionSort(list.head);         Console.WriteLine("\nLinkedList After sorting");         list.printlist(list.head);     } }    // This code contributed by Rajput-Ji