الگوریتم مرتب سازی درجی (Insertion Sort)

insertion sort algorithm 7313 تصویر

الگوریتم مرتب سازی درجی (Insertion Sort)

الگوریتم مرتب سازی درجی (Insertion Sort) یکی الگوریتم های  برای مرتب سازی یک آرایه نامرتب است. این الگوریتم برای مرتب سازی مجموعه های بزرگ کارایی خیلی کمتری در مقایسه با الگوریتم هایی مثل Merge Sort، Heap Sort و Quick Sort دارد. روش کار به این صورت است که عناصر آرایه را یکی یکی برداشته و در جای مناسب در بخش مرتب شده، قرار می دهد. در زیر می توانید تصویری از نحوه عملکرد الگوریتم Insertion Sort را مشاهه کنید.

insertion sort algorithm 7313 1 تصویر

مثال

فرض کنید یک آرایه با مقادیر زیر داریم:

در این مثال i از ۱ (یعنی عنصر دوم) تا ۴ (یعنی عنصر آخر) ادامه می یابد.

i = 1، چون ۱۲ از ۱۱ بزرگتر است، ۱۱ به قبل از ۱۲ انتقال می یابد.

i = 2، ۱۳ در جای خودش باقی می ماند. چون عناصر باقی مانده کوچکتر از آن هستند.

i = 3، مقدار ۵ به ابتدای آرایه انتقال می یابد و مقادیر ۱۱ و ۱۳ یک واحد به جلو انتقال می یابند.

i = 4، مقدار ۶ به موقعیت بعد از ۵ انتقال می یابد و مقادیر ۱۱ و ۱۳ یک واحد به جلو انتقال می یابند.

پیاده سازی این الگوریتم با استفاده از زبان C++:

امتحان کنید

خروجی:

نکات

  • پیچیدگی زمانی برابر است با O(n*2).
  • فضای موقت برابر است با O(1).
  • این الگوریتم زمانی که آرایه به صورت برعکس مرتب شده باشد، بیشترین زمان را می گیرد و زمانی که به صورت مرتب شده باشد، کمترین زمان را می گیرد.
  • این الگوریتم برای مجموعه هایی که تعداد عناصر کمی دارند و همچنین مجموعه هایی که تقریبا مرتب شده هستند، کارایی خوبی دارد.
ثبت نظر
ریفریش کنید!
نظرات کاربران (۲ مورد)
  1. تصویر آواتار کاربر 0
    Ali پنج شنبه , ۹ آبان

    سلام اعداد تصادفی تولید کند و زمان مرتب سازی را نشان دهد مثلا ۱۰۰هزاو عدد رو تصادفی تولید کند و بعد مرتب کند زمان رو به ما نشون بده