package org.wesome.dsalgo;
import java.util.Map;
import java.util.TreeMap;
public class SortArrayWithDuplicate {
public static int[] sortArrayWithDuplicate(int[] arr) {
Map<Integer, Integer> freqMap = new TreeMap<>();
/* Store the integer as key and its frequency as value in Tree Map */
for (int key : arr) {
freqMap.put(key, freqMap.getOrDefault(key, 0) + 1);
}
/* Tree Map sorts the key into natural order. */
int i = 0;
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
int value = entry.getValue();
while (value > 0) {
/* override the input array with key upto frequency times */
arr[i] = entry.getKey();
i++;
value--;
}
}
return arr;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
import static org.wesome.dsalgo.SortArrayWithDuplicate.sortArrayWithDuplicate;
public class SortArrayWithDuplicateTest {
@Test
public void sortArrayWithDuplicateTest() {
int[] arr = {30, 20, 40, 10, 30, 10, 40, 20, 10, 50, 40};
int[] sortedArr = {10, 10, 10, 20, 20, 30, 30, 40, 40, 40, 50};
Assertions.assertArrayEquals(sortedArr, sortArrayWithDuplicate(arr));
System.out.println(Arrays.toString(arr));
}
}
plugins {
id 'java'
id "io.freefair.lombok" version "6.2.0"
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}