Help regarding the sorting of arrays with flags!

[Yuriy M]

Hey everyone. I've been working on a C problem that involved sorting large arrays through the use of flags that indicate whether the array has been sorted or not.

Here's the original question:

The bubble sort of dem11-7.c is inefficient for sorting large arrays because it does not recognize when the array is sorted. The program makes "size1" passes on an array with "size" elements even if the array is already sorted. The program will be more efficient if when making a pass over the array, it recognizes if the array is sorted and stops. Recode dem11-7.c to do this.

Here's a hint that the question gave me:

Use a flag called "sorted". Set "sorted" equal to zero immediately before making a pass over the array. If the flag equals 1, the array is sorted. In this case, exit the loop. If the flag equals zero, the array is not sorted. In this case, the program must make a pass over the array. In the inner loop of the nested "for" loop, when the function swaps two array elements, set the flag to 1.

Here's dem11-7.c in all of its unaltered glory:

/* dem11-7.c */

/*
* This program shows how to sort the elements
* in an array.
*/

#include <stdio.h>

#define NUM_QUIZZES 10

main()
{
      /* The array to store the quiz grades */

     int grade[NUM_QUIZZES];

     int quiz,                         /* Subscript for the array grade[] */
          temp,                       /* For swapping array elements */
          pass,                        /* The number of the pass */
          limit;                        /* Keeps track of how far to go on a pass */

     /* Get the grades */

     printf("\nPlease enter %d integer quiz grades.\n\n", NUM_QUIZZES);

     for (quiz = 0; quiz < NUM_QUIZZES; ++quiz)
     {
       printf("\nEnter grade for quiz %d: ", quiz + 1);
       scanf("%d", &grade[quiz]);
     }

     /* Display the quiz grades */

     printf("\n\nThe grades you entered are as follows:\n");
     for (quiz = 0; quiz < NUM_QUIZZES; ++quiz)
      printf("%6d", grade[quiz]);
     printf("\n");

     /* Do the bubble sort */

     limit = NUM_QUIZZES - 2;

     for (pass = 1; pass <= NUM_QUIZZES - 1; ++pass)
     {
       for (quiz = 0; quiz <= limit; ++quiz)
        if (grade[quiz] > grade[quiz + 1])
        {
           temp = grade[quiz];
           grade[quiz] = grade[quiz + 1];
           grade[quiz + 1] = temp;
        }
      --limit;
      }

      /* Display the sorted quiz grades */

      printf("\n\nThe grades in increasing order are as follows:\n");

      for (quiz = 0; quiz < NUM_QUIZZES; ++quiz)
       printf("%6d", grade[quiz]);
      printf("\n");
}

Now here's the modified version with the "sorted" flag that I put in:

/* Prob 11-10
*  Created by Yuriy Mokriy
*/

#include <stdio.h>

#define NUM_QUIZZES 10                  /* Total number of quiz grades in the array */

main()
{
      int grade[NUM_QUIZZES],           /* The array to store the quiz grades */
          temp,                         /* For swapping array elements */
          quiz,                         /* Subscript for the array grade[] */
          pass,                         /* The number of the pass */
          limit,                        /* Keeps track of how far to go on a pass */
          sorted = 1;                   /* A flag that indicates when the array is sorted */
      
      /* Get the grades */
      
      printf("\nPlease enter %d integer quiz grades. \n\n", NUM_QUIZZES);
          
      for (quiz = 0; quiz < NUM_QUIZZES; quiz++)
      {
       printf("\nEnter grade for quiz %d: ", quiz + 1);
       scanf("%d", &grade[quiz]);
      }
       /* Check if grade entered is greater or smaller than the one previous */
      
       if (grade[quiz] > grade[quiz + 1])
        sorted = 0;
       else
        sorted = 1;     

      /* Display the quiz grades */
      
      printf("\n\nThe grades you entered are as follows:\n");
      for (quiz = 0; quiz < NUM_QUIZZES; ++quiz)
        printf("%6d", grade[quiz]);
      printf("\n");
        
       /* Do the bubble sort if sorted is equal to 0 */
      
       limit = NUM_QUIZZES - 2;
      
       if (sorted != 1)
       {
        for (pass = 1; pass <= NUM_QUIZZES - 1; ++pass)
        {
         for (quiz = 0; quiz <= limit; ++quiz)
          if (grade[quiz] > grade[quiz + 1])
          {
            temp = grade[quiz];
            grade[quiz] = grade[quiz + 1];
            grade[quiz + 1] = temp;
            sorted = 1;
          } 
          --limit;   
        }
       } 
      
      /* Display the sorted quiz grades */
      
      printf("\n\nThe grades in increasing order are as follows:\n");
      
      for (quiz = 0; quiz < NUM_QUIZZES; ++quiz)
       printf("%6d", grade[quiz]);
      printf("\n");
}

