#include <stdio.h>
#include <stdlib.h>
#define MAX 65535
void simpleSelectionSort(int seq[], int n)
{
int i;
int j;
int min;
int exchange;
for (i=0; i<n; i++) {
min = MAX;
/* Get the least number */
for (j=i; j<n; j++) {
if (seq[j] < min) {
min = seq[j];
exchange = j;
}
}
if(exchange != i){
/* Swap */
min = seq[i];
seq[i] = seq[exchange];
seq[exchange] = min;
}
}
}
void treeSelectionSort(int seq[], int n){
int q[100];
int q_data[100];
int idx;
int len;
int leaves = 0;
int level;
int remain;
int second_level_leves;
int parent;
int left;
int right;
int i;
int j;
/* Count level of the tree */
leaves = 1;
level = 1;
while(leaves < n){
leaves *= 2;
level++;
}
/* How many leaves remained after put all the numbers on the botton of the tree */
remain = leaves - n;
/* How many leaves can set in the last second level */
remain = remain / 2;
second_level_leves = 0;
leaves = n;
while(remain>0){
/* Leaves move to remain position */
remain--;
if(leaves%2==1){
/* If remove a left child, get a new remained position. */
remain++;
}
leaves--;
}
/* Total nodes */
len = 1;
for(i=2;i<=level;i++){
len *= 2;
}
/* Total node = exp leaves - 1 */
len--;
len += leaves;
for(i=0;i<len;i++){
q[i] = i;
}
for(i=len-1; i>0; i--){
parent = (i-1)/2;
if(i%2==0){
/* right child */
if(seq[len-q[i-1]-1] < seq[len-q[i]-1]){
q[parent] = q[i-1];
}else{
q[parent] = q[i];
}
i--;
}else{
/* left child */
q[parent] = q[i];
}
}
idx = 0;
for(j=0; j<n; j++){
i = q[0];
q_data[idx++] = seq[ len-q[i]-1 ];
seq[ len-q[i]-1 ] = MAX;
while(i>0){
parent = (i-1)/2;
if(i%2==0){
/* right child */
if(seq[ len-q[i-1]-1 ] < seq[ len-q[i]-1 ]){
q[parent] = q[i-1];
}else{
q[parent] = q[i];
}
}else{
/* left child */
if(i+1<len){
if(seq[ len-q[i]-1 ] < seq[ len-q[i+1]-1 ]){
q[parent] = q[i];
}else{
q[parent] = q[i+1];
}
}else{
q[parent] = q[i];
}
}
i = parent;
}
}
for(i=0;i<n;i++){
seq[i] = q_data[i];
}
return;
}
void main()
{
int ancient[] = {1,9,1,2,3,4,4,5,5,7,8,9,10};
int seq[] = {1,9,1,2,3,4,4,5,5,7,8,9,10};
int n = sizeof(seq)/sizeof(int);
int i;
printf("Simple selection sort: \n");
printf("Seq:\n");
for (i=0; i<n; i++) {
seq[i] = ancient[i];
printf(" %2d", seq[i]);
}
printf("\n");
simpleSelectionSort(seq, n);
for (i=0; i<n; i++) {
printf(" %2d", seq[i]);
}
printf("\n");
printf("Tree Selection sort: \n");
printf("Seq:\n");
for (i=0; i<n; i++) {
seq[i] = ancient[i];
printf(" %2d", seq[i]);
}
printf("\n");
treeSelectionSort(seq, n);
for (i=0; i<n; i++) {
printf(" %2d", seq[i]);
}
printf("\n");
}