Lost Password?

Go Back   CodeCall Programming Forum > Software Development > C and C++

Unregistered, Check out the Coder Battles in the Announcement and Game forums.

C and C++ C and C++ forum for discussing all forms of C except for C#. These languages are powerful low level languages used for creating Operating Systems, Device Drivers, compilers and much more.

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1 (permalink)  
Old 09-26-2007, 11:17 AM
Yuriy M's Avatar   
Yuriy M Yuriy M is offline
Newbie
 
Join Date: Sep 2007
Location: Winnipeg, Canada
Age: 26
Posts: 6
Credits: 0
Rep Power: 0
Yuriy M is on a distinguished road
Send a message via MSN to Yuriy M
Angry Help regarding the sorting of arrays with flags!

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:
Code:
/* 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:
Code:
/* 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?
__________________
For $1000: Something that is a miserable pile of secrets.
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote

Sponsored Links
  #2 (permalink)  
Old 09-27-2007, 01:42 AM
felixme86's Avatar   
felixme86 felixme86 is offline
Newbie
 
Join Date: Sep 2007
Location: Seattle WA
Posts: 11
Credits: 0
Rep Power: 0
felixme86 is on a distinguished road
Default

Code:
// 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.

Last edited by WingedPanther; 09-27-2007 at 10:51 AM. Reason: Add code tags
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #3 (permalink)  
Old 09-27-2007, 07:13 AM
v0id's Avatar   
v0id v0id is offline
Super Moderator
 
Join Date: Apr 2007
Location: Denmark
Posts: 2,573
Last Blog:
CherryPy(thon)
Credits: 54
Rep Power: 28
v0id is a glorious beacon of lightv0id is a glorious beacon of lightv0id is a glorious beacon of lightv0id is a glorious beacon of lightv0id is a glorious beacon of lightv0id is a glorious beacon of light
Send a message via MSN to v0id
Default

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:
[code]
This is where you put your code.
[/code]
__________________

To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
|
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
|
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
|
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
-
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
-
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.

I'm always up for a chat, so feel free to contact me...
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #4 (permalink)  
Old 10-12-2007, 10:30 PM
Yuriy M's Avatar   
Yuriy M Yuriy M is offline
Newbie
 
Join Date: Sep 2007
Location: Winnipeg, Canada
Age: 26
Posts: 6
Credits: 0
Rep Power: 0
Yuriy M is on a distinguished road
Send a message via MSN to Yuriy M
Default

Code:
/* 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.
__________________
For $1000: Something that is a miserable pile of secrets.
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
Reply



Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On

Similar Threads
Thread Thread Starter Forum Replies Last Post
Python arrays... Sir_Rimo Python 3 06-20-2007 08:54 AM
Finding non-standard sorting order via graph theory elle General Programming 1 05-17-2007 09:36 PM
Arrays clookid PHP Tutorials 1 01-11-2007 08:30 PM
Sorting Arrays falco85 PHP Forum 5 08-23-2006 09:31 PM
Arrays Sionofdarkness C and C++ 5 07-26-2006 05:35 PM


All times are GMT -5. The time now is 04:56 AM.

Contest Stats

Xav ........ 1097.16
MeTh0Dz|Reb0rn ........ 986.37
morefood2001 ........ 850.04
John ........ 841.93
WingedPanther ........ 684.54
marwex89 ........ 638.26
Brandon W ........ 493.36
chili5 ........ 292.12
Steve.L ........ 188.37
orjan ........ 187.41

Contest Rules

CodeCall Goal

Goal: 100,000 Posts
Complete: 79%

Ads