What I'm basically trying to do here is to have each grade read in individually and compared to see if they are already in sorted order. If they are sorted, the flag sorted is set to 1. If not, it is set to 0, the bubble sort is executed and then the flag is set to 1.

The problem I'm having with the code is that it doesn't seem to recognize the flag and just gives me the same disorganized output. What am I not doing right?

[felixme86]

// Start out by saying that the array is not sorted
// because we have not gone through the array
bool sorted=false;
        for (pass = 1; pass <= NUM_QUIZZES - 1&&!sorted; ++pass)
        {
             // Set sorted to true.  now we will go though the list once
             // if we find any variable out of place then we set sorted
             // to false.  If we have made it through without moving
             // any variables there is no reason to repeat the outer
             // loop because we will not move any variables on
             // subsequent checks.
             sorted=true;
             for (quiz = 0; quiz <= limit; ++quiz)
             if (grade[quiz] > grade[quiz + 1])
             {
                 temp = grade[quiz];
                 grade[quiz] = grade[quiz + 1];
                 grade[quiz + 1] = temp;
                 sorted = false;
             } 
             --limit;   
        }

Hopefully this is what you are looking for.

[v0id]

felixme86, here on CodeCall (and on many other forums) we've a so-called code-tags. It's easier for us to read your code, if you use them. They work in this way:

[code]
This is where you put your code.
[/code]

[Yuriy M]

/* Prob 11-10
*  Created by Yuriy Mokriy
*/

#include <stdio.h>

#define NUM_QUIZZES 10                  /* Total number of quiz grades in the array */

main()
{
      int grade[NUM_QUIZZES],           /* The array to store the quiz grades */
          temp,                         /* For swapping array elements */
          quiz,                         /* Subscript for the array grade[] */
          pass,                         /* The number of the pass */
          limit,                        /* Keeps track of how far to go on a pass */
          sorted = 1;                   /* A flag that indicates when the array is sorted */
      
      /* Get the grades */
      
      printf("\nPlease enter %d integer quiz grades. \n\n", NUM_QUIZZES);
          
      for (quiz = 0; quiz < NUM_QUIZZES; quiz++)
      {
       printf("\nEnter grade for quiz %d: ", quiz + 1);
       scanf("%d", &grade[quiz]);
      }
       /* Check if grade entered is greater or smaller than the one previous */
      
      if (quiz > 0)
       {
         if (grade[quiz] < grade[quiz - 1])
           sorted = 0;
         else
           sorted = 1;
       }  

      /* Display the quiz grades */
      
      printf("\n\nThe grades you entered are as follows:\n");
      for (quiz = 0; quiz < NUM_QUIZZES; ++quiz)
        printf("%6d", grade[quiz]);
      printf("\n");
        
       /* Do the bubble sort if sorted is equal to 0 */
      
       limit = NUM_QUIZZES - 2;
      
       if (sorted != 1)
       {
        for (pass = 1; pass <= NUM_QUIZZES - 1; ++pass)
        {
         for (quiz = 0; quiz <= limit; ++quiz)
          if (grade[quiz] > grade[quiz + 1])
          {
            temp = grade[quiz];
            grade[quiz] = grade[quiz + 1];
            grade[quiz + 1] = temp;
            sorted = 1;
          } 
          --limit;   
        }
       } 
      
      /* Display the sorted quiz grades */
      
      printf("\n\nThe grades in increasing order are as follows:\n");
      
      for (quiz = 0; quiz < NUM_QUIZZES; ++quiz)
       printf("%6d", grade[quiz]);
      printf("\n");
}

Got the problem fixed. All I needed to do was use an if statement to check if the quiz grade entered is greater than 0 and whether the current quiz grade was less than the one before it. After that, the program sorted the grades smoothly.