ch4-Quick sort

Chapter_4     Exercise_4-11     Print_decimal

Exercise_4-12

---

---

qsort.c     K&R, p. 87-88         download

#include <stdio.h> // for printf(), putchar()
#include <stdlib.h> // for srand(), rand()
#include <time.h> // for time_t, time()

#define SIZE 100 // array size

// sort v[left] ... v[right] into increasing order:
void qSort (int v[], int left, int right); // qsort() in declared in stdlib.h

int main()
{
int array[SIZE];
int i;
time_t t;

srand((unsigned) time(&t)); // seed for rand()
for (i = 0; i < SIZE; i++)
{array[i] = rand() % 1000;} // initialize array[]

printf("Unsorted:\n");
for (i = 0; i < SIZE; i++)
{
printf("%d%c", array[i], (i % 10) == 9 ? '\n' : ' ');
}
putchar('\n');

qSort(array, 0, SIZE-1);

printf("Sorted:\n");
for (i = 0; i < SIZE; i++)
{
printf("%d%c", array[i], (i % 10) == 9 ? '\n' : ' ');
}

return 0;
}

void swap(int v[], int i, int j); // swap v[i] and v[j]

// sort v[left] ... v[right] into increasing order:
void qSort (int v[], int left, int right)
{
int i, last;

if (left >= right) // do nothing if array contains fewer that
{return;} // two elements (stopping condition for recursion)

swap(v, left, (left + right) / 2); // move partition element to v[left]
last = left; // v[left] is now in the middle of v[left] ... v[right]

for (i = left+1; i <= right; i++)
{ // value of `left' does not change here
if (v[i] < v[left]) // compare v[left] ... v[right] to partition element
{swap(v, ++last, i);} // smaller to the left, bigger to the right
}

swap(v, left, last); // restore partition element
qSort(v, left, last-1); // recursive call (sort first half)
qSort(v, last+1, right); // recursive call (sort last half)
}

void swap(int v[], int i, int j) // swap v[i] and v[j]
{
int temp;

temp = v[i];
v[i] = v[j];
v[j] = temp;
}
/*
gcc qsort.c -o qsort
./qsort
Unsorted:
454 449 499 215 79 630 447 413 455 926
794 606 308 651 272 157 564 34 613 649
472 824 563 278 883 472 50 100 849 39
217 655 488 716 222 567 699 669 333 154
947 127 112 256 130 736 765 46 770 378
696 243 202 611 873 86 83 924 186 284
963 755 939 803 824 513 722 523 535 407
29 482 534 493 90 17 230 856 63 0
234 111 595 789 722 469 227 805 745 413
441 60 520 732 215 344 246 289 219 781

Sorted:
0 17 29 34 39 46 50 60 63 79
83 86 90 100 111 112 127 130 154 157
186 202 215 215 217 219 222 227 230 234
243 246 256 272 278 284 289 308 333 344
378 407 413 413 441 447 449 454 455 469
472 472 482 488 493 499 513 520 523 534
535 563 564 567 595 606 611 613 630 649
651 655 669 696 699 716 722 722 732 736
745 755 765 770 781 789 794 803 805 824
824 849 856 873 883 924 926 939 947 963
*/

Note:  See function_rand() on TutorialsPoint for the initialization of our int array.

---

---

Chapter_4     Exercise_4-11     Print_decimal

BACK_TO_TOP

Exercise_4-12