# Programming Pearls: Column11-12

## Book notes

### QuickSort

void swap(int *array, int m, int n) {
int temp;
temp = array[m];
array[m] = array[n];
array[n] = temp;
}

int randint(int m, int n) {
return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

void isort(int *array, int n) {
int i, j, t;
for (i = 1; i < n; ++i) {
t = array[i];
for (j = i; j >= 0  && array[j - 1] < t; --j) {
array[j] = array[j - 1];
}
array[j - 1] = t;
}
}

void qsort1(int *array, int l, int u) {
/*use array[l] for the mid element */
if (l >= u) {
return;
}
int m;
m = l;
for (int i = l + 1; i <= u; ++i) {
if (array[i] < array[l]) {
swap(array, ++m, i);
}
}
swap(array, l, m);
qsort1(array, l, m - 1);
qsort1(array, m + 1, u);
}

void qsort2(int *array, int l, int u) {
/*use array[l] for the mid element, from back to start,
always swap the first element */
if (l >= u) {
return;
}
int i, m;
i = m = u + 1;
do {
do {
--i;
} while (array[i] < array[l]);
swap(array, --m, i);
} while (i > l);
qsort2(array, l, m - 1);
qsort2(array, m + 1, u);
}

void qsort3(int *array, int l, int u) {
/* two-way partition, use array[l] for the mid element */
if (l >= u) {
return;
}
int t, i , j;
t = array[l];
i = l;
j = u + 1;
for (;;) {
do {
++i;
} while (i <= u && array[i] < t);
do {
--j;
} while (array[j] > t);
if (i > j) {
break;
}
swap(array, i, j);
}
swap(array, l, j);
qsort3(array, l, j - 1);
qsort3(array, j + 1, u);
}

const int kCutOff = 50;
void qsort4(int *array, int l, int u) {
/* qsort3 + randomization + isort small subarrays + swap inline */
if (u - l < kCutOff) {
return;
}
int t, i , j;
swap(array, l, randint(l, u));
t = array[l];
i = l;
j = u + 1;
for (;;) {
do {
++i;
} while (i <= u && array[i] < t);
do {
--j;
} while (array[j] > t);
if (i > j) {
break;
}
swap(array, i, j);
}
swap(array, l, j);
qsort3(array, l, j - 1);
qsort3(array, j + 1, u);
}


### 生成随机数

#### 1

void GenerateSortedRand(int m, int n) {
int select = m;
int remaining = n;
for (int i = 0; i < n && select > 0; ++i) {
if (rand() % remaining < select) {
cout << i << " ";
--select;
}
--remaining;
}
cout << endl;
}


#### 2

void GenKnuth(int m, int n) {
for (int i = 0; i < n && m > 0; ++i) {
if (rand() % (n - i) < m) {
cout << i << " ";
--m;
}
}
cout << endl;
}


#### 3

void GenSets(int m, int n) {
set<int> num_set;
while (num_set.size() < m) {
num_set.insert(rand() % n);
}
for (set<int>::iterator it = num_set.begin(); it != num_set.end(); ++it) {
cout << *it << " ";
}
cout << endl;
}


#### 4

int randint(int m, int n) {
return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

int compare(const void *a, const void *b) {
return (*static_cast<const int*>(a) - *static_cast<const int*>(b));
}

void GenShuf(int m, int n) {
int *x = new int[n];
int i = 0;
for (i = 0; i < n; ++i) {
x[i] = i;
}
for (i = 0; i < m; ++i) {
int j = randint(i, n - 1);
int t = x[j];
x[j] = x[i];
x[i] = t;
}
qsort(x, m, sizeof(int), compare);
for (i = 0; i < m; ++i) {
cout << x[i] << " ";
}
cout << endl;
delete x;
}


### 原则

• 理解问题。与用户讨论提出问题的有关场景。问题的陈述中往往包含问题的想法，和所有早期的想法一样，它们应该被考虑而不是与其他排斥。
• 指出一个抽象问题。一个清晰，整洁的问题陈述不旦帮助我们解决这个问题，并且能体现如何把这个解答应用到其他的问题上。
• 探索设计空间。不要急于立刻去解决问题，思考一分钟，花一天时间编程。应该思考一小时，编程一小时。使用通俗的上层语言帮助我们描述设计：伪代码描述控制六，抽象化表示关键数据结构的数据类型。
• 实现一种解答。我们应该追求以直接清晰的代码来实现选择的设计，使用最强大的能用的操作。
• 回顾。Polya 的How to Solve It能帮助任何程序员成为更好的问题解决者。在 15 页他说：”基本存在一些东西去做，随着足够的学习和突破，我们能改善每个解答，并且在任何情况下，我们都能经常改善我们对解答的理解。“

## Problems

### Column11-9

void swap(int *array, int m, int n) {
int temp;
temp = array[m];
array[m] = array[n];
array[n] = temp;
}

int randint(int m, int n) {
return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

void SelectK(int *array, int l, int u, int k) {
if (l >= u) {
return;
}
int t, i, j;
swap(array, l, randint(l, u));
t = array[l];
i = l;
j = u + 1;
for (;;) {
do {
++i;
} while (i <= u && array[i] < t);
do {
--j;
} while (array[j] > t);
if (i > j) {
break;
}
swap(array, i, j);
}
swap(array, l, j);
if (j < k) {
SelectK(array, j + 1, u, k);
}
else if (j > k) {
SelectK(array, l, j - 1, k);
}
}


### 1

int randint(int m, int n) {
return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

int bigrand() {
return RAND_MAX * rand() + rand();
}


### 2

int randint(int m, int n) {
return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

void GenerateM(int m, int n) {
int i, t;
i = randint(0, n - 1);
for(int j = 0; j < m; ++j) {
t = i + j;
if (t >= n) {
t -= n;
}
cout << t << " " << endl;
}
cout << endl;
}


### 8

0..n-1 中生成 m 个随机数。

int randint(int m, int n) {
return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

int compare(const void *a, const void *b) {
return (*static_cast<const int*>(a) - *static_cast<const int*>(b));
}

void GenShuf(int m, int n) {
int *x = new int[n];
int i = 0;
for (i = 0; i < n; ++i) {
x[i] = i;
}
for (i = 0; i < m; ++i) {
int j = randint(i, n - 1);
int t = x[j];
x[j] = x[i];
x[i] = t;
}

for (i = 0; i < m; ++i) {
cout << x[i] << " ";
}
cout << endl;
delete x;
}


void GenSets(int m, int n) {
multiset<int> num_set;
while (num_set.size() < m) {
num_set.insert(rand() % n);
}
for (multiset<int>::iterator it = num_set.begin(); it != num_set.end();
++it) {
cout << *it << " ";
}
cout << endl;
}


void GenM(int m, int n) {
for (int i = 0; i < m; ++i) {
cout << randint(0, n - 1) << " ";
}
cout << endl;
}


### 9

int randint(int m, int n) {
return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

void GenSets(int m, int n) {
set<int> num_set;
int t;
for (int i = n - m ; i < n; ++i) {
t = randint(0, i);
if (num_set.find(t) == num_set.end()) {
num_set.insert(t);
} else {
num_set.insert(i);
}
}
for (set<int>::iterator it = num_set.begin(); it != num_set.end(); ++it) {
cout << *it << " ";
}
cout << endl;
}


### 10

int randint(int m, int n) {
return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

int Select() {
int res;
int i = 0;
res = object[i];
++i;
while (IsEnd(object[i])) {
int j = randint(0, i);
if (j < 1) {
res = object[i];
}
++i;
}
return res;
}


More: 选 k 个