summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/lib7z/Sort.c
blob: 57559a5d580e42d9ae5d838a8f2bd3bcd54ee8bd (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/* Sort.c -- Sort functions
2010-09-17 : Igor Pavlov : Public domain */

#include "Sort.h"

#define HeapSortDown(p, k, size, temp) \
	{ for (;;) { \
	UInt32 s = (k << 1); \
	if (s > size) break; \
	if (s < size && p[s + 1] > p[s]) s++; \
	if (temp >= p[s]) break; \
	p[k] = p[s]; k = s; \
	} p[k] = temp; }

void HeapSort(UInt32 *p, UInt32 size)
{
	if (size <= 1)
	return;
	p--;
	{
	UInt32 i = size / 2;
	do
	{
		UInt32 temp = p[i];
		UInt32 k = i;
		HeapSortDown(p, k, size, temp)
	}
	while (--i != 0);
	}
	/*
	do
	{
	UInt32 k = 1;
	UInt32 temp = p[size];
	p[size--] = p[1];
	HeapSortDown(p, k, size, temp)
	}
	while (size > 1);
	*/
	while (size > 3)
	{
	UInt32 temp = p[size];
	UInt32 k = (p[3] > p[2]) ? 3 : 2;
	p[size--] = p[1];
	p[1] = p[k];
	HeapSortDown(p, k, size, temp)
	}
	{
	UInt32 temp = p[size];
	p[size] = p[1];
	if (size > 2 && p[2] < temp)
	{
		p[1] = p[2];
		p[2] = temp;
	}
	else
		p[1] = temp;
	}
}

/*
#define HeapSortRefDown(p, vals, n, size, temp) \
  { UInt32 k = n; UInt32 val = vals[temp]; for (;;) { \
    UInt32 s = (k << 1); \
    if (s > size) break; \
    if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
    if (val >= vals[p[s]]) break; \
    p[k] = p[s]; k = s; \
  } p[k] = temp; }

void HeapSortRef(UInt32 *p, UInt32 *vals, UInt32 size)
{
  if (size <= 1)
    return;
  p--;
  {
    UInt32 i = size / 2;
    do
    {
      UInt32 temp = p[i];
      HeapSortRefDown(p, vals, i, size, temp);
    }
    while (--i != 0);
  }
  do
  {
    UInt32 temp = p[size];
    p[size--] = p[1];
    HeapSortRefDown(p, vals, 1, size, temp);
  }
  while (size > 1);
}
*/