я надеюсь что это не плагиат, потому что этот алгоритм я придумал сам (из-за того что я сначала не правильно понял оригинальный TreeSort)
эта сортировка обгоняет QuickSort при выриантах значений меньше чем 5000... при 5000 скорости сравниваются
конечно сортировка черпаками быстрее но просто кому нить будет интересно
и так, вот алгоритм (написан на C#)
class sealed Sort
{
private Sort(){}
public static void TreeSort(int[] a)
{
if (a.Length<2)
return;
Node root=new Node(a[0]);
for(int i=1; i<a.Length; i++)
AddNode(root,a[i]);
int k=0;
ComputeNode(root,a,ref k);
}
private static void ComputeNode(Node nd, int[] a, ref int k)
{
if (nd.min!=null)
ComputeNode(nd.min,a,ref k);
for(int i=0; i<nd.cnt; i++)
a[k++]=nd.val;
if(nd.max!=null)
ComputeNode(nd.max,a,ref k);
}
private static void AddNode(Node nd, int value)
{
if (nd.val>value)
if (nd.min==null)
nd.min=new Node(value);
else
AddNode(nd.min,value);
else if (nd.val==value)
nd.cnt++;
else
if (nd.max==null)
nd.max=new Node(value);
else
AddNode(nd.max,value);
}
class Node
{
public int val, cnt=1;
public Node min, max;
public Node(int value)
{
val=value;
}
}
}
Здравствуйте, uniqSnk, Вы писали:
S>я надеюсь что это не плагиат, потому что этот алгоритм я придумал сам (из-за того что я сначала не правильно понял оригинальный TreeSort)
S>эта сортировка обгоняет QuickSort при выриантах значений меньше чем 5000... при 5000 скорости сравниваются
S>конечно сортировка черпаками быстрее но просто кому нить будет интересно
S>и так, вот алгоритм (написан на C#)
S>S>class sealed Sort
S>{
S> private Sort(){}
S> public static void TreeSort(int[] a)
S> {
S> if (a.Length<2)
S> return;
S> Node root=new Node(a[0]);
S> for(int i=1; i<a.Length; i++)
S> AddNode(root,a[i]);
S> int k=0;
S> ComputeNode(root,a,ref k);
S> }
S> private static void ComputeNode(Node nd, int[] a, ref int k)
S> {
S> if (nd.min!=null)
S> ComputeNode(nd.min,a,ref k);
S> for(int i=0; i<nd.cnt; i++)
S> a[k++]=nd.val;
S> if(nd.max!=null)
S> ComputeNode(nd.max,a,ref k);
S> }
S> private static void AddNode(Node nd, int value)
S> {
S> if (nd.val>value)
S> if (nd.min==null)
S> nd.min=new Node(value);
S> else
S> AddNode(nd.min,value);
S> else if (nd.val==value)
S> nd.cnt++;
S> else
S> if (nd.max==null)
S> nd.max=new Node(value);
S> else
S> AddNode(nd.max,value);
S> }
S> class Node
S> {
S> public int val, cnt=1;
S> public Node min, max;
S> public Node(int value)
S> {
S> val=value;
S> }
S> }
S>}
S>
Может я чего-то не понял, но сложность этой сортировки в худшем случае O(n^2). Например, если взять возрастающую последовательность, то это поисковое дерево вытянется в список. А обгон quick sort получается, видимо, только из-за хранения количества одинаковых чисел и большого количества одинаковых чисел в тестах.
... << RSDN@Home 1.1.4 beta 7 rev. 447>>
