خانه / fd / الگوریتم های مرتب سازی در سوئیفت (Swift) — به زبان ساده

الگوریتم های مرتب سازی در سوئیفت (Swift) — به زبان ساده

مرتب‌سازی یکی از مفاهیم ضروری برای مدیریت داده‌ها محسوب می‌شود. داده‌های مرتب شده امکان اجرای مؤثرتر الگوریتم‌ها را فراهم می‌سازند. هدف ما از مرتب‌سازی این است که از یک وضعیت بی‌نظمی به وضعیت منظم برسیم. این کار از طرق چیدمان داده‌ها با یک توالی منطقی به دست می‌آید، به طوری که می‌توانیم بفهمیم اطلاعات را از کجا بیابیم. این توالی‌ها را به راحتی می‌توان با استفاده از نوع داده صحیح (Integer) به دست آورد؛ اما در این مسیر می‌توان از کاراکترها (یعنی حروف الفبا) و دیگر مجموعه‌ها مانند اعداد باینری، هگزادسیمال و مشابه نیز بهره جست. در این نوشته با الگوریتم های مرتب سازی در سوئیفت آشنا خواهیم شد. در مثال‌های زیر، از تکنیک‌های مختلفی برای مرتب‌سازی یک آرایه استفاده می‌کنیم.

//array of unsorted integers let numberList : Array<Int> = [8, 2, 10, 9, 7, 5]

برای یک لیست کوتاه، بصری‌سازی مسئله، امری ساده است. برای چیدمان مجموعه به صورت یک دنباله منظم می‌توانیم یک «ناوردا» (invariant) پیاده‌سازی کنیم. ناورداها فرضیاتی را نمایش می‌دهند که در تمام طول اجرا بدون تغییر می‌مانند. برای این که ببینید این وضعیت چگونه کار می‌کند، الگوریتم مرتب‌سازی ادغامی را ملاحظه کنید.

مرتب‌سازی ادغامی

«مرتب‌سازی ادغامی» (INSERTION SORT) یکی از ابتدایی‌ترین الگوریتم‌ها در علوم رایانه به حساب می‌آید. این الگوریتم عناصر را از طریق تکرار یک چرخه روی یک مجموعه و تعیین موقعیت عناصر بر اساس ارزششان رتبه‌بندی می‌کند. این مجموعه به دو نیمه مرتب و نامرتب تقسیم می‌شود و این کار تا زمانی که همه عناصر مرتب‌سازی شوند تداوم می‌یابد:

extension Array where Element: Comparable {    func insertionSort() -> Array<Element> {                  //check for trivial case         guard self.count > 1 else {             return self         }                  //mutated copy                 var output: Array<Element> = self                  for primaryindex in 0..<output.count {                          let key = output[primaryindex]             var secondaryindex = primaryindex                          while secondaryindex > -1 {                 if key < output[secondaryindex] {                                          //move to correct position                     output.remove(at: secondaryindex + 1)                     output.insert(key, at: secondaryindex)                 }                                  secondaryindex -= 1             }                     }                  return output             }   } //execute sort let results: Array<Int> = numberList.insertionSort()

مرتب‌سازی حبابی

«مرتب‌سازی حبابی» (BUBBLE SORT) یک تکنیک مرتب‌سازی رایج دیگر است. این تکنیک نیز مانند مرتب‌سازی ادغامی حاصل ترکیب یک سری مراحل با یک ناوردا است. این تابع با ارزیابی جفت مقدارها عمل می‌کند. زمانی که مقایسه صورت بگیرد، موقعیت بزرگ‌ترین مقدار با کوچک‌ترین مقدار تعویض می‌شود. هنگامی که این کار به دفعات کافی صورت بگیرد، تأثیر این «حباب سازی» خود را نشان می‌دهد و در نهایت همه عناصر در لیست مرتب‌سازی می‌شوند:

extension Array where Element: Comparable { func bubbleSort() -> Array<Element> {                          //check for trivial case         guard self.count > 1 else {             return self         }                          //mutated copy         var output: Array<Element> = self                          for primaryIndex in 0..<self.count {                                     let passes = (output.count - 1) - primaryIndex                                      //"half-open" range operator             for secondaryIndex in 0..<passes {                                 let key = output[secondaryIndex]                                                                  //compare / swap positions                 if (key > output[secondaryIndex + 1]) {                   output.swapAt(secondaryIndex, secondaryIndex + 1)                 }             }         }                          return output             } } //execute sort let results: Array<Int> = numberList.bubbleSort()

مرتب‌سازی انتخابی

«مرتب‌سازی انتخابی» (SELECTION SORT) نیز همانند مرتب‌سازی حبابی به رتبه‌بندی عناصر از طریق تعریف چرخه‌ای روی یک مجموعه و تعویض مکان عناصر بر اساس مقدارشان عمل می‌کند. مجموعه به نیمه‌های مرتب و نامرتب تقسیم می‌شود و این فرایند تا زمانی که همه عناصر مرتب‌سازی شوند ادامه می‌یابد:

extension Array where Element: Comparable { func selectionSort() -> Array<Element> {                       //check for trivial case         guard self.count > 1 else {             return self         }                          //mutated copy         var output: Array<Element> = self                          for primaryindex in 0..<output.count {                                      var minimum = primaryindex             var secondaryindex = primaryindex + 1                                      while secondaryindex < output.count {                     //store lowest value as minimum                 if output[minimum] > output[secondaryindex] {                     minimum = secondaryindex                 }                                 secondaryindex += 1             }                                       //swap minimum value with array iteration             if primaryindex != minimum {             output.swapAt(primaryindex, minimum)             }                     }                          return output             } } //execute sort let results: Array<Int> = numberList.selectionSort()

علاوه بر روش‌های مرتب‌سازی درجی، انتخابی و حبابی، الگوریتم‌های مرتب‌سازی زیاد دیگری نیز وجود دارند. همان طور که می‌دانید ساختمان‌های داده درخت جستجوی دودویی و «هیپ» (Heap) نیز به فرایند مرتب‌سازی عناصر کمک می‌کنند؛ اما این کار را به عنوان بخشی از فرایند درج انجام می‌دهند.

اگر این نوشته برای شما مفید بوده است، آموزش‌های زیر به شما پیشنهاد می‌شوند:

