Problem: Gnome Sort After getting to know your roommate better, you\'ve discover

Question

Problem: Gnome Sort

After getting to know your roommate better, you've discovered a rather strange secret about her family: they own the largest collections of gnomes in North America!!! The reason this came up is that recently some neighborhood hoodlums moved around all the gnomes in your roommates' parents' yard. Her parents desperately want to get the gnomes back into their proper numerical order. Luckily, you just learned about sorting in your programming course and your roommate has decided that it's only fitting that you write a program implementing Gnome sort to help her!

She kindly pointed you to the wiki page on Gnome sort:

https://en.wikipedia.org/wiki/Gnome_sort

Complete the function below so that it performs a Gnome sort on the input array of integers. The function prototype is given to you below and you can download the program to add your function to:

// Pre-condition: n 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 n);

The given code scaffold will contain all necessary testing code.

(Here is the code)

gnomesort-scaffold.c

Explanation / Answer

Here is the complete program with GnomeSort function

#include <stdio.h>
#include<time.h>
#include<stdlib.h>

#define SIZE 5
#define MAXVAL 100
#define PRINT 1

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

int main() {

// Fill, print, and sort.
srand(time(0));
int a[SIZE];
fillRandomArray(a, SIZE, MAXVAL);
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(" ");
}

// Sorts the items array[0] through array[length-1] using the Gnome Sort algorithm.
void GnomeSort(int array[], int length) {
/*** FILL IN YOUR CODE HERE ***/
// Gnome Sort
int i = 0;
int temp;
while (i < length)
{
if (i == 0 || array[i - 1] <= array[i])
i++;
else
{
temp = array[i-1];
array[i - 1] = array[i];
array[i] = temp;
i = i - 1;
}
}
}

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

// Fills array[0] through array[length-1] with randomly
// chosen integers in the range [1, max].
void fillRandomArray(int array[], int length, int max) {
int i;
for (i=0; i<length; i++)
array[i] = rand()%max + 1;
}

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

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

return 1;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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