Problem: Sorting Elements of an Array by Frequency

*Difficulty: Easy

Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.

If frequencies of two elements are same, print them in increasing order.

 

Input:

The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, …, AN denoting the elements of the array.
Output:

Print each sorted array in a seperate line. For each array its numbers should be seperated by space.
Constraints:

1 ≤ T ≤ 70
30 ≤ N ≤ 130
1 ≤ A [ i ] ≤ 60
Example:

Input:

1
5
5 5 4 6 4

Output:

4 4 5 5 6

Implementation: Python 2.7

"""
    @author: loctv
    @time: 12:54PM January 5, 2017
"""

def get_frequency(data):
    """
        Get frequency of each element in data
    """
    frequency = {}
    for value in data:
        frequency[value] = frequency.setdefault(value, 0) + 1
    temp = list(frequency.keys())
    return temp, frequency

def merge_sort(data, frequency):
    if len(data) == 1:
        return data
    left_side = merge_sort(data[:len(data)//2], frequency)
    right_side = merge_sort(data[len(data)//2:], frequency)
    sorted_data = merge(left_side, right_side, frequency)
    return sorted_data

def merge(left, right, frequency):
    result, left_count, right_count = [], 0, 0
    while left_count < len(left) and right_count < len(right):
        if frequency[left[left_count]] > frequency[right[right_count]]:
            result.append(left[left_count])
            left_count += 1
        elif frequency[left[left_count]] < frequency[right[right_count]]:
            result.append(right[right_count])
            right_count += 1
        else: #equal frequency
            if left[left_count] < right[right_count]:
                result.append(left[left_count])
                left_count += 1
            else:
                result.append(right_count)
                right_count += 1
    while left_count < len(left):
        result.append(left[left_count])
        left_count += 1
    while right_count < len(right):
        result.append(right[right_count])
        right_count += 1
    return result

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = input()
        data = map(int, raw_input().strip().split())
        temp, frequency = get_frequency(data)
        temp = merge_sort(temp, frequency)
        res = []
        for _ in temp:
            res.extend([_]*frequency[_])
        print res
            
Advertisements