/*****************************************************************************
* sort.c
*
* Implementation for sort algorithms.
*
* Qch, 2011-05
*****************************************************************************/
#include
#include
typedef int bool;
#define true 1
#define false 0
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
/**
* Bubble sort algorithm.
* "a" ----> array of Comparable items.
* "left" ----> the left-most index of the subarray.
* "right" ----> the right-most index of the subarray.
*/
void bubbleSort(int *a, int left, int right)
{
bool cond = true;
int i,j;
for (i = left; i < right; ++i)
{
cond = false;
for (j = right; j > i; --j)
if (a[j] < a[j - 1])
{
swap(&a[j], &a[j - 1]);
cond = true;
}
if (!cond)
return;
}
}
/**
* Selection sort algorithm.
* "a" ----> array of Comparable items.
* "left" ----> the left-most index of the subarray.
* "right" ----> the right-most index of the subarray.
*/
void selectSort(int *a, int left, int right)
{
int minPos;
int i,j;
for (i = left; i < right; ++i)
{
minPos = i;
for (j = i + 1; j <= right; ++j)
if (a[j] < a[minPos])
minPos = j;
if (i != minPos)
swap(&a[i], &a[minPos]);
}
}
/**
* Insertion sort algorithm.
* "a" ----> array of Comparable items.
* "left" ----> the left-most index of the subarray.
* "right" ----> the right-most index of the subarray.
*/
void insertSort(int *a, int left, int right)
{
int p;
for (p = left + 1; p <= right; p++)
{
int tmp = a[p];
int j;
for (j = p; j > left && tmp < a[j - 1]; --j)
a[j] = a[j - 1];
a[j] = tmp;
}
}
/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 20.
* "a" ----> array of Comparable items.
* "left" ----> the left-most index of the subarray.
* "right" ----> the right-most index of the subarray.
*/
int median3(int *a, int left, int right);
void quickSort(int *a, int left, int right)
{
if (left + 20 <= right)
{
int pivot = median3(a, left, right);
// begin partitioning
int i = left, j = right - 1;
for (;;)
{
while (a[++i] < pivot)
{
}
while (pivot < a[--j])
{
}
if (i < j)
swap(&a[i], &a[j]);
else
break;
}
// Restore pivot
swap(&a[i], &a[right - 1]);
// Sort small elements
quickSort(a, left, i - 1);
// Sort large elements
quickSort(a, i + 1, right);
}
else
insertSort(a, left, right);
}
/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
int median3(int *a, int left, int right)
{
int center = (left + right) / 2;
if (a[center] < a[left])
swap(&a[left], &a[center]);
if (a[right] < a[left])
swap(&a[left], &a[right]);
if (a[right] < a[center])
swap(&a[center], &a[right]);
swap(&a[center], &a[right - 1]);
return a[right - 1];
}
/**
* Merg sort algorithm (nonrecursion).
* "a" ----> array of Comparable items.
* "start" ----> the left-most index of the subarray.
* "end" ----> the right-most index of the subarray.
*/
void merge(int *a,int start, int mid, int end);
void mergSort(int *a,int start, int end)
{
int mid;
if (start < end) {
mid = (start + end) / 2;
//printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n",
// start, mid, mid+1, end,
// a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
mergSort(a,start, mid);
mergSort(a,mid+1, end);
merge(a,start, mid, end);
//printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\n",
// start, mid, mid+1, end,
// a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
}
}
/**
* Merg two subsequence to a bigger one.
* The first subsequence is a[start] ... a[mid-1], and
* The second subsqeuence is a[mid] ... a[end].
*/
void merge(int *a,int start, int mid, int end)
{
int n1 = mid - start + 1;
int n2 = end - mid;
//int left[n1], right[n2];
int *left=(int *)malloc(n1*sizeof(int));
int *right=(int *)malloc(n2*sizeof(int));
int i, j, k;
for (i = 0; i < n1; i++) /* left holds a[start..mid] */
left[i] = a[start+i];
for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
right[j] = a[mid+1+j];
i = 0;
j = 0;
k = start;
while (i < n1 && j < n2)
if (left[i] < right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
while (i < n1) /* left[] is not exhausted */
a[k++] = left[i++];
while (j < n2) /* right[] is not exhausted */
a[k++] = right[j++];
free(left);
free(right);
}
/**
* Heap sort algorthm.
* "a" ----> array of Comparable items.
* "left" ----> the left-most index of the subarray.
* "right" ----> the right-most index of the subarray.
*/
void filterDown(int *a, int i, int n);
void heapSort(int *a, int left, int right)
{
int n = right - left + 1;
//int tmp[n];
int *tmp=(int *)malloc(n*sizeof(int));
int i,j;
for (i = 0; i < n; ++i)
tmp[i] = a[left + i];
for (i = n / 2; i >= 0; --i)
filterDown(tmp, i, n);
for (j = n - 1; j > 0; --j)
{
swap(&tmp[0], &tmp[j]);
filterDown(tmp, 0, j);
}
for (i = 0; i < n; ++i)
a[left + i] = tmp[i];
free(tmp);
}
/**
* Percolate down the heap.
* "i" ----> the position from which to percolate down.
* "n" ----> the logical size of the binary heap.
*/
void filterDown(int *a, int i, int n)
{
int child;
int tmp;
for (tmp = a[i]; 2 * i + 1 < n; i = child)
{
child = 2 * i + 1;
if (child != n - 1 && a[child] < a[child + 1])
child++;
if (tmp < a[child])
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
int main()
{
int d[] =
{ 7, 5, 6, 4, 2, 3, 1, 9, 8 };
int n,opt=0;
for (n = 0; n < sizeof(d) / sizeof(int); n++)
printf("%d", d[n]);
printf("\n");
//int opt = 0;
printf("1 bubbleSort\n");
printf("2 selectSort\n");
printf("3 insertSort\n");
printf("4 quickSort\n");
printf("5 mergSort\n");
printf("6 heapSort\n");
printf("option:");
scanf("%d",&opt);
printf("\n");
switch (opt)
{
case 1:
bubbleSort(d, 0, 9);
break;
case 2:
selectSort(d, 0, 9);
break;
case 3:
insertSort(d, 0, 9);
break;
case 4:
quickSort(d, 0, 9);
break;
case 5:
mergSort(d, 0, 9);
break;
case 6:
heapSort(d, 0, 9);
break;
default:
printf("input error!\n");
exit(1);
}
for (n = 0; n < sizeof(d) / sizeof(int); n++)
printf("%d", d[n]);
}