Median and Mode using Counting Sort
Given an n sized unsorted array, find median and mode using counting sort technique. This can be useful when array elements are in limited range.
Examples:
Input : array a[] = {1, 1, 1, 2, 7, 1} Output : Mode = 1 Median = 1 Note: Median is average of middle two numbers (1 and 1) Input : array a[] = {9, 9, 9, 9, 9} Output : Mode = 9 Median = 9
Prerequisites: Count Sort, Median of Array, Mode (Most frequent element in array)
Input = [1, 4, 1, 2, 7, 1, 2, 5, 3, 6]
1. Auxiliary(count) array before summing its previous counts, c[]:
Index: 0 1 2 3 4 5 6 7 8 9 10
count: 0 3 2 1 1 1 1 1 0 0 0
2. Mode = index with maximum value of count.
Mode = 1(for above example)
3. count array is modified similarly as it is done while performing count sort.
Index: 0 1 2 3 4 5 6 7 8 9 10
count: 0 3 5 6 7 8 9 10 10 10 10
4. output array is calculated normally as in count sort, b[]:
output array b[] = {1, 1, 1, 2, 2, 3, 4, 5, 6, 7}
5. If size of array b[] is odd, Median = b[n/2]
Else Median = (b[(n-1)/2] + b[n/2])/2
6. For above example size of b[] is even hence, Median = (b[4] + b[5])/2.
Median = (2 + 3)/2 = 2.5
Basic Approach to be followed :
Assuming size of input array is n:
Step1: Take the count array before summing its previous counts into next index.
Step2: The index with maximum value stored in it is the mode of given data.
Step3: In case there are more than one indexes with maximum value in it, all are results for mode so we can take any.
Step4: Store the value at that index in a separate variable called mode.
Step5: Continue with the normal processing of the count sort.
Step6: In the resultant(sorted) array, if n is odd then median = middle-most element of the sorted array, And if n is even the median = average of two middle-most elements of the sorted array.
Step7: Store the result in a separate variable called median. Following is the implementation of problem discussed above:
Following is the implementation of problem discussed above:
C++
// C++ Program for Mode and // Median using Counting // Sort technique #include <bits/stdc++.h> using namespace std; // function that sort input array a[] and // calculate mode and median using counting // sort. void printModeMedian( int a[], int n) { // The output array b[] will // have sorted array int b[n]; // variable to store max of // input array which will // to have size of count array int max = *max_element(a, a+n); // auxiliary(count) array to // store count. Initialize // count array as 0. Size // of count array will be // equal to (max + 1). int t = max + 1; int count[t]; for ( int i = 0; i < t; i++) count[i] = 0; // Store count of each element // of input array for ( int i = 0; i < n; i++) count[a[i]]++; // mode is the index with maximum count int mode = 0; int k = count[0]; for ( int i = 1; i < t; i++) { if (count[i] > k) { k = count[i]; mode = i; } } // Update count[] array with sum for ( int i = 1; i < t; i++) count[i] = count[i] + count[i-1]; // Sorted output array b[] // to calculate median for ( int i = 0; i < n; i++) { b[count[a[i]]-1] = a[i]; count[a[i]]--; } // Median according to odd and even // array size respectively. float median; if (n % 2 != 0) median = b[n/2]; else median = (b[(n-1)/2] + b[(n/2)])/2.0; // Output the result cout << "median = " << median << endl; cout << "mode = " << mode; } // Driver program int main() { int a[] = { 1, 4, 1, 2, 7, 1, 2, 5, 3, 6 }; int n = sizeof (a)/ sizeof (a[0]); printModeMedian(a, n); return 0; } |
Java
import java.util.Arrays; // Java Program for Mode and // Median using Counting // Sort technique class GFG { // function that sort input array a[] and // calculate mode and median using counting // sort. static void printModeMedian( int a[], int n) { // The output array b[] will // have sorted array int [] b = new int [n]; // variable to store max of // input array which will // to have size of count array int max = Arrays.stream(a).max().getAsInt(); // auxiliary(count) array to // store count. Initialize // count array as 0. Size // of count array will be // equal to (max + 1). int t = max + 1 ; int count[] = new int [t]; for ( int i = 0 ; i < t; i++) { count[i] = 0 ; } // Store count of each element // of input array for ( int i = 0 ; i < n; i++) { count[a[i]]++; } // mode is the index with maximum count int mode = 0 ; int k = count[ 0 ]; for ( int i = 1 ; i < t; i++) { if (count[i] > k) { k = count[i]; mode = i; } } // Update count[] array with sum for ( int i = 1 ; i < t; i++) { count[i] = count[i] + count[i - 1 ]; } // Sorted output array b[] // to calculate median for ( int i = 0 ; i < n; i++) { b[count[a[i]] - 1 ] = a[i]; count[a[i]]--; } // Median according to odd and even // array size respectively. float median; if (n % 2 != 0 ) { median = b[n / 2 ]; } else { median = ( float ) ((b[(n - 1 ) / 2 ] + b[(n / 2 )]) / 2.0 ); } // Output the result System.out.println( "median = " + median); System.out.println( "mode = " + mode); } // Driver program public static void main(String[] args) { int a[] = { 1 , 4 , 1 , 2 , 7 , 1 , 2 , 5 , 3 , 6 }; int n = a.length; printModeMedian(a, n); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for Mode and Median # using Counting Sort technique # Function that sort input array a[] and # calculate mode and median using counting sort def printModeMedian(a, n): # The output array b[] will # have sorted array b = [ 0 ] * n # Variable to store max of input array # which will to have size of count array Max = max (a) # Auxiliary(count) array to store count. # Initialize count array as 0. Size of # count array will be equal to (max + 1). t = Max + 1 count = [ 0 ] * t # Store count of each element # of input array for i in range (n): count[a[i]] + = 1 # Mode is the index with maximum count mode = 0 k = count[ 0 ] for i in range ( 1 , t): if (count[i] > k): k = count[i] mode = i # Update count[] array with sum for i in range ( 1 , t): count[i] = count[i] + count[i - 1 ] # Sorted output array b[] # to calculate median for i in range (n): b[count[a[i]] - 1 ] = a[i] count[a[i]] - = 1 # Median according to odd and even # array size respectively. median = 0.0 if (n % 2 ! = 0 ): median = b[n / / 2 ] else : median = ((b[(n - 1 ) / / 2 ] + b[n / / 2 ]) / 2.0 ) # Output the result print ( "median =" , median) print ( "mode =" , mode) # Driver Code if __name__ = = '__main__' : arr = [ 1 , 4 , 1 , 2 , 7 , 1 , 2 , 5 , 3 , 6 ] n = len (arr) printModeMedian(arr, n) # This code is contributed by himanshu77 |
C#
// C# Program for Mode and // Median using Counting // Sort technique using System; using System.Linq; class GFG { // function that sort input array a[] and // calculate mode and median using counting // sort. static void printModeMedian( int []a, int n) { // The output array b[] will // have sorted array int [] b = new int [n]; // variable to store max of // input array which will // to have size of count array int max = a.Max(); // auxiliary(count) array to // store count. Initialize // count array as 0. Size // of count array will be // equal to (max + 1). int t = max + 1; int []count = new int [t]; for ( int i = 0; i < t; i++) { count[i] = 0; } // Store count of each element // of input array for ( int i = 0; i < n; i++) { count[a[i]]++; } // mode is the index with maximum count int mode = 0; int k = count[0]; for ( int i = 1; i < t; i++) { if (count[i] > k) { k = count[i]; mode = i; } } // Update count[] array with sum for ( int i = 1; i < t; i++) { count[i] = count[i] + count[i - 1]; } // Sorted output array b[] // to calculate median for ( int i = 0; i < n; i++) { b[count[a[i]] - 1] = a[i]; count[a[i]]--; } // Median according to odd and even // array size respectively. float median; if (n % 2 != 0) { median = b[n / 2]; } else { median = ( float ) ((b[(n - 1) / 2] + b[(n / 2)]) / 2.0); } // Output the result Console.WriteLine( "median = " + median); Console.WriteLine( "mode = " + mode); } // Driver Code public static void Main(String[] args) { int []a = {1, 4, 1, 2, 7, 1, 2, 5, 3, 6}; int n = a.Length; printModeMedian(a, n); } } // This code is contributed by Rajput-Ji |
PHP
<?php // PHP Program for Mode and Median using // Counting Sort technique // Function that sort input array a[] and // calculate mode and median using counting // sort. function printModeMedian( $a , $n ) { // The output array b[] will // have sorted array $b [ $n ] = array (); // variable to store max of input // array which will to have size // of count array $max = max( $a ); // auxiliary(count) array to store // count. Initialize count array as // 0. Size of count array will be // equal to (max + 1). $t = $max + 1; $count [ $t ] = array (); for ( $i = 0; $i < $t ; $i ++) $count [ $i ] = 0; // Store count of each element // of input array for ( $i = 0; $i < $n ; $i ++) $count [ $a [ $i ]]++; // mode is the index with maximum count $mode = 0; $k = $count [0]; for ( $i = 1; $i < $t ; $i ++) { if ( $count [ $i ] > $k ) { $k = $count [ $i ]; $mode = $i ; } } // Update count[] array with sum for ( $i = 1; $i < $t ; $i ++) $count [ $i ] = $count [ $i ] + $count [ $i - 1]; // Sorted output array b[] // to calculate median for ( $i = 0; $i < $n ; $i ++) { $b [ $count [ $a [ $i ]] - 1] = $a [ $i ]; $count [ $a [ $i ]]--; } // Median according to odd and even // array size respectively. $median ; if ( $n % 2 != 0) $median = $b [ $n / 2]; else $median = ( $b [( $n - 1) / 2] + $b [( $n / 2)]) / 2.0; // Output the result echo "median = " , $median , "\n" ; echo "mode = " , $mode ; } // Driver Code $a = array ( 1, 4, 1, 2, 7, 1, 2, 5, 3, 6 ); $n = sizeof( $a ); printModeMedian( $a , $n ); // This code is contributed by jit_t ?> |
Javascript
// JavaScript program for Mode and Median // using Counting Sort technique // Function that sort input array a[] and // calculate mode and median using counting sort function printModeMedian(a, n) { // The output array b[] will // have sorted array let b = new Array(n).fill(0); // Variable to store max of input array // which will to have size of count array let Max = Math.max(...a); // Auxiliary(count) array to store count. // Initialize count array as 0. Size of // count array will be equal to (max + 1). let t = Max + 1; let count = new Array(t).fill(0); // Store count of each element // of input array for (let i = 0; i < n; i++) { count[a[i]] += 1; } // Mode is the index with maximum count let mode = 0; let k = count[0]; for (let i = 1; i < t; i++) { if (count[i] > k) { k = count[i]; mode = i; } } // Update count[] array with sum for (let i = 1; i < t; i++) { count[i] = count[i] + count[i - 1]; } // Sorted output array b[] // to calculate median for (let i = n - 1; i >= 0; i--) { b[count[a[i]] - 1] = a[i]; count[a[i]] -= 1; } // Median according to odd and even // array size respectively. let median = 0.0; if (n % 2 !== 0) { median = b[Math.floor(n / 2)]; } else { median = (b[Math.floor((n - 1) / 2)] + b[Math.floor(n / 2)]) / 2.0; } // Output the result console.log( "median =" , median); console.log( "mode =" , mode); } // Driver Code let arr = [1, 4, 1, 2, 7, 1, 2, 5, 3, 6]; let n = arr.length; printModeMedian(arr, n); // This code is contributed by phasing17 |
median = 2.5 mode = 1
Time Complexity = O(N + P), where N is the time for input array and P is time for count array.
Space Complexity = O(P), where P is the size of auxiliary array.