مرتب سازی رشته ای ( مرتب سازی Strand ) یکی از الگوریتم مرتب سازی ادغامی می باشد. عملیاتی در استخراج مکرر فهرست های فرعی مرتب شده خارج از آن فهرستی که باید مرتب شود و ادغام آن ها با یکدیگر که خروجی یک آرایه نتیجه می باشد. در هر تکرار از بین فهرست نامرتب شده، یک مجموعه اعضاء استخراج می شود که قبلاً مرتب بودند و ادغام آن مجموعه ها با هم. [ ۱]
نام این الگوریتم از "رشته یا Strand" که از داده های مرتب شده در فهرست نامرتب، که در یک زمان حذف می شود می آید؛ و این مرتب سازی مقایسهٔ که علت استفاده از مقایسه های که هنگام حذف رشته ها و زمانی که آن ها با ادغام شدنشان درون آرایه، مرتب شده می باشد.
الگوریتم مرتب سازی رشته ای ( Strand Sort ) روش مناسبی برای داده های که در یک فهرست پیوندی ذخیره می شوند با توجه به اضافه و حذف مکرر داده های که داریم و در دیگر موارد استفاده ساختمان داده ای مانند یک آرایه، تا حد زیادی زمان اجرا و پیچیدگی الگوریتم به علت طولانی بودن اضافه ها و حذف ها، افزایش می یابد. الگوریتم مرتب سازی رشته ای روش مناسبی برای داده ای است که از قبل حجم زیادی از داده ها مرتب شده باشند، زیرا که داده ها را می توان در یک رشته واحد برداشته شوند.
این الگوریتم در بدترین حالت ( یک فهرست که به ترتیب معکوس مرتب سازی شده باشد ) از مرتبهٔ Θ ( n۲ ) است.
این الگوریتم در حالت متوسط از مرتبهٔ Θ ( n۲ ) است.
بهترین حالت این است که فهرست قبلاً مرتب شده باشد که در این حالت الگوریتم از مرتبه O ( n ) است.
• یکبار فهرست نامرتب تجزیه می شود، عددهای صعودی ( مرتب شده ) گرفته می شوند.
• فهرست فرعی ( مرتب شده ) را در صورتی که بار اول تکرارش باشد درون فهرست خالی ذخیره می کند.
• دوباره تجزیه فهرست نامرتب و گرفتن عددهای نسبتا مرتب شده.
• از آنجایی که فهرست مرتب سازی شده در حال حاضر پره شده، ادغام فهرست های فرعی در فهرست مرتب شده انجام می شود.
• تکرار گام های ( ۳ - ۴ ) تا زمانی که هر دو فهرست نا مرتب و فهرست فرعی خالی شوند.
در زیر شبه کد پیاده سازی الگوریتم رشته می باشد.
procedure strandSort ( A : list of sortable items ) defined as: while length ( A ) > ۰ clear sublist sublist := A remove A for each i in ۰ to length ( A ) - ۱ do: if A > sublist then append A to sublist remove A end if end for merge sublist into results end while return results end procedure
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفنام این الگوریتم از "رشته یا Strand" که از داده های مرتب شده در فهرست نامرتب، که در یک زمان حذف می شود می آید؛ و این مرتب سازی مقایسهٔ که علت استفاده از مقایسه های که هنگام حذف رشته ها و زمانی که آن ها با ادغام شدنشان درون آرایه، مرتب شده می باشد.
الگوریتم مرتب سازی رشته ای ( Strand Sort ) روش مناسبی برای داده های که در یک فهرست پیوندی ذخیره می شوند با توجه به اضافه و حذف مکرر داده های که داریم و در دیگر موارد استفاده ساختمان داده ای مانند یک آرایه، تا حد زیادی زمان اجرا و پیچیدگی الگوریتم به علت طولانی بودن اضافه ها و حذف ها، افزایش می یابد. الگوریتم مرتب سازی رشته ای روش مناسبی برای داده ای است که از قبل حجم زیادی از داده ها مرتب شده باشند، زیرا که داده ها را می توان در یک رشته واحد برداشته شوند.
این الگوریتم در بدترین حالت ( یک فهرست که به ترتیب معکوس مرتب سازی شده باشد ) از مرتبهٔ Θ ( n۲ ) است.
این الگوریتم در حالت متوسط از مرتبهٔ Θ ( n۲ ) است.
بهترین حالت این است که فهرست قبلاً مرتب شده باشد که در این حالت الگوریتم از مرتبه O ( n ) است.
• یکبار فهرست نامرتب تجزیه می شود، عددهای صعودی ( مرتب شده ) گرفته می شوند.
• فهرست فرعی ( مرتب شده ) را در صورتی که بار اول تکرارش باشد درون فهرست خالی ذخیره می کند.
• دوباره تجزیه فهرست نامرتب و گرفتن عددهای نسبتا مرتب شده.
• از آنجایی که فهرست مرتب سازی شده در حال حاضر پره شده، ادغام فهرست های فرعی در فهرست مرتب شده انجام می شود.
• تکرار گام های ( ۳ - ۴ ) تا زمانی که هر دو فهرست نا مرتب و فهرست فرعی خالی شوند.
در زیر شبه کد پیاده سازی الگوریتم رشته می باشد.
procedure strandSort ( A : list of sortable items ) defined as: while length ( A ) > ۰ clear sublist sublist := A remove A for each i in ۰ to length ( A ) - ۱ do: if A > sublist then append A to sublist remove A end if end for merge sublist into results end while return results end procedure
wiki: مرتب سازی رشته ای