پرسش: برنامه ای بنویسید که یک لیست پیوندی و یک عدد دریافت نماید و آن را بگونه ای تغییر دهد که همه مقادیر کوچکتر از x قبل از مقادیر بزرگتر یا مساوی x قرار گیرند. ترتیب نسبی عناصر کوچکتر نسبت به هم و عناصر بزرگتر یا مساوی نسبت به هم نباید تغییر کند.
پاسخ: طبق حل مساله را با یک مثال شروع می کنیم تا مطمین شویم آن را درست درک کرده ایم. چنانچه یک لیست پیوندی شامل مقادیر 12<-9<-5<-11<-2<-15 داشته باشیم و 9=x باشد، آنگاه در لیست پیوندی نهایی حاصل مقادیر کمتر از 9 باید قبل آن و بقیه باید بعد آن قرار گیرند. بنابر این لیست نهایی باید بصورت 12<-9<-11<-15<-5<-2 در آید.
ساده ترین راه برای حل این مساله ایجاد دو لیست پیوندی جداگانه است که یکی شامل عناصر بزرگتر مساوی x و دیگری شامل عناصر کوچکتر از x می باشند. بعد از جداکردن مقادیر عناصر کوچکتر از بزرگتر، این دو لیست را به هم وصل کنیم تا یک لیست جدید با خاصیت گفته شده بوجود آید. برای ایجاد دو لیست جدا باید لیست پیوندی اصلی را یکبار پیمایش کنیم و با دیدن هر عنصر تصمیم بگیریم که به انتهای کدام یک از دو لیست جدید وصلش کنیم.
برای اینکه از درستی این الگوریتم اطمینان حاصل کنیم باید آن را روی لیست پیوندی مثال امتحان کنیم. با این کار همچنین دقیق تر می فهمیم که اشاره گرهای next را در هنگام پیاده سازی چگونه تنظیم نماییم. همزمان که شکل زیر را رسم می کنیم در یک به یک مراحل اجرای الگوریتم را شرح می دهیم و دنبال می کنیم. شکل زیر وضعیت ابتدایی لیست پیوندی اصلی و دو لیست پیوندی جدید یعنی greater_eq_list (عناصر بزرگتر یا مساوی x) و less_list (عناصر کوچکتر از x) را نشان می دهد.
شکل زیر وضعیت لیست ها بعد از پیمایش سه عنصر اول لیست اصلی را نشان می دهد.
با توجه به اینکه عنصر اول بزرگتر از 9 می باشد به لیست greater_eq_list اضافه می شود. اگر یکی از عناصر بعدی نیز بزرگتر از 9 باشد باید آن را به انتهای این لیست اضافه کنیم. بنابر این نیاز داریم که اشاره گری داشته باشیم که آخرین عنصر این لیست را بداند. اسم این اشاره گر را gtail (کلمه tail به معنای دم یا انتهاست و g یاداور کلمه greater) می نامیم. در ادامه پیمایش لیست اصلی به دومین عنصر می رسیم. به این خاطر که آن کوچکتر از 9 می باشد، به لیست less_list اضافه اش می کنیم. یک اشاره گر به نام ltail برای این لیست پیوندی تعریف می کنیم که اشاره گری به انتهای آن را نگه دارد. عنصر بعدی مقدار 11 دارد که از 9 بیشتر است. بنابر این باید آن را به انتهای لیست greater_eq_list اضافه کنیم. این کار را با تغییر اشاره گر next عنصر آخر لیست یعنی gtail انجام می دهیم. سپس مقدار gtail را بروز می کنیم تا به عنصر آخر جدید اشاره کنید. این کار را تا رسیدن به انتهای لیست انجام می دهیم.
با رسیدن به انتهای لیست وضعیت اشاره گر ها اینگونه خواهد بود.
خوب تا اینجای کار عناصر بزرگتر یا مساوی را در یک لیست جدا گذاشته ایم و عناصر کوچکتر را در یک لیست پیوندی دیگر.
حالا باید این دو لیست را با هم ترکیب کنیم بگونه ای که همه عناصر کوچکتر قبل از همه عناصر بزرگتر از x قرار بگیرند. برای این کار باید (۱) عنصر انتهای لیست کوچکترها به عنصر ابتدای لیست بزرگتر مساوی ها اشاره کند، (۲) مقدار next در عنصر انتهایی در لیست بزرگتر مساوی ها به null تنظیم شود، و (۳) متغیر head که به ابتدای لیست نهایی اشاره گر می کند باید به اولین عنصر لیست کوچکترها اشاره کند. شکل زیر وضعیت نهایی اشاره گرها را نشان می دهد.
با این اوصاف مطمین می شویم که الگوریتم درست عمل می کند و می فهمیم که در پیاده سازی به تعدادی اشاره گر و متغییر اضافی نیاز داریم. از آنجا که لیست دارای ترتیب مشخصی نمی باشد بنابر این پیمایش آن اجتناب ناپذیر است. به این خاطر که نیاز به پیمایش کامل لیست داریم، اگر طول لیست n باشد، آنگاه پیچیدگی محاسباتی (مرتبه اجرایی) این الگوریتم (O(n می باشد و الگوریتمی سریعتر ازآن یافت نخواهد شد.
می توانیم در مورد روش پیاده سازی دیگری نیز بصورت خلاصه صحبت کنیم. به این صورت که یکبار لیست را بپیماییم تا عنصر انتهایی لیست را بیابیم. سپس دوباره از ابتدای لیست پیوندی حرکت کنیم. اگر عنصری بزرگتر یا مساوی مقدار x بود آنرا به انتهای لیست منتقل کنیم و در غیر این صورت کاری نکنیم. این الگوریتم دارای پیچیدگی محاسباتی مانند روش ایجاد دو لیست پیوندی است. با این تفاوت که لیست را دوبار باید بپیماییم.
بنظر می رسد که الگوریتم اول سر راست تر است و پیاده سازی آن خواناتر خواهد بود.
بنابراین شروع به پیاده سازی روش اول می کنیم. ابتدا نام مناسب و پارامترهای مناسب شامل عنصر اول لیست پیوندی و مقداری x را به آن می دهیم (خط 1). سپس یک لیست خالی برای ساختن لیست از عناصر بزرگتر مساوی x تعریف می کنیم (خط 2). یک اشاره گر نیز برای اشاره با عنصر انتهایی لیست می گیریم (خط 3). لیست مشابهای برای عناصر کوچکتر از x در نظر می گیریم (خطوط 5 و 6). سپس در یک حلقه تکرار هر بار یک عنصر در لیست پیش می رویم و عنصر کنونی را متناسب با مقدار آن به انتهای لیست بزرگتر مساوی ها یا لیست کوچکتر ها اضافه می کنیم (خطوط 8 تا 16). در انتها مقدار اشاره گر عنصر آخر لیست پیوندی بزرگتر مساوی ها (gtail) را null می کنیم و اشاره گر عنصر آخر لیست پیوندی کوچکترها را به ابتدای لیست بزرگتر مساوی ها تنظیم می کنیم (خط 18 و 19). در انتها عنصر ابتدایی رشته کوچکترها را به عنوان ابتدای لیست جدید برمی گردانیم (خط 20).
