package com.victor.sort.seeds;
import java.util.ArrayList;
public class FewUniqueKeys extends Seeds {
@Override
protected ArrayList<Integer> doGenerate(int size) {
ArrayList<Integer> seedsList = new ArrayList<Integer>();
int requiredSize = getSize();
java.util.Random rd = new java.util.Random();
int numberOfKeys = rd.nextInt(5) + 5;
int[] values = new int[numberOfKeys];
for(int i=0;i<numberOfKeys;i++)
{
values[i] = rd.nextInt(10000);
}
for(int i=0;i<requiredSize;i++)
{
int nextValue = rd.nextInt(requiredSize)%numberOfKeys;
seedsList.add(values[nextValue]);
}
return seedsList;
}
@Override
public String getDescriptions() {
return "Sorting an array that consists of a small number of unique keys is common in practice. " +
"One would like an algorithm that adapts to O(n) time when the number of unique keys is O(1). " +
"In this example, there are 4 unique keys. The traditional 2-way partitioning quicksort exhibits " +
"its worse-case O(n2) behavior here. For this reason, " +
"any quicksort implementation should use 3-way partitioning, " +
"where the array is partitioned into values less than, equal, " +
"and greater than the pivot. Because the pivot values need not be sorted recursively, " +
"3-way quick sort adapts to O(n) time in this case. Shell sort also adapts to few unique " +
"keys, though I do not know its time complexity in this case.";
}
@Override
public String getName() {
return "Few Unique Keys";
}
public static void main(String[] args)
{
Seeds rd = new FewUniqueKeys();
rd.setSize(100);
rd.generate();
rd.print();
}
}© 著作权归作者所有
举报
加载中
选择专区和圈子：{{title}}
{{o.name}}
{{m.name}}
公众号
视频号
问题反馈
深圳市奥思网络科技有限公司版权所有
粤ICP备12009483号
顶部