مرتب سازی پرچم آمریکا. مرتب سازی پرچم آمریکا نوع دیگر الگوریتم مؤثر و درجا از مرتب سازی پایه ای است که آیتم ها را درون صدها سطل توزیع می کند. از الگوریتم های مرتب سازی غیرمقایسه ای مانند مرتب سازی پایه ای و مرتب سازی پرچم آمریکا معمولاً برای مرتب کردن اشیای بزرگ مانند رشته ها استفاده می شود که در آن ها مقایسه عمل واحد زمان نیست. مرتب سازی پرچم آمریکا میان بیت های شی تکرار شده که برای هر شی در هر زمان چندین بیت را در نظر می گیرد. مرتب سازی پرچم آمریکا برای هر مجموعه از بیت ها دو بار آرایهٔ اشیا را مرور می کند: اول برای شمارش تعداد اشیایی که در هر سطل قرار می گیرد، و دوم برای قرار دادن شی در سطل خودش. این روش مخصوصاً زمانی مؤثر واقع می شود که با استفاده از ۲۵۶ سطل یک بایت در یک زمان مرتب شود. این روش با برخی بهینه سازی ها برای مجموعه های بزرگی از رشته ها دو برابر سریع تر از مرتب سازی سریع است.
نام این روش از قیاس با مسئله پرچم ملی هلند در گام آخر می آید: افراز مؤثر آرایه به تعداد زیادی «راه راه».
به طور کلی الگوریتم های مرتب سازی لیستی از اشیا را با توجه به طرح مرتب سازی، مرتب می کنند. در مقابل الگوریتم های مرتب سازی بر اساس مقایسه، مانند مرتب سازی سریع، مرتب سازی پرچم آمریکا تنها قادر به مرتب سازی اعداد صحیح است ( یا اشیایی که بتوان آن ها را به منزلهٔ اعداد صحیح تفسیر کرد ) . الگوریتم های مرتب سازی درجا، ازجمله مرتب سازی پرچم آمریکا، بدون تخصیص مقادیر قابل توجهی حافظه که فراتر از مقدار استفاده شده توسط آرایهٔ اصلی باشد، اجرا می شوند. این موضوع مزیت مهمی در صرفه جویی در حافظه و زمان کپی کردن آرایه است.
مرتب سازی پرچم آمریکا با تقسیم پیاپی لیستی از اشیا به سطل ها بر اساس اولین رقم نمایش پایه N آن هاست ( پایه ای که استفاده می شود به عنوان مبنا ذکر می شود ) . اگر N برابر ۲ باشد، می توان هر شی را با استفاده از الگوریتم پرچم ملی هلند در سطل درست قرار داد. وقتی N بزرگتر باشد، اشیا نمی توانند بلافاصله در جایگاه قرار گیرند، زیرا مشخص نیست که هر سطل کجا شروع و به کجا ختم می شود. مرتب سازی پرچم آمریکا با دو بار مرور کردن آرایه این مشکل را حل می کند. بار اول تعداد اشیایی را که در هر یک از N سطل قرار می گیرند شمرده و سپس با مجموع مقدار سطل های قبلی، ابتدا و انتهای هر سطل در آرایه اصلی محاسبه می شود. در مرحله دوم هر شی به مکان درستش جابه جا می شود.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفنام این روش از قیاس با مسئله پرچم ملی هلند در گام آخر می آید: افراز مؤثر آرایه به تعداد زیادی «راه راه».
به طور کلی الگوریتم های مرتب سازی لیستی از اشیا را با توجه به طرح مرتب سازی، مرتب می کنند. در مقابل الگوریتم های مرتب سازی بر اساس مقایسه، مانند مرتب سازی سریع، مرتب سازی پرچم آمریکا تنها قادر به مرتب سازی اعداد صحیح است ( یا اشیایی که بتوان آن ها را به منزلهٔ اعداد صحیح تفسیر کرد ) . الگوریتم های مرتب سازی درجا، ازجمله مرتب سازی پرچم آمریکا، بدون تخصیص مقادیر قابل توجهی حافظه که فراتر از مقدار استفاده شده توسط آرایهٔ اصلی باشد، اجرا می شوند. این موضوع مزیت مهمی در صرفه جویی در حافظه و زمان کپی کردن آرایه است.
مرتب سازی پرچم آمریکا با تقسیم پیاپی لیستی از اشیا به سطل ها بر اساس اولین رقم نمایش پایه N آن هاست ( پایه ای که استفاده می شود به عنوان مبنا ذکر می شود ) . اگر N برابر ۲ باشد، می توان هر شی را با استفاده از الگوریتم پرچم ملی هلند در سطل درست قرار داد. وقتی N بزرگتر باشد، اشیا نمی توانند بلافاصله در جایگاه قرار گیرند، زیرا مشخص نیست که هر سطل کجا شروع و به کجا ختم می شود. مرتب سازی پرچم آمریکا با دو بار مرور کردن آرایه این مشکل را حل می کند. بار اول تعداد اشیایی را که در هر یک از N سطل قرار می گیرند شمرده و سپس با مجموع مقدار سطل های قبلی، ابتدا و انتهای هر سطل در آرایه اصلی محاسبه می شود. در مرحله دوم هر شی به مکان درستش جابه جا می شود.
wiki: مرتب سازی پرچم آمریکا