برای صعودی کردن آرایه ای به طولn که بصورت نزولی مرتب شده است از روش مرتی سازی سریع استفاده می کنیم :اگر همواره کوچکترین عنصر را به عنوان محور انتخاب کنیم مرتبه زمانی آن چند می شود؟
به نظر خودم بدترین حالت نیست به نظر شما این بدترین حالت هست؟
(۰۱ دى ۱۳۹۱ ۰۸:۴۲ ب.ظ)nasim mehri92 نوشته شده توسط: برای صعودی کردن آرایه ای به طولn که بصورت نزولی مرتب شده است از روش مرتی سازی سریع استفاده می کنیم :اگر همواره کوچکترین عنصر را به عنوان محور انتخاب کنیم مرتبه زمانی آن چند می شود؟
به نظر خودم بدترین حالت نیست به نظر شما این بدترین حالت هست؟
به نظر من بدترین حالته و میشه n^2
سلام
بله بدترین حالت هست چون یه زیرآرایه به طول n-1 و دیگری به طول ۱ این بدترین حالته و بنابراین مرتبش O(n) میشه
سلام.
دوستان دقت کنید که گفته هربار "کوچک ترین" عنصر رو بعنوان محور در نظر می گیریم.
--------------------------------------------------------------------------------------------
بدترین حالت در مرتب سازی سریع زمانی هست که عناصر بصورت صعودی مرتب شده باشند و بخوایم عناصر رو بصورت صعودی مرتب کنیم. و همچنین بدترین حالت زمانی هست که عناصر نزولی مرتب باشند و بخوایم نزولی مرتب کنیم.
اما سوال گفته که در ابتدا عناصر بصورت نزولی مرتب شده است؛ و ما می خواهیم اون رو بصورت صعودی مرتب کنیم.
پس یعنی مثلا عناصر زیر
۹۸۷۶۵۴۳۲۱
رو بصورت
۱۲۳۴۵۶۷۸۹
مرتب کنیم.
رو داده های زیر امتحان کنید و هر بار کوچکترین عنصر رو محور بگذارید.
(محور عدد ۱)مرحله اول جای ۱ و ۹ عوض میشه. ------> 187654329 (در مرحله بعد ۲ بعنوان لولا انتخاب میشه. درسته که تمام عناصر یک طرف عدد ۱ قرار دارند ولی این ربطی به بدترین حالت نداره).
(محور عدد ۲)مرحله دوم جای ۲ با ۸ عوض میشه------->127654389
(محور عدد ۳)مرحله سوم جای ۳ با ۷ عوض میشه.----->123654789
(محور عدد ۴)مرحله چهارم جای ۴ با ۶ عوض میشه.---->123456789
(محور عدد ۵)مرحله پنجم جای ۵ با ۵ عوض میشه.---->123456789
در مراحل دیگه هم اعداد ۶ و ۷ و ۸ و ۹ با خودشون عوض میشن.
فکر می کنم با بدترین حالت تفاوت داشته باشه و از مرتبه O(n باشه.(مطمئن نیستم).
(۰۲ دى ۱۳۹۱ ۰۱:۲۴ ق.ظ)azad_ahmadi نوشته شده توسط: سلام.سلام
دوستان دقت کنید که گفته هربار "کوچک ترین" عنصر رو بعنوان محور در نظر می گیریم.
--------------------------------------------------------------------------------------------
بدترین حالت در مرتب سازی سریع زمانی هست که عناصر بصورت صعودی مرتب شده باشند و بخوایم عناصر رو بصورت صعودی مرتب کنیم. و همچنین بدترین حالت زمانی هست که عناصر نزولی مرتب باشند و بخوایم نزولی مرتب کنیم.
اما سوال گفته که در ابتدا عناصر بصورت نزولی مرتب شده است؛ و ما می خواهیم اون رو بصورت صعودی مرتب کنیم.
پس یعنی مثلا عناصر زیر
۹۸۷۶۵۴۳۲۱
رو بصورت
۱۲۳۴۵۶۷۸۹
مرتب کنیم.
رو داده های زیر امتحان کنید و هر بار کوچکترین عنصر رو محور بگذارید.
(محور عدد ۱)مرحله اول جای ۱ و ۹ عوض میشه. ------> 187654329 (در مرحله بعد ۲ بعنوان لولا انتخاب میشه. درسته که تمام عناصر یک طرف عدد ۱ قرار دارند ولی این ربطی به بدترین حالت نداره).
(محور عدد ۲)مرحله دوم جای ۲ با ۸ عوض میشه------->127654389
(محور عدد ۳)مرحله سوم جای ۳ با ۷ عوض میشه.----->123654789
(محور عدد ۴)مرحله چهارم جای ۴ با ۶ عوض میشه.---->123456789
(محور عدد ۵)مرحله پنجم جای ۵ با ۵ عوض میشه.---->123456789
در مراحل دیگه هم اعداد ۶ و ۷ و ۸ و ۹ با خودشون عوض میشن.
فکر می کنم با بدترین حالت تفاوت داشته باشه و از مرتبه O(n باشه.(مطمئن نیستم).
اگه اینجوری بود که میگفتن بهترین حالت مرتب سازی سریع هستش اوی ان !!! تازه من میرفتم ثبتش میکردم و معروف میشدم !
خوب تیری در تاریکیه. خواهشا اگه ثبتش کردی حداقل تو پیشگفتاری جایی اسم من رو هم فراموش نشه.
شاید همون بدترین حالت باشه، اما باز مطمئن نیستم.
(۰۲ دى ۱۳۹۱ ۰۱:۲۴ ق.ظ)azad_ahmadi نوشته شده توسط: سلام.توجه کنین توی حالت اول n-1 مقایسه انجام شده حالت دوم n-2 و الی آخر که به ۱ ختم بشه مجموع این مقایسه هاO(n^2) میشه.
دوستان دقت کنید که گفته هربار "کوچک ترین" عنصر رو بعنوان محور در نظر می گیریم.
--------------------------------------------------------------------------------------------
بدترین حالت در مرتب سازی سریع زمانی هست که عناصر بصورت صعودی مرتب شده باشند و بخوایم عناصر رو بصورت صعودی مرتب کنیم. و همچنین بدترین حالت زمانی هست که عناصر نزولی مرتب باشند و بخوایم نزولی مرتب کنیم.
اما سوال گفته که در ابتدا عناصر بصورت نزولی مرتب شده است؛ و ما می خواهیم اون رو بصورت صعودی مرتب کنیم.
پس یعنی مثلا عناصر زیر
۹۸۷۶۵۴۳۲۱
رو بصورت
۱۲۳۴۵۶۷۸۹
مرتب کنیم.
رو داده های زیر امتحان کنید و هر بار کوچکترین عنصر رو محور بگذارید.
(محور عدد ۱)مرحله اول جای ۱ و ۹ عوض میشه. ------> 187654329 (در مرحله بعد ۲ بعنوان لولا انتخاب میشه. درسته که تمام عناصر یک طرف عدد ۱ قرار دارند ولی این ربطی به بدترین حالت نداره).
(محور عدد ۲)مرحله دوم جای ۲ با ۸ عوض میشه------->127654389
(محور عدد ۳)مرحله سوم جای ۳ با ۷ عوض میشه.----->123654789
(محور عدد ۴)مرحله چهارم جای ۴ با ۶ عوض میشه.---->123456789
(محور عدد ۵)مرحله پنجم جای ۵ با ۵ عوض میشه.---->123456789
در مراحل دیگه هم اعداد ۶ و ۷ و ۸ و ۹ با خودشون عوض میشن.
بدترین حالت اتفاق می افته
چون کد پارتشین آرایه رو طوری تقسیم میکنه که روال بازگشتی به این صورت فراخوانی بشه : [tex](1,N-1)[/tex]
پس بدترین حالت رخ میده و از مرتبه [tex]O(n^{2})[/tex] است.