ایا این الگوریتم سریعتر از quicksort است؟

[saeedcheginy]

در لگوریتم بنده تنها میتوان با دادههای 4 بایتی یا کمتر ارایه عمل کرد والا سرعت ان مناسب نخواهد بود.
من از متخصصین کمک می خواهم که جطور می تونم این الگوریتم وکد را ارایه کنم تا اولا این الگوریتم توسط افراد سود جو از جانب خودشان اریه نشد دوما با ارایه آن منافعی (مثل پذیرش در دانشگاههای معتبر یا هرچی) شامل حالم بشه.
سوما اصلا شک دارم که این الگوریتم قبلا ایجاد شده یا نه چون از نظر من چیز ساده وتو چشمی میاد؟
این الگوریتم از ساختار بایتها یعنی 0 تا 256 استفاده کرده طی 4 مرحله که هر مرحله حدود 2n هست آرایه کمتر از 4 بایت را سرت می کند ودر مجموع با حدود 8 تا 10 n کار تمامه.
البته کدها زمانگیر و همه کار با حافظه هستند ولی به علت کم بودن کدها n که از 200000 بیشتر میشه سرعتش از کوییک سرت بیشتر میشه.
ضمنا این روش اصلا بستگی به داده ها نداره و فقط تعدادشون مهمه پس باز از کوییک سرت بهتره چون در شرایطی n^2 هست.
مرتبه زمانی این کد( O (n هست.
ممنون از وقتی که می ذارید وراهنماییتون.:لبخندساده:

[Aidin]

:لبخند: .

[Exception]

در لگوریتم بنده تنها میتوان با دادههای 4 بایتی یا کمتر ارایه عمل کرد والا سرعت ان مناسب نخواهد بود.
من از متخصصین کمک می خواهم که جطور می تونم این الگوریتم وکد را ارایه کنم تا اولا این الگوریتم توسط افراد سود جو از جانب خودشان اریه نشد دوما با ارایه آن منافعی (مثل پذیرش در دانشگاههای معتبر یا هرچی) شامل حالم بشه.
سوما اصلا شک دارم که این الگوریتم قبلا ایجاد شده یا نه چون از نظر من چیز ساده وتو چشمی میاد؟
این الگوریتم از ساختار بایتها یعنی 0 تا 256 استفاده کرده طی 4 مرحله که هر مرحله حدود 2n هست آرایه کمتر از 4 بایت را سرت می کند ودر مجموع با حدود 8 تا 10 n کار تمامه.
البته کدها زمانگیر و همه کار با حافظه هستند ولی به علت کم بودن کدها n که از 200000 بیشتر میشه سرعتش از کوییک سرت بیشتر میشه.
ضمنا این روش اصلا بستگی به داده ها نداره و فقط تعدادشون مهمه پس باز از کوییک سرت بهتره چون در شرایطی n^2 هست.
مرتبه زمانی این کد( O (n هست.
ممنون از وقتی که می ذارید وراهنماییتون.:لبخندساده:
اولین نکته اینکه سریعترین سورت، quick sort نیست و اگر شرایط مساله رو در حالت خاص فرض کنیم (مثل مساله شما) الگوریتم های زیادی با (o(n وجود دارند.
با این تعریفی که شما کردین، این الگوریتم خیلی شبیه Radix Sort به نظر میرسه: http://en.wikipedia.org/wiki/Radix_sort
در اونجا هم (مثل کار شما) (o(kn داریم.

از همه این حرفها گذشته، در مورد شیوه ارایه الگوریتم جواب واضحه! به صورت یک مقاله علمی مینویسیدش و برای ژورنالهای معتبر (همونها که اصطلاحا بهشون ISI میگن) میفرستین. اگر اونها تایید کنن و چاپش کنن هم میتونین (تقریبا) مطمین باشید که الگوریتمتون جدید بوده و هم براتون سند و مدرکه که بتونین از همه مزایاش میتونین استفاده کنین.

ولی در کل به قول آیدین: :لبخند:
(معنیش هم اینه که ارایه الگوریتم برای سورت به این کشکی ها نیست! آخه n ساله که داره رو این مساله کار میشه)

[saeedcheginy]

در جواب دوستان عرض کنم که این الگوریتم بارها با quick sort مقایسه شده و در تمام حالات از آن سریعتر به جواب می رسد لطفا اگه الگوریتم سریعتر از کوییک سرت هست اسمشو بگین تا با الگوریتم خودم مقایسه کنم.
الگوریتم radix کاملا کندتر از کوییک سرته.

[Exception]

در جواب دوستان عرض کنم که این الگوریتم بارها با quick sort مقایسه شده و در تمام حالات از آن سریعتر به جواب می رسد لطفا اگه الگوریتم سریعتر از کوییک سرت هست اسمشو بگین تا با الگوریتم خودم مقایسه کنم.
الگوریتم radix کاملا کندتر از کوییک سرته.
شما منظورم رو درست متوجه نشدین. اصولا شما نمیتونین روش خودتون رو با Quick Sort مقایسه کنید. Quick Sort یک روش مرتب سازی کلی (بدون در نظر گرفتن شرایط خاص بر روی مساله) هست که برای هر تعداد n با هر مشخصاتی (مثل طول عدد) جواب میده. شما در صورتی میتونین سرعت الگوریتمتون رو با این روش مقایسه کنید که روش شما هم همین خصوصیات رو داشته باشه.
وقتی شما روی مساله شرایط خاص میذارین (مثل همین که گفتین داده های 4 بایتی یا کمتر) اونوقت باید الگوریتمتون رو با الگوریتمهای مشابه مقایسه کنید.
در مورد Order هم الگوریتم شما کاملا مشابه Radix Sort هست. در Radix Sort هم Order ضریب ثابتی از n هست که این ضریب ثابت (k) از طول ارقام و مبنای استفاده شده در sort به دست میاد. مثلا اگر مبنا رو 16 بگیرید، اونوقت برای داده های 4 بایتی دقیقا Order الگوریتم (O(8n میشه (دقیقا مثل همون که شما گفتید).
حالا در نهایت یک سوال هم من دارم. شما طبق چه منطقی میگید که Radix Sort از Quick Sort کندتره؟ همینجوری بدون دلیل که نمیشه ادعا کرد.

[saeedcheginy]

با تشکر از شما که علاقه مند هستین و اگه مثل دوستمون به نظرتون مسئله طرح شده خنده داره باز با متانت پاسخ بنده رو دادین.
تا آنجا که من میدانم الگوریتم radix تنها زمانی kn میشه که داده ها به صورت 10 10ی در هر بایت
وجود داشته باشند یعنی مدلی خاص از ذخیرهی دادهها که با پرت زیاد منجر به کارایی وسرعت میشه.
در غیر این صورت با تقسیم های سنگین میباست اعداد را بشکند.ضمنا اگه بخواهد از ساختار بایت ها هم استفاده کند باید در مبنای 256 ببرد نه 16 .
که درین صورت باز سرت آن 4 یا هشت مرحله به این کشکی هانمی شود.
در الگوریتم من با کمترین ضرب و تقسیم فقط با کار با حافظه عمل سرت انجام می شود.
در ضمن الگوریتم من درباره ی تمام انواع دادهها kn است ولی به علت مکس زیاد حافظه تصور میکردم برای دادههای 4 بایت بیشتر جواب نمیده ولی
همین امشب با بهینه کردن الگوریتمم حدود 20% سریعتر شد که حالا خیلی امیدوارم برای دادههای بیشتر از4 بایت هم جواب بده.
ولی هنوز شکم اینه که این الگوریتم استفاده بشه والا فوق العاده میتونه جای کار داشته باشه حتی به نظرم تا 10 15 درصد دیگه هم جای بهینه شدن داره که درین صورت نصف زمان quick sort خواهد بود. بازم ممنونم