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, bucket sort :)
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.
[2] Download/view Java code from GitHub

17 comments:

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

    ReplyDelete

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

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


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

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


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


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


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


    https://www.youtube.com/watch?v=9gXhlVaS9rk

    ReplyDelete
  3. very very nice post

    شراء الاثاث المستعمل بالمدينة المنورة


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


    شركة مكافحة حشرات بينبع  


    شركة تنظيف خزانات بالمدينة المنورة


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

    شركة شراء اثاث مستعمل بالمدينه المنوره


    شراء الاثاث المستعمل بالمدينة المنورة

    شراء الاثاث المستعمل بالمدينة المنورة


    شراء الاثاث المستعمل بالمدينة المنورة


    ارقام شراء الاثاث المستعمل بالمدينة المنورة



    شراء الاثاث المستعمل بالمدينة المنورة



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


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


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


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



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


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


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


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


    شراء الاثاث المستعمل بتبوك


    شركة مكافحة حشرات بينبع


    شركة تسليك مجارى بالمدينة المنورة



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


    شركة تنظيف خزانات بالمدينة المنورة


    شركة تنظيف خزانات بالمدينة المنورة


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


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


    شركة تنظيف خزانات بالمدينة المنورة


    شركة شراء الاثاث المستعمل بالمدينة المنورة


    شركة شراء اثاث مستعمل بالمدينة المنورة



    تسليك مجارى بالمدينة المنورة


    شركة غسيل كنب بالمدينة المنورة

    ReplyDelete