  • مجموعه آموزش‌ های برنامه‌‌ نویسی
  • آموزش برنامه نویسی Swift (سوئیفت) برای برنامه نویسی iOS
  • مجموعه آموزش‌ های مهندسی نرم افزار
  • شروع برنامه‌نویسی با زبان سوئیفت در اوبونتو
  • آموزش ‌آرایه در برنامه نویسی Swift (سوئیفت)
  • آرایه‌ ها در زبان برنامه نویسی سوئیفت (Swift) — به زبان ساده
  • آموزش برنامه نویسی سوئیفت (Swift): متغیر، ثابت و انواع داده

==

بلی خیر

نوشته الگوریتم های مرتب سازی در سوئیفت (Swift) — به زبان ساده اولین بار در وبلاگ فرادرس. پدیدار شد.

درباره ی admin

مطلب پیشنهادی

تعمیر یک هارد درایو خراب و بازیابی داده های آن— به زبان ساده

گفته شده که وقتی انسان می‌میرد، کل زندگیش در یک لحظه از جلوی چشمانش عبور می‌کند. البته همین اتفاق در صورتی که مطلع شوید با یک هارد درایو خراب مواجه شده‌اید نیز ممکن است برای شما می‌افتد! در این لحظه یاد هزاران عکس می‌افتید که از آن‌ها پشتیبان‌گیری نکرده‌اید و احتمالاً به فکر بازیابی آن‌ها بیفتید. در این مقاله روش این کار را توضیح می‌دهیم. اگر هارددیسک شما از کار بیفتد، با استفاده از این راهنما می‌توانید داده‌های خود را تعمیر و بازیابی کنید. داستان یک فرد نادم در این بخش داستانی را برای شما تعریف می‌کنیم که ممکن است برای هر کدام از ما اتفاق بیفتد. قهرمان داستان ما چند سال پیش با یک خرابی هارددیسک مواجه شده است. ابتدای قضیه از عملکرد عجیب لپ‌تاپ آغاز می‌شود. زمانی که این عملکرد عجیب پس از ریبوت لپ‌تاپ همچنان تداوم می‌یابد وی متوجه می‌شود که مشکل چیزی بیش از یک پر شدن ظرفیت RAM است. درنتیجه بی‌درنگ اقدام به پشتیبانی گیری از فایل‌های جدید خود می‌کند. نیم ساعت بعد هارددیسک با سر و صدا از کار می‌افتد و لپ‌تاپ دیگر بوت نمی‌شود. وی قبلاً نسخه‌های پشتیبانی از فایل‌های خود تهیه کرده بود؛ اما ش..

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *