苗火 Nicholas

[Data Structures]Selection sort

2019-5-17 萧 写技术

#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");


}

标签: Data Structures data_structures