علی‌آباد

Gɴᴏᴍᴇ-Sᴏʀᴛ

يكشنبه, ۶ مهر ۱۳۹۹، ۰۴:۵۷ ق.ظ
الان که دارم این پست رو می‌گذارم ساعت نزدیک ۴ بامداد یکشنبه است. باید تکلیف ساختمان داده رو تا شنبه شب آپلود می‌کردم ولی هنوز حتی یه خط هم ننوشتم. خب استادش ناشیه و توی سامانه ددلاینی برای آپلود نذاشته. و من انگار هنوز از ترم پیش درس نگرفتم که تمرین‌ها رو به نزدیک ددلاین و بعد از ددلاین واگذار نکنم.

باید از مطالبی که استاد هفتهٔ قبل درس داده دوتا سوال دلخواه در بیارم و با جواب بفرستم. موضوع درس الگوریتم‌های مرتب‌سازی بود و نمادهای تحلیل زمان الگوریتم. [خب حالا اینا یعنی چی؟ فرض کنید یه دسته مدادرنگی داریم که بعضی‌هاشون کوتاه‌تر و بعضی‌هاشون بلندترن، و با یه ترتیب تصادفی توی جعبه چیده شدند. حالا چطور می‌تونیم با عملیات‌های مقایسه و جابجایی، این مدادها رو بر اساس طول مرتب کنیم؟ یه روش اینه که کوتاه‌ترین مداد رو پیدا کنیم و جاش رو با مداد اول عوض کنیم. بعد توی n-1 مداد باقی‌مونده کوتاه‌ترین رو پیدا کنیم و با مداد دوم جابجا کنیم و الخ... به این روش می‌گیم مرتب‌سازی انتخابی. حالا باید تحلیل کنیم که بر اساس تعداد مدادها و وضعیت اولیه مدادها، حداقل و حداکثر به چندتا عملیات نیاز پیدا می‌کنیم و این یعنی اجرای الگوریتم‌مون چقدر زمان می‌بره... به عنوان تمرین، می‌تونید فکر کنید که چه روش‌های دیگه‌ای برای مرتب‌کردن مدادرنگی‌ها به ذهن‌تون می‌رسه :)] 

توی ویکی‌پدیا دنبال یه الگوریتم می‌گشتم که نه اونقدر تحلیلش پیچیده باشه که توی نصف صفحه جا نشه و نه اونقدر ساده باشه که نمره نگیرم ازش. دنبال موردی بودم با مرتبهٔ زمانی n² و البته با یه ایدهٔ جدید. حبابی، انتخابی، درجی... اینا خیلی بدیهی بودند. شِل‌سورت، تیم‌سورت، کتابخانه‌ای... اینا هم بیش از حد پیچیده بودند. چشمم خورد به مرتب‌سازی گنوم. گفتم شاید ربطی به گنو/لینوکس داشته باشه. هرچند ربطی نداشت. از اونجا که تازه وارد لینوکس شدم، هر کلمه‌ای مرتبط باهاش توجهم رو جلب می‌کنه.

صفحه‌ی گنوم‌سورت رو توی ویکی‌پدیا باز کردم. چشمم خورد به کلمهٔ شریف. بیشترتر توجهم جلب شد. برگشتم بالای صفحه. نوشته بود این الگوریتم برای اولین‌بار توسط دانشمند رایانهٔ ایرانی ح. سین. الف. (استاد مهندسی و علوم کامپیوتر دانشگاه صنعتی شریف) در سال ۲۰۰۰ مطرح شده. no way! همین امروز صبح با دکتر سین. کلاس داشتم. یعنی من یکی از طراحان الگوریتم‌های مرتب‌سازی رو از نزدیک دیدم و باهاش کلاس هم دارم؟ :) خب باید بگم که تا پیش از این دکتر سین. جذاب‌ترین استاد این ترمم محسوب می‌شد و حالا با این کشف جایگاه ویژه‌تری هم پیدا کرده! 

دربارهٔ خود الگوریتم اگه بخوام بگم، مثال بارز اصل KISS هست: keep it simple, stupid! کل الگوریتم شامل یک حقله، یک شرط و یک متغییر برای پیمایشه. از این نظر با الگوریتم‌های معمولی که می‌شناسیم (دو حلقهٔ تودرتو یا اینکه تابع به صورت بازگشتی خودش رو صدا بزنه) ظاهر متفاوتی داره. اینم از شبه‌کدش:
Gnome-Sort(a[]):
    pos := 0
    while pos < length(a):
        if (pos == 0 or a[pos] >= a[pos-1]):
            pos := pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos := pos - 1

