You have a collection of gnomes. Each gnome has a number so that they can be pla

Question

You have a collection of gnomes. Each gnome has a number so that they can be placed in numerical order. You wish to write a program to sort these gnomes.

A scaffold of the solution has been created for you.

Do not modify the code that is already present. Instead, fill in the GnomeSort function marked like this:    /*** ... ***/

This function will perform a gnome sort to order the gnomes based on their assigned values. Implement the pseudocode below by translating it to C syntax in your function.

You must use this prototype to receive credit for the assignment.

// Pre-condition: length is the size of the array gnomes.

// Post-condition: gnomes will be sorted in numerical order, from

//                 smallest to largest.

void GnomeSort(int gnomes[], int length);

Gnome Sort Pseudocode

procedure gnomeSort(a[])
    pos := 1
    while pos < length(a)
        if (a[pos] >= a[pos-1])
            pos := pos + 1
        else
            swap a[pos] and a[pos-1]
            if (pos > 1)
                pos := pos - 1
            end if
        end if
    end while
end procedure

Here is the scaffold code:

#include <stdio.h>

#define SIZE 5
#define PRINT 1

void swap(int* ptrA, int*ptrB);
void print(int array[], int length);
void fillArray(int array[], int length);
void GnomeSort(int gnomes[], int length);
int isSorted(int array[], int length);

int main() {
    int a[SIZE];

    fillArray(a, SIZE);
    if (PRINT) print(a, SIZE);
    GnomeSort(a, SIZE);
    if (PRINT) print(a, SIZE);

    // Print out the final result.
    if (isSorted(a, SIZE))
        printf("The sort worked properly. ");
    else
        printf("There was a problem with the sort. ");

    return 0;
}

// Prints out values in array[0]...array[length-1].
void print(int array[], int length) {
    int i;

    for (i=0; i<length; i++)
        printf("%d ", array[i]);
    printf(" ");

    return;
}

// Sorts the items array[0] through array[length-1] using the Gnome Sort algorithm.
void GnomeSort(int gnomes[], int length) {
    /*** FILL IN YOUR CODE HERE ***/
}

// Swaps the variables pointed to by ptrA and ptrB.
void swap(int* ptrA, int* ptrB) {
    int temp = *ptrA;
    *ptrA = *ptrB;
    *ptrB = temp;
    return;
}

// Fills array[0] through array[length-1] with integers
// from a specified file
void fillArray(int array[], int length) {
    int i;
    char filename[20];
    FILE * ifp = NULL;

    printf("What is the name of the file? ");
    scanf("%s", filename);
    ifp = fopen(filename, "r");

    for (i=0; i<length; i++)
        fscanf(ifp, "%d", &array[i]);

    fclose(ifp);

    return;
}

// Returns 1 iff array[0] through array[length-1] are
// in sorted order from smallest to largest.
int isSorted(int array[], int length) {
    int i;

    // Return false if a pair of consecutive values is out of order.
    for (i=0; i<length-1; i++)
        if (array[i] > array[i+1])
            return 0;

    return 1;
}

Explanation / Answer

void GnomeSort(int gnomes[], int length) {
int pos=1;
  
   while(pos < length)
   {
       if(gnomes[pos] > gnomes[pos-1])
       {
       pos++;
       }
       else
       {
           swap(&gnomes[pos], &gnomes[pos-1]);
           if(pos > 1)
           {
           pos--;
           }
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.