## Wednesday, October 3, 2012

### Counting Sort

New Generation of Sorting Approach? The general idea behind sorting is to compare the elements with one another and move them in correct relative positions. This involves `O(n^2)` algorithms like Bubble Sort, Selection Sort, Insertion Sort; and `O(n*logn)` procedures like Heapsort, Merge Sort, and Quicksort. Counting sort is linear order sorting and it does NOT depend on how elements compare to each other, rather it depends on their absolute values.

Can you explain it to my 5 year old brother? Say, you have a bag of coins; values: 1 to 5. Your mom asked you to arrange the coins in increasing order making a queue. One of the mechanisms is to pick a coin and search for the right location in sorted queue, and insert at right place. (Do you see insertion sort here?). Another idea is you pick five empty buckets, mark them as 1, 2,... 5. Now, you pick coins from the bag put coin with value 1 in bucket marked as 1, coin with value 2 in bucket number 2, and so on.

 Buckets in Counting Sort, start adding coins :)
Once we are done with this, we empty bucket 1, make a queue of coins of value 1. Then empty bucket 2, append to the queue, and continue this till you emptied all the buckets. You now have sorted queue. This is the idea behind counting sort. And with a little variation, the same concept applies to Bucket sort and Radix sort.

Wow! I will use it everywhere! So, why do we not always use linear sorting? The caveat is, it needs extra space; something like an array at least of length (Amax - Amin). Just to give you an idea, if you have an array with a number `134,217,728`, (about 134Mn; let's say you are sorting rich people by their wealth) you will have to preallocate an array of type int of length 134217728. The maths of it is `134217728*4 bytes = 536870912 bytes = 512MB` of space!! So, you can't just apply it on any input. It is good as long as you know the bounds of the array and the auxiliary array can be accomodated in your machine's RAM without twitching it.

Back to business: Here is the algorithm:
```countingSort(A)
max = maxOf(A)
//create buckets
buckets = INT[max]

//initialize buckets
for i = 1 to buckets.length
buckets[i] = 0

//add values to appropriate bucketsI will explain in a rather layman terms.
for i = 1 to A.length
currentVal = A[i]
buckets[currentVal] = buckets[currentVal] + 1

//shift the value with offset equal to the queue ahead of it.
for i = 2 to buckets.length
buckets[i] = buckets[i-1] + buckets[i]

//put sorted values to a new Array
B = INT[A.length]
for i = 1 to A.length
B[buckets[A[i]]] = A[i]
buckets[A[i]] = buckets[A[i]] - 1

return B

maxOf(A)
max = INT_MIN
for i = 1 to A.length
if A[i] > max
max = A[i]
return max```

Complexity: All operations are `O(n)`.

Refer:
[1] Introduction to Algorithms - CLRS, chapter 8: Sorting in linear time.

1. شركة أبو سمره
لخدمات المنزلية في مدينة الرياض انها :
تقدم ارقى خدمات التنظيف في مدينة الرياض مثال: شقق والمازل والشقق والفلل و خزانات و مجالس فى اسرع وقت ممكن وفى سريه تامه وبدون ازعاج للعميل اقل الاسعار المتميزه سوف تجد لدينا مع افضل لقد ابتكرنا طرق جديدة شركة تنظيف بالرياض
وابتكرنا ايضا افضل شئ وافضل بند من بنود التنظيف وهو اليدة العاملة فعمالة شركة مدربة على اعلى مستوى مع
شركة ابو سمره لجميع الخمات المنزلية الشركة الاولى بالمنطقة شركة نقل اثاث بالرياض
شركة تخزين اثاث بالرياض
التى تعتمد على ارقى العمالة المدربة لدينا قدرات خاصة ولدينا افضل واعظم الايد العاملة نقوم بنقل الاثاث من حى الي حى او من بيت الى بيت وايضا نقوم بنقل العفش
داخل وخارج مدينة الرياض والاستعانة باافضل شركة تنظيف خزانات بالرياض
شركة عزل خزانات بالرياض
شركة كشف تسربات المياه بالرياض
شركة ابو سمره للتنظيف ارقى الشركات بمدينة الرياض كما تعمل شركتنا ايضا في مجال نقوم بتسليك او بحل اى انسداد مهم كانت صعويته بفضل خبرتنا التى اكتسبنا من السنوات الطويلة التى عملنا به نقوم بتدريب عمالتنا با استمرا للوصول الى
تمكنا من ايجاد طرق تنظيف
شركة رش مبيدات بالرياض
الشركة الاولى فى الرياض فى هذا المجال اتصل نصل نحن متوجدون دائما بجانبك بعد كل ذلك الانجازات لا تنسى الشركة اهم وافضل الاقسام هو مكافة الحشرات اليكم ارقى شركات الخرج فى تلك المجال مقدمه من شركة مكافحة حشرات بالرياض
يختلف عن المكافحة فنحن نراعى دائما توفير كل سبل الراحلة لعملائنا الكرام فتفضل
واليك خدمات عديدة بمدينة الرياض ووصلت وتنتهى با افضل
تعد شركتنا الشركة المحببه فى تلك المجالات والتى تقوم با ارضاء جميع عملائها دائما نحظى على اعجاب الكثيرون ونامل ان نكون عند حسن الظن دائماً
شركة تنظيف شقق بالرياض
شركة تنظيف فلل بالرياض
تنظيف موكيت بالرياض
شركة تسليك مجاري بالرياض
شركة تنظيف بيارات بالرياض
شركة صيانة وترميم بالرياض انتظروا ل جديد من شركتنا

2. شركة مكافحة حشرات بالمدينه المنوره

شركة مكافحة حشرات بالمدينه المنوره

مكافحة جميع انواع الحشرات والقوارض بالمدينة المنورة بافضل التقنيات
بايدى متخصصين ماهرين فى مجال مكافحة الحشرات باليات حديثة عاية الجودة
رش حشرات بالمدينة المنوة مكافحة الصراصير
النمل العتة البق النمل الابيض الفئران
الافاعى الابراص افضل انواع المبيدات
طعوم عالمية للفئران
اتصل بنا 0550617882
زورو موقعنا

شركة مكافحة حشرات بالمدينة المنورة

شركة مكافحة البق بالمدينة المنورة

شركة مكافحة النمل الابيض بالمدينة المنورة

شركة مكافحة الصراصير بالمدينة المنورة