اگه از خوندن کد متوجه رفتارش نشدید، می‌تونید اینجا یه مثال تجسمی ازش ببینید: [کلیک]

اطلاعات بیشتر از صفحهٔ شخصی استاد میگه این الگوریتم رو وقتی توی انگلستان دانشجوی دکترا بوده توی خبرنامهٔ دانشکده منتشر کرده. خیلی برام جالبه که بدونم چطور اولین بار ایدهٔ این الگوریتم به ذهنش رسیده. آیا داشته روی الگوریتم‌های مرتب‌سازی فکر می‌کرده و دنبال کم‌کردن تعداد دستورها بوده؟ آیا کد مشابهی توی یه کتاب دیده و پارامترهاشو کم و زیاد کرده تا به این رسیده؟ یا اینکه یه روز صبح یهویی بیدار شده و این الگوریتم به ذهنش الهام شده؟!
موافقین ۱۱ مخالفین ۰ ۹۹/۰۷/۰۶
علی ‌‌

نظرات  (۱۳)

عه.... یادش بخیر... منم کلی متعجب شدم وقتی دیدم این الگوریتم رو اوشون طراحی کرده😁

پاسخ:
اینا که واسه ما تجربه است، واسه شما خاطره است :دی
۰۶ مهر ۹۹ ، ۱۳:۳۲ فاطمه ‌‌‌‌

به نظرم حالا که استادتونه بپرسین ازش! همینو هم به عنوان تکلیف بدین خوشحال شه :)) 

پاسخ:
اگه فرصتش پیش بیاد حتماً ماجراش رو می‌پرسم!
ولی تکلیفی که گفتم برای درس ساختمان داده و الگوریتم‌ها بود که با یه استاد دیگه دارم. با دکتر سین، درس ساختار کامپیوتر دارم. اصلاً ایشون توی گروه سخت‌افزار و معماری کامپیوتره، نه نرم‌افزار.

@فاطمه

بله، ما تو سخت‌افزار همچین استادهای خفنی داشتیم😏😏

 

۰۶ مهر ۹۹ ، ۲۲:۳۷ استیو ‌‌

اه، علی! صبحی یه کامنتِ بلندبالا برات نوشته بودما، بعد آخراش بودم که یهویی گوشیم خاموش شد.

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

ولی واقعا دلم برای ریاضی تنگ شده یه مقدار، بیشتر از فیزیک! باورش برام سخته حتی :دی با این که همیشه می‌گفتم و احتمالا می‌گم که فیزیک رو به ریاضیات ترجیح می‌دم، واقعا گسسته رو به فیزیک ترجیح می‌دم، براساس این شناخت اولیه و ساده و ابتدایی‌م البته.

نم‌دونم که، خدا آخر و عاقبت‌مون رو به خیر کنه.

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

حالا غیرتی نشی یه وقت :دی

الان یه طوریم که واقعا کامپیوتر شریف رو نیارم و برم تهران ناراحت نمی‌شم، ولی اگه یه وقت امسال ملت وحشی بشن و همه بیان کامپیوتر و مجبور بشم برم امیرکبیر، آره، ناراحت می‌شم احتمالا.

 

+آقا شما شریفیا که همه‌چی رو خلاصه می‌کنین، می‌گم یه مخفف برای کامپیوتر ه

+آه علی! بر طبل شادانه بکوب، پیروز و مردانه بکوب! الان دقیقا آخر خط بالا بودم، که یهویی شارژ لپ‌تاپ هم تموم شد =| نکته‌ی جالب این‌جاست که شارژرش فقط چند سانتی‌متر اون‌طرف‌تر بود و به برق هم وصل بود =| ولی خب، نکته‌ی مثبت این‌جاست که الان که زدمش شارژ و دوباره روشنش کردم، صفحه‌ِی وب باز مونده بود.

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

پاسخ:
امیدوارم زودتر بگیری لپ‌تاپتو. من که ترم اول لپ‌تاپ نداشتم آوره بودم همش. یه مدت از لپ‌تاپ داداشم استفاده می‌کردم، یه مدت کامپیوتر خونه، یه مدت سایت دانشکده... ولی از وقتی لپ‌تاپ گرفتم دیگه همه فایل‌ها و برنامه‌ها و امتحان‌ها و... رو مرتب و منظم و طبقه‌بندی‌شده دارم. تازه پوستمم شفاف‌تر شده =)

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

+ چرا، به طور غیررسمی مخفف کامپیوتر میشه "کامپ". دانشجوی کامپیوتر هم میشه "کامپی". مثل دانشجوی برق که میشه برقی. البته بسیاری معتقدند که برقی و کامپی بودن فقط به رشته‌ات بستگی نداره و این رفتار و کردارته که تعیین‌کننده است. در این باب بین بچه‌های دانشگاه یه ضرب‌المثل داریم که میگه: «برق یک‌ رشته نیست یه سبک زندگیه!» D:
۰۸ مهر ۹۹ ، ۲۲:۲۵ فاطمه ‌‌‌‌

@ نارا

نکشی‌مون خفن :)))

 

@ استیو

شما بیا تهران خودم یه مخففایی یادم بدم دیگه نگی شریفیا همه چی رو خلاصه می‌کنن :))

 

حس می‌کنم شریفی‌ها بیان رو گرفتن :/ =))

۰۹ مهر ۹۹ ، ۱۰:۴۴ استیو ‌‌

پوست شفاف‌تر :دیییی

 

باشد که مقبول درگاه حضرت حق واقع شویم و روزی ما را نیز به حق، کامپی بخوانند!

سبک زندگی :دییی

 

+ علی مراقب باش، وبلاگت داره می‌شه پاتوق مهندسا!

(وی تلاش می‌کند پیش‌پیش خودش را در جمع مهندسان بچپاند :دی)

 

@فاطمه

هنوز ذره‌ای شک و تردید تو دلم مونده بود که برم شریف، که الان دیگه خیالم راحت شد :دی حیف شد که مهلت انتخاب رشته تموم شده، وگرنه می‌رفتم اصلا شریف رو می‌کردم اولویت دومم :دی

 

ولی فکر کنم شریفیا بیشتر نیستن نسبت به تهرانیا، منتها چون نسبتا بیشتر در مورد دانشگاه حرف می‌زنن، سلطه‌ی بیشتری دارن به مراتب!

پاسخ:
+ من که خیلی ذوق دارم که مهندس محسوب بشم :). توی دانشگاه هم نگهبان و نیروهای خدماتی و اینا ما رو مهندس صدا می‌کردند کلی کیف می‌کردیم 😊. ولی احتمالا از نظر بچه‌های علوم پایه این یه فحش حساب میشه 😄

اوهوم. ما اقلیت فعالیم، زیاد به چشم میایم :))
۱۱ مهر ۹۹ ، ۱۲:۲۲ جوزفین مارچ

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

 

+ اون CE اگه مخفف مهندسی کامپیوتر نیست، پس چیه؟ چرا به این بچه نمی‌گی خیالش راحت شه؟ :)

پاسخ:
پس وقتایی که مسیرتون به دانشگاه‌های صنعتی می‌خوره یه مسلسل همراه داشته باشید =)

+ آها خب CE رو می‌دونستم که از قبل بلد بود.

چه جالبه که میای تو اینجور وبلاگ ها بحث دانشگاه و رشته و مهندسی و غیر مهندسی می‌بینی و میشنوی (میخونی)..

شاید هم مربوط به سنتونه این جور بحثها..

 

پاسخ:
اینجور وبلاگ‌ها یعنی کدوم جور وبلاگ‌ها؟ D:
۱۱ مهر ۹۹ ، ۱۹:۵۹ استیو ‌‌

@جوزفین

قبلاً گفته بودن این مورد رو، ولی این‌مخفف‌سازی‌ها قراره کار رو راحت کنه، نه که مجبور بشم هی زبان کی‌بورد رو عوض کنم خب! همین میم‌کامپ خیلی هم خوب و باحاله!

تازه من یه مدت همه‌جا می‌گفتم مهندسی بیوتکنولوژی :دی بعد پیارسال یه روز اومدم دانشگاه‌تون و وقتی پرسیدم، گفتن تو ساختمون علوم‌پایه‌ست، اون موقع بود که تازه به فکر افتادم و فهمیدم!

پاسخ:
حالا میم‌کاف رو هیچکی نمی‌گه. ما از ترم یک خواستیم در راستای پاسداری از زبان فارسی اینو جایگزین CE کنیم ولی استقبال نشد. ولی مهندسی شیمی خیلی رایجه که بگن میم‌شیمی. شیمی خالی هم اگه بگی ناراحت می‌شن و بهشون برمی‌خوره و توضیح می‌دن که رشته‌شون چی هست و چی نیست و ربطی به شیمی نداره و اینا مهندس می‌شن نه شیمی‌دان :)))
۱۱ مهر ۹۹ ، ۲۰:۳۲ استیو ‌‌

میم‌کاف نه‌هااا، میم‌کامپ! نمی‌شه؟.. راه نداره :دی؟ لااقل تو صحبت با تو ازش استفاده می‌کنم :دی

آرهه، منم تو دو مورد دیده بودم که چقدر بدشون می‌آد. حقم دارن، رتبه‌ی قبولی این کجا و اون کجا!


+ به نظر شخص من، «این‌جور وبلاگا» یعنی وبلاگای پرمغز و باحالِ مهندسای مملکت :دی

پاسخ:
نچ نچ نچ... خیلی کار زشت و بیخودیه آدم خیال کنه به خاطر رتبه‌ی کنکور از بقیه بالاتره. تو مثل میم‌شیمی‌ها نباش :)

حالا نمی‌دونم چطور بحث رسید به اینجا، ولی بذار بگم اینو. استاد ادبیات‌مون خیلی حساس بود روی این فرهنگ زبانی دانشجوهای شریف. و به تبعش من رو هم حساس کرده. یه نمونه که بهمون گفت این بود که ما به جای اکثر قیدها، «تا حد خوبی» رو به کار می‌بریم. تا حد خوبی درس خوندم، تا حد خوبی خسته‌ام، امتحان تا حد خوبی سخت بود. اینکه ریشه‌ی این عبارت از کجا اومده، بحث بود سرش. ولی معلومه که گاهی معنای جمله رو ۱۸۰ درجه عوض می‌کنه.

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

الان که سرچ کردم به فارسی چیزی پیدا نشد. ولی به انگلیسی، یه کتابچه پیدا کردم به اسم Jargon File که اصطلاحات مربوط به برنامه‌نویس‌ها رو از دانشگاه‌هایی مثل ام‌آی‌تی و استنفورد جمع‌آوری کرده. می‌رم که بهش یه نگاهی بندازم. شایدم حتی یه پست از نکات جالب و برجسته‌اش نوشتم :)
۱۱ مهر ۹۹ ، ۲۱:۴۰ استیو ‌‌

نههه! منظورم بالاتر و برتر نیست (وگرنه که باید بگیم امسال کلی آدم از من بالاتر بودن، اصلا مگه می‌شه؟! :دییییی)، ولی خب تلاش بیش‌تری کرده به هرحال و دوست داره تلاشش دیده بشه!!

 

آوو، چه باحال! این موضوع جارگون خیلی جالب بودش برام واقعا، ممنون نوشتی. منتظر پست مربوطه هم هستیم :)

@ استیو

"این جور وبلاگا" یعنی وبلاگ کسانی که تازه واردند به دانشگاه و مهندسی و.. و زیادی تو این جور بحث ها و مقایسه هان..

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

 

البته من خودم مسیر مهندسی خودم رو خوشم میاد و برام مهم بود و حرفهای جامعه رو نمیگم درسته، اما به هر حال حرفای شما رو هم اگه خیلی از مهندسین ورودی سالها پیش بشنون، اونا هم براشون جالب خواهد بود.. 

پاسخ:
اوهوم. تأثیر جو سال‌اولی بودنه دیگه :)
۲۲ مهر ۹۹ ، ۰۳:۲۳ پیمان ‌‌

اع اسمش گنوم سورته؟ من یادمه ما بهش سربازی سورت یا استیوپید سورت می‌گفتیم.

ولی خوب انقدر از اون فضا دور شدم که یادم نیست چیزی درست.

پاسخ:
برای اولین بار دکتر سربازی اسم استیوپید سورت رو روش گذاشته بود :)
ولی الان به گنوم سورت معروفه.

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی