مرتب ساز شمارشی یکی از الگوریتم های مرتب سازی است که ( مثل مرتب ساز سطلی ) با فرض دانستن بازه اعداد داخل آرایه ( A ) ، عمل مرتب سازی را انجام می دهد. این الگوریتم از این بازه برای ساختن یک آرایه ( C ) با این طول استفاده می کند. هر اندیس i در آرایه C برای شمارش تعداد عناصر A که دارای مقدار i هستند، به کار می رود. این اعداد در C برای قرار دادن عناصر A در جای درستشان در آرایه خروجی، به کار می روند. مرتب ساز لانه کبوتری از این الگوریتم، کارآمدتر است.
مرتب ساز شمارشی، یک مرتب ساز پایدار است و دارای زمان اجرای ( Θ ( n+k است که n و k به ترتیب، طول های آرایه های A ( آرایه ورودی ) و C ( آرایه شمارشی ) هستند. برای این که الگوریتم، کارآمد باشد، k نباید خیلی بیشتر از n باشد.
اندیس های C، باید از کوچکترین تا بزرگترین عناصر A باشند تا بتوان C را به صورت مستقیم با مقادیر A، اندیس گذاری کرد. در غیر این صورت، مقادیر A باید انتقال ( شیفت ) داده شوند تا کمترین مقدار A، معادل کوچکترین اندیس C شود. اگر بیشتری و کمترین مقادیر A معلوم نباشند، باید توسط یک الگوریتم انتخاب، که زمان ( Θ ( n می گیرد، آنها را پیدار کرد. طول آرایه شمارشی C، حداقل باید برابر بازه اعداد ورودی باشد. ( کمترین منهای بیشتری و به اضافه ۱ ) . این ویژگی باعث می شود که استفاده از مرتب ساز شمارشی برای بازه های بزرگ اعداد، غیرعملی شود. مرتب ساز شمارشی، برای مثال، می تواند بهترین الگوریتم برای اعدادی باشد که بین ۰ و ۱۰۰ قرار دارند. این الگوریتم برای مرتب کردن اسامی بر اساس حروف الفبا، نامناسب است ( مراجعه شود به مرتب ساز سطلی و مرتب ساز لانه کبوتری ) .
به علت اینکه مرتب ساز شمارشی، از مقادیر به عنوان اندیس آرایه استفاده می کند، یک الگوریتم مرتب ساز مقایسه ای، نیست و بنابراین کران پایین ( Ω ( n log n برای این الگوریتم قابل تطبیق نیست.
• کوچکترین و بزرگترین عناصر مجموعه را پیدا کن.
• مقادیر مختلف موجود در آرایه را بشمار. ( برای مثال، مجموعه دارای سه تا ۴ و دو تا ۱ است )
• شمارش ها را جمع کن.
• آرایه مقصد را از انتها پر کن: هر عنصر را در موقعیت countام قرار بده. هر موقع که عنصری را درج می کنی، شمارشش را یکی کم کن.
/// countingSort - sort an array of values. /// /// For best results the range of values to be sorted /// should not be significantly larger than the number of /// elements in the array. /// /// param nums - input - array of values to be sorted /// param size - input - number of elements in the array /// void counting_sort ( int *nums, int size ) { // search for the minimum and maximum values in the input int i, min = nums, max = min; for ( i = 1; i < size; ++i ) { if ( nums < min ) min = nums; else if ( nums > max ) max = nums; } // create a counting array, counts, with a member for // each possible discrete value in the input. // initialize all counts to 0. int distinct_element_count = max - min + 1; int* counts = new int; for ( i=0; i< distinct_element_count; ++i ) counts = 0; // accumulate the counts - the result is that counts will hold // the offset into the sorted array for the value associated with that index for ( i=0; i< size; ++i ) ++counts; // store the elements in the array int j=0; for ( i=min; i< =max; i++ ) for ( int z=0; z< counts; z++ ) nums = i; delete counts; } . . . . منبع Wikipedia contributors, "Counting sort, " Wikipedia, The Free Encyclopedia, http://en. wikipedia. org/w/index. php?title=Counting_sort& oldid=209333915
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمرتب ساز شمارشی، یک مرتب ساز پایدار است و دارای زمان اجرای ( Θ ( n+k است که n و k به ترتیب، طول های آرایه های A ( آرایه ورودی ) و C ( آرایه شمارشی ) هستند. برای این که الگوریتم، کارآمد باشد، k نباید خیلی بیشتر از n باشد.
اندیس های C، باید از کوچکترین تا بزرگترین عناصر A باشند تا بتوان C را به صورت مستقیم با مقادیر A، اندیس گذاری کرد. در غیر این صورت، مقادیر A باید انتقال ( شیفت ) داده شوند تا کمترین مقدار A، معادل کوچکترین اندیس C شود. اگر بیشتری و کمترین مقادیر A معلوم نباشند، باید توسط یک الگوریتم انتخاب، که زمان ( Θ ( n می گیرد، آنها را پیدار کرد. طول آرایه شمارشی C، حداقل باید برابر بازه اعداد ورودی باشد. ( کمترین منهای بیشتری و به اضافه ۱ ) . این ویژگی باعث می شود که استفاده از مرتب ساز شمارشی برای بازه های بزرگ اعداد، غیرعملی شود. مرتب ساز شمارشی، برای مثال، می تواند بهترین الگوریتم برای اعدادی باشد که بین ۰ و ۱۰۰ قرار دارند. این الگوریتم برای مرتب کردن اسامی بر اساس حروف الفبا، نامناسب است ( مراجعه شود به مرتب ساز سطلی و مرتب ساز لانه کبوتری ) .
به علت اینکه مرتب ساز شمارشی، از مقادیر به عنوان اندیس آرایه استفاده می کند، یک الگوریتم مرتب ساز مقایسه ای، نیست و بنابراین کران پایین ( Ω ( n log n برای این الگوریتم قابل تطبیق نیست.
• کوچکترین و بزرگترین عناصر مجموعه را پیدا کن.
• مقادیر مختلف موجود در آرایه را بشمار. ( برای مثال، مجموعه دارای سه تا ۴ و دو تا ۱ است )
• شمارش ها را جمع کن.
• آرایه مقصد را از انتها پر کن: هر عنصر را در موقعیت countام قرار بده. هر موقع که عنصری را درج می کنی، شمارشش را یکی کم کن.
/// countingSort - sort an array of values. /// /// For best results the range of values to be sorted /// should not be significantly larger than the number of /// elements in the array. /// /// param nums - input - array of values to be sorted /// param size - input - number of elements in the array /// void counting_sort ( int *nums, int size ) { // search for the minimum and maximum values in the input int i, min = nums, max = min; for ( i = 1; i < size; ++i ) { if ( nums < min ) min = nums; else if ( nums > max ) max = nums; } // create a counting array, counts, with a member for // each possible discrete value in the input. // initialize all counts to 0. int distinct_element_count = max - min + 1; int* counts = new int; for ( i=0; i< distinct_element_count; ++i ) counts = 0; // accumulate the counts - the result is that counts will hold // the offset into the sorted array for the value associated with that index for ( i=0; i< size; ++i ) ++counts; // store the elements in the array int j=0; for ( i=min; i< =max; i++ ) for ( int z=0; z< counts; z++ ) nums = i; delete counts; } . . . . منبع Wikipedia contributors, "Counting sort, " Wikipedia, The Free Encyclopedia, http://en. wikipedia. org/w/index. php?title=Counting_sort& oldid=209333915
wiki: مرتب سازی شمارشی