Phil Carmody
8/16/2011 11:25:00 AM
arnuld <sunrise@invalid.address> writes:
> Just wrote selection-sort in C. Is it the right way to do this in C ?
>
> (definition of selection-sort taken from exercise 2.2-2 of Introduction
> to Algorithms, 2e)
>
>
> /* Exercise 2.2-2, page 29, Selection Sort */
>
> #include <stdio.h>
>
> enum { SIZE_ARR = 6 };
>
> void selectionSort(char s[], int len);
> int findSmallest(char s[], const int idx_cur, const int len);
The consts on those parameters don't do much, but aren't actually
wrong.
>
>
> int main(void)
> {
> char arr[SIZE_ARR+1] = {'a', 'r', 'n', 'u', 'l', 'd'};
>
> printf("%s\n", arr);
> selectionSort(arr, SIZE_ARR);
> printf("%s\n", arr);
>
> return 0;
> }
>
>
> void selectionSort(char s[], int len)
> {
> int i, idx;
> char tmp;
Schools of thought vary, but some prefer variables that are only
going to be used in a small scope to be declared within that scope.
> for(i = 0; i != len; ++i)
> {
> idx = findSmallest(s, i, len);
so that could be
int idx = findSmallest(s, i, len);
> /* printf("i = %d, Smallest Index = %d, s[%d] = %c\n", i, idx,
> idx, s[idx]); */
> tmp = s[i];
and that could be
char tmp = s[i];
> s[i] = s[idx];
> s[idx] = tmp;
Note that the swap is only necessary if(i != idx).
> }
> }
>
>
> int findSmallest(char s[], const int idx_cur, const int len)
> {
> int j, ret_index;
> char smallest = s[idx_cur];
> ret_index = idx_cur;
>
> for(j = idx_cur+1; j != len; ++j)
> {
> /* printf("idx_cur = %d, j = %d\n", idx_cur, j); */
> if(smallest > s[j])
Again, it's a matter of taste, but some prefer the object
you're testing to be first in the comparison. And here you're
testing s[j]. So:
if(s[j] < smallest)
> {
> smallest = s[j];
> ret_index = j;
> }
> }
>
> return ret_index;
> }
The sort looks fine. You might want to write a simple test
harness to test arbitrary inputs.
Phil
--
Humans will have advanced a long, long, way when religious
belief has a cozy little classification in the DSM.
-- David Melville (on r.a.s.f1)