苗火 Nicholas

[Data Structures] Swap sort

2019-4-28 萧 写技术

#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int seq[], int n)
{
	int i;
	int j;
	int tmp;
	int exchange;
	for (i=0; i<n; i++) {
		exchange = 0;
		for (j=n; j>i; j--) {
			if (seq[j] < seq[j-1]) {
				/* swap j and j-1 */
				tmp = seq[j];
				seq[j] = seq[j-1];
				seq[j-1] = tmp;

				exchange = 1;
			}	
		}
		if (exchange == 0) {
			return;
		}
	}		
}

int partition(int seq[], int n, int low, int high) {
	int i;
	int pivot = seq[low];
	int tmp;
	int k=low;
	for (i=low+1; i<=high; i++) {
		if (seq[i] < pivot) {
			k++;

			/* swap k and i */		
			tmp = seq[k];
			seq[k] = seq[i];
			seq[i] = tmp;
		}
	}
	
	/* swap k and low */
	seq[low] = seq[k];
	seq[k] = pivot;
	return k;
}

void quickSort(int seq[], int n, int low, int high) {
	int pivotPos;
	if (low < high) {
		pivotPos = partition(seq, n, low, high);
		quickSort(seq, n, low, pivotPos-1);	
		quickSort(seq, n, pivotPos+1, high);
	}
}

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("Bubble sort: \n");
	printf("Seq:\n");
	for (i=0; i<n; i++) {
		printf(" %2d", seq[i]);
	}	
	printf("\n");
	bubbleSort(seq, n);
	for (i=0; i<n; i++) {
		printf(" %2d", seq[i]);
	}	
	printf("\n");

	printf("Quick sort: \n");
	printf("Seq:\n");
	for (i=0; i<n; i++) {
		seq[i] = ancient[i];
		printf(" %2d", seq[i]);
	}
	printf("\n");
	quickSort(seq, n, 0, n-1);
	for (i=0; i<n; i++) {
		printf(" %2d", seq[i]);
	}	
	printf("\n");
}

标签: data_structures