/* Quick Sort, Partition Exchange Sort - Recursive */
#include
#include
#define MAXNOS 100 /* Macro definition for maximum numbers to be input */
void quick(int [], int, int); /* sorting function prototype declaration */
void partition(int [], int, int, int *); /* function required for */
/* creating left and right partitions in the array around the pivot */
void main(void)
{
int a[MAXNOS]; /* array to hold the input numbers */
int m; /* stores the total count of input numbers */
int i; /* for loop variable */
input : /* label name for transfer of control through goto */
clrscr();
printf("Quick Sort OR Partition Exchange Sort - Recursive\n");
printf("----- ---- -- --------- -------- ---- - ---------\n\n");
printf("Enter how many numbers will be input for sorting - ");
flushall();
scanf("%d", &m);
if (m < 2 || m > MAXNOS) /* check for valid input */
{
printf("Error - input value is out of range...");
getch();
goto input;
}
printf("Enter the numbers one by one -\n");
for (i=0; i {
printf("%2d - ", (i+1));
flushall();
scanf("%d", &a[i]);
}
quick(a, 0, (m-1)); /* function is invoked for sorting the numbers */
printf("\n\nSorted numbers are - \n");
for (i=0; i printf("%d\t", a[i]); /* sorted numbers are displayed on the screen */
getch();
}
void quick(int x[], int lb, int ub) /* lb & ub are lower & upper bounds */
{
int j; /* used to obtain the position of the pivot */
if (lb >= ub) /* if partition size is equal to 1 or left & right */
{ /* partitions have merged into each other then stop */
return; /* partitioning process. */
}
partition(x, lb, ub, &j); /* call the partitioning function */
quick(x, lb, (j-1)); /* process the left partition recursively */
quick(x, (j+1), ub); /* process the right partition recursively */
}
void partition(int x[], int lb, int ub, int *pj)
{
int pivot; /* stores the pivot value */
int down; /* pointer which moves from left to right in the array */
int up; /* pointer which moves from right to left in the array */
int hold; /* temporary storage variable */
pivot = x[lb]; /* the leftmost first value is chosen as the pivot */
down = lb; /* set the pointer to the lower bound */
up = ub; /* set the pointer to the upper bound */
while (down < up) /* check if pointers have crossed each other */
{
while (x[down] <= pivot && down < ub) /* the left partition must */
{ /* contain values less than or equal to the pivot and */
/* down pointer must be less than the upper bound */
down++; /* increment the down pointer */
} /* end of while loop for down */
while (x[up] > pivot) /* Right partition must contain values */
{ /* greater than the pivot */
up--; /* decrement the up pointer */
} /* end of while loop for up */
if (down < up) /* check if pointers have not crossed over */
{
hold = x[down]; /* swap values across partitions if they are */
x[down] = x[up]; /* wrongly placed */
x[up] = hold;
} /* end of if for down < up */
} /* end of while loop for creating left and right partitions */
x[lb] = x[up]; /* swap the up value with the pivot value */
x[up] = pivot;
*pj = up; /* store position of pivot equal to up pointer value */
} /* end of partition function */
#include
#include
#define MAXNOS 100 /* Macro definition for maximum numbers to be input */
void quick(int [], int, int); /* sorting function prototype declaration */
void partition(int [], int, int, int *); /* function required for */
/* creating left and right partitions in the array around the pivot */
void main(void)
{
int a[MAXNOS]; /* array to hold the input numbers */
int m; /* stores the total count of input numbers */
int i; /* for loop variable */
input : /* label name for transfer of control through goto */
clrscr();
printf("Quick Sort OR Partition Exchange Sort - Recursive\n");
printf("----- ---- -- --------- -------- ---- - ---------\n\n");
printf("Enter how many numbers will be input for sorting - ");
flushall();
scanf("%d", &m);
if (m < 2 || m > MAXNOS) /* check for valid input */
{
printf("Error - input value is out of range...");
getch();
goto input;
}
printf("Enter the numbers one by one -\n");
for (i=0; i
printf("%2d - ", (i+1));
flushall();
scanf("%d", &a[i]);
}
quick(a, 0, (m-1)); /* function is invoked for sorting the numbers */
printf("\n\nSorted numbers are - \n");
for (i=0; i
getch();
}
void quick(int x[], int lb, int ub) /* lb & ub are lower & upper bounds */
{
int j; /* used to obtain the position of the pivot */
if (lb >= ub) /* if partition size is equal to 1 or left & right */
{ /* partitions have merged into each other then stop */
return; /* partitioning process. */
}
partition(x, lb, ub, &j); /* call the partitioning function */
quick(x, lb, (j-1)); /* process the left partition recursively */
quick(x, (j+1), ub); /* process the right partition recursively */
}
void partition(int x[], int lb, int ub, int *pj)
{
int pivot; /* stores the pivot value */
int down; /* pointer which moves from left to right in the array */
int up; /* pointer which moves from right to left in the array */
int hold; /* temporary storage variable */
pivot = x[lb]; /* the leftmost first value is chosen as the pivot */
down = lb; /* set the pointer to the lower bound */
up = ub; /* set the pointer to the upper bound */
while (down < up) /* check if pointers have crossed each other */
{
while (x[down] <= pivot && down < ub) /* the left partition must */
{ /* contain values less than or equal to the pivot and */
/* down pointer must be less than the upper bound */
down++; /* increment the down pointer */
} /* end of while loop for down */
while (x[up] > pivot) /* Right partition must contain values */
{ /* greater than the pivot */
up--; /* decrement the up pointer */
} /* end of while loop for up */
if (down < up) /* check if pointers have not crossed over */
{
hold = x[down]; /* swap values across partitions if they are */
x[down] = x[up]; /* wrongly placed */
x[up] = hold;
} /* end of if for down < up */
} /* end of while loop for creating left and right partitions */
x[lb] = x[up]; /* swap the up value with the pivot value */
x[up] = pivot;
*pj = up; /* store position of pivot equal to up pointer value */
} /* end of partition function */