ch3-shellsort (For characters and integers)

Chapter_3     Exercise_3-2

Exercise_3-3

---

---

shellsort     K&R, p. 62  (shellc.c,  shelli.c)

shellc.c     (for characters)     download

#include <stdio.h> // for printf(), scanf()

#define SIZE 100 // array size

int strLen(char []); // strlen() is declared in string.h, included by stdio.h

// sort v[0] ... v[n-1] into increasing order
void shellsort(char v[], int n);

int main()
{
char array[SIZE];

printf("Type a word: ");
scanf("%s", array);

shellsort(array, strLen(array));
printf("Sorted: %s\n", array);

return 0;
}

int strLen(char s[])
{
int i = 0;

while (s[i] != '\0')
{i++;}

return i;
}

// sort v[0] ... v[n-1] into increasing order
void shellsort(char v[], int n)
{
int gap, i, j, temp;

for (gap = n/2; gap > 0; gap /= 2)
{
for (i = gap; i < n; i++)
{
for (j = i-gap; j >= 0 && v[j] > v[j+gap]; j -= gap)
{ // interchange v[j], v[j+gap] using a temporary variable
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}
}
}
/*
gcc shellc.c -o shellc
./shellc
Type a word: abracadabra
Sorted: aaaaabbcdrr

./shellc
Type a word: hocus-pocus
Sorted: -cchoopssuu
*/

Note:  See also strlen in Chapter_2, Sec. 2.3.

---

---

shelli.c     (for integers)     download

#include <stdio.h> // for printf()

#define SIZE 100 // array size
#define SEED 24 // seed for rand()

unsigned long int next = 1; // global var used by rand()

int rand(void); // pseudo-random number generator
void srand(unsigned int seed); // set seed for rand()

// sort v[0] ... v[n-1] into increasing order
void shellsort(int v[], int n);

void printArray(int arr[], int n);

int main()
{
int array[SIZE];
int i;
srand(SEED);

for (i = 0; i < SIZE; i++)
{array[i] = rand();}

printf("Unsorted:\n");
printArray(array, SIZE);

shellsort(array, SIZE);
printf("\nSorted:\n");
printArray(array, SIZE);

return 0;
}

// return pseudo-random integer on 0..32767
int rand(void)
{
next = next * 1103515245 + 12345;

return (unsigned int)(next / 65536) % 32768;
}

void srand(unsigned int seed)
{
next = seed; // set seed for rand()
}

// sort v[0] ... v[n-1] into increasing order
void shellsort(int v[], int n)
{
int gap, i, j, temp;

for (gap = n/2; gap > 0; gap /= 2)
{
for (i = gap; i < n; i++)
{
for (j = i-gap; j >= 0 && v[j] > v[j+gap]; j -= gap)
{ // interchange v[j], v[j+gap] using a temporary variable
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}
}
}

void printArray(int arr[], int n)
{
int i;

for (i = 0; i < n; i++)
{
printf("%d%c", arr[i], ((i % 10) == 9) || (i == n-1) ? '\n' : ' ');
}
}
/*
gcc shelli.c -o shelli
./shelli
Unsorted:
10903 4890 13005 9985 9417 7879 19373 18922 11980 2947
13349 11897 22310 32244 26256 22527 21518 3349 24032 10771
11943 29378 26935 2553 26106 14595 7494 10959 17846 28696
32614 28797 27815 14664 18040 5466 16118 12906 19837 32415
16422 3632 5108 27532 4298 25911 26615 27484 3078 3023
5652 17897 16589 30858 15084 17183 17108 1926 4750 32034
3928 9850 24977 10559 405 13699 21491 916 4865 10412
28085 18814 25421 13887 26930 28357 17433 7630 8003 31113
17529 21504 21780 12524 30764 7965 3013 2685 30358 28759
11712 615 19843 1502 13789 19038 25498 8610 11319 31557

Sorted:
405 615 916 1502 1926 2553 2685 2947 3013 3023
3078 3349 3632 3928 4298 4750 4865 4890 5108 5466
5652 7494 7630 7879 7965 8003 8610 9417 9850 9985
10412 10559 10771 10903 10959 11319 11712 11897 11943 11980
12524 12906 13005 13349 13699 13789 13887 14595 14664 15084
16118 16422 16589 17108 17183 17433 17529 17846 17897 18040
18814 18922 19038 19373 19837 19843 21491 21504 21518 21780
22310 22527 24032 24977 25421 25498 25911 26106 26256 26615
26930 26935 27484 27532 27815 28085 28357 28696 28759 28797
29378 30358 30764 30858 31113 31557 32034 32244 32415 32614
*/

Note:  See also rand in Chapter_2, Sec. 2.7.

---

---

Chapter_3     Exercise_3-2

BACK_TO_TOP

Exercise_3-3