Sorting an array Question

Question

I am using Turbo C, and I've some query about my code. I'm just perplexed... The program first asks for a list of numbers(you shouldn't type more than 20). As the user types in the numbers, they are placed in the array list[]. Once the user terminates the list by typing 0*(which is not placed on the list)*, the program then calls the sort() function, which sorts the values in the list. At the last part, which has a comment of /*I AM NOW CONFUSED WITH THIS PART*/, is the part where I need your help... Kindly help me out.

enter image description here

       File   Edit   Run   Compile   Project   Options   Debug   Break/watch
    ╒════════════════════════════════════ Edit ════════════════════════════════════╕
    │      Line 1     Col 43  Insert Indent Tab Fill Unindent * C:NONAME.C         │
    │                                                                              │
    │ #define MAXSIZE 20                            /* size of buffter */          │
    │ void sort(int[], int);                        /* prototype */                |
    │                                                                              |
    │ main()                                                                       |
    │ {                                                                            |
    │     static int list[MAXSIZE];                 /* buffer for numbers */       |
    │     int size = 0;                             /* size 0 before input */      |
    │     int dex;                                  /* index of array */           |
    │     do                                        /* get list of numbers */      |
    │     {                                                                        |
    │         printf("Type number: ");                                             |
    │         scanf("%d", &list[size]);                                            |
    │     }                                                                        |
    │     while(list[size++] != 0);                 /* exit loop on 0 */           |
    │                                                                              |
    │     sort(list,--size);                        /* sort nubmers */             |
    │     for(dex=0; dex<size; dex++)               /* print sorted list */        |
    │         printf("%d\n", list[dex]);                                           |
    │                                                                              |
    │      getche();                                                               |
    │ }                                                                            |
    │                                                                              |
    │ void sort(int list[], int size)                                              |
    │ {                                                                            |
    │     int out, in, temp;                        /* I AM NOW CONFUSED */        |
    │                                                                              |
    │     for(out=0; out<size-1; out++)             /* IN THIS PART! */            |
    │         for(in=out; in<size; in++)                                           |
    │              if(list[out] > list[in])                                        |
    │              {                                                               |
    │                  temp=list[in];                                              |
    |                  list[in]=list[out];                                         |
    │                  list[out]=temp;                                             |
    │              }                                                               |
    │ }                                                                            |
    │                                                                              |
    │                                                                              |
    ├─────────────────────────────────── Watch ────────────────────────────────────┤
    │                                                                              │
    └──────────────────────────────────────────────────────────────────────────────┘
     F1-Help  F5-Zoom  F6-Switch  F7-Trace  F8-Step  F9-Make  F10-Menu   NUM

This just looks like a bubble sort, though it isn't doing the swapping correctly. — chrisaycock
– chrisaycock, Commented May 25, 2011 at 3:55
Heh, I thought someone else left the please show me what's wrong comment, it's hard to guess what's wrong... :) — sarnold
– sarnold, Commented May 25, 2011 at 3:58
@bdares I'm just asking for a help how 2 correctly construct the code... — Aaron
– Aaron, Commented May 25, 2011 at 3:59
@sarnold It's not the size; it's the swapping as other answers have listed. — chrisaycock
– chrisaycock, Commented May 25, 2011 at 4:01

Community · Accepted Answer · 2017-05-23 11:48:23Z

2

It's just code that is meant to sort the array elements but it's never going to work in its current form since:

temp=list[in];
list[out]=temp;

will overwrite list[out] with list[in] without ever preserving the original contents of list[out].

The best way to swap two variables is with something like:

temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;

And, please, for the love of whatever deity you believe in, don't do this :-)

So, if your question is how to sort the data, then the following pseudo-code should help. I'd provide C code but, on the off chance that this is homework, you should do some of the work yourself ^a.

def sort (arr[], sz):
    swapped = true                       # Force loop entry.
    while swapped:                       # Loop until a pass had no swaps.
        swapped = false
        for idx goes from 1 to sz-1:     # For all but the first element.
            if arr[idx-1] > arr[idx]:    # If order is wrong.
                swapped = true           # More passes will be needed.
                temp = arr[idx-1]        # Swap
                arr[idx-1] = arr[idx]    #   the
                arr[idx] = temp          #     elements.

This is a bubble sort variation which exits as soon as the list is sorted (well, after one pass with no swaps). Some naive variants will simply keep going for roughly n² times regardless.

^a If you'd like to indicate in a comment that it's not homework, I'd be happy to provide the C code. Just be aware (if you're planning to lie to me) that your educators will almost certainly be able to see that code and you will probably fail in that case (or be expelled for blatant plagiarism).

And, since you've stated it's not homework, here's a complete C program illustrating it:

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

#define FALSE (1==0)
#define TRUE  (1==1)

static void sort (int arr[], int sz) {
    int idx, temp, swapped;

    swapped = TRUE;                        // Force loop entry.
    while (swapped) {                      // Loop until a pass had no swaps.
        swapped = FALSE;
        for (idx  = 1; idx < sz; idx++) {  // For all but the first element.
            if (arr[idx-1] > arr[idx]) {   // If order is wrong.
                swapped = TRUE;            // More passes will be needed.
                temp = arr[idx-1];         // Swap
                arr[idx-1] = arr[idx];     //   the
                arr[idx] = temp;           //     elements.
            }
        }
    }
}

int main (int argc, char *argv[]) {
    int sz, i, *vals;

    sz = argc - 1;
    if (sz < 1)
        return 0;
    if ((vals = malloc (sz * sizeof (int))) == NULL) {
        printf ("ERROR: Cannot allocate memory.\n");
        return 1;
    }

    for (i = 0; i < sz; i++)
        vals[i] = atoi (argv[i+1]);

    printf ("Numbers before:");
    for (i = 0; i < sz; i++)
        printf (" %d", vals[i]);
    printf ("\n");

    sort (vals, sz);

    printf ("Numbers after :");
    for (i = 0; i < sz; i++)
        printf (" %d", vals[i]);
    printf ("\n");

    free (vals);
    return 0;
}

Running this with:

$ ./testprog 3 1 4 1 5 9 2 6 5 3 5 8 9

gives you the output:

Numbers before: 3 1 4 1 5 9 2 6 5 3 5 8 9
Numbers after : 1 1 2 3 3 4 5 5 5 6 8 9 9

edited May 23, 2017 at 11:48

CommunityBot

11 silver badge

answered May 25, 2011 at 3:59

paxdiablo

888k243 gold badges1.6k silver badges2k bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Aaron Over a year ago

@paxdiablo no, it's not homework... We'v not yet reached the date of school starting...

Aaron Over a year ago

@paxdiablo... I have modified my code, and it really works. But I have some additional question. In the line for(out=0; out<size-1; out++) I tried to remove the -1 like this one for(out=0; out<size; out++) and these two were actually working in turn. But I just want to be more accurate(which one is accurate). What happened when I omit the -1? I'm just trying to figure it out... Thanks in advance

paxdiablo Over a year ago

@aerohn, normally you would detect a sentinel value like zero before trying to place it in the array, something like val = getval(); while (val != 0) { arr[idx++] = val; val = getval(); }.

paxdiablo Over a year ago

@aerohn, yes, &(list[size]) and list+size should come down to the same address. The floating point formats not linked-type errors are usually in systems where floating-point support is optional (eg, embedded systems) and/or in a separate library to the main stuff. I wouldn't expect to see that unless you'd used a floating point format string like %f. Changing the addresses rather than the format string shouldn't cause that. Are you sure you haven't included a floating point converter somewhere?

paxdiablo Over a year ago

@aerohn, that declaration is correct. However, if you receive a message like floating point formats not linked during compilation, the floating point stuff isn't being included by default - you need to do this yourself. From memory (and this is deep dark memeory so I may be mis-remembering), Turbo C will do this if you simply force a floating point operation, like float f = 1.1 / 1.0; in the code.

|

wallyk · Accepted Answer · 2011-05-25 03:59:06Z

1

The value swap in the inner-most loop of sort() is incomplete. It never assigns list[in] to anything.

answered May 25, 2011 at 3:59

wallyk

58.1k17 gold badges92 silver badges155 bronze badges

Comments

CEGRD · Accepted Answer · 2011-05-25 04:29:46Z

0

I believe the following is what you are trying to do. Essentially you are trying to find the minimum element at each inner loop iteration. For instance, if you start with the array [5,4,3,2,1], after the first inner loop iteration, the array would look like the following:

[5,4,3,2,1] : after in = 0

[4,5,3,2,1] : after in = 1

[3,5,4,2,1] : after in = 2

[2,5,4,3,1] : after in = 3

[1,5,4,3,2] : after in = 4

Now 1 is at the beginning. Eventually, the array would be sorted as [1,2,3,4,5].

void sort(int list[], int size) {
    int out, in, temp;       
    for(out=0; out<size; out++)  {        |
        for(in=out; in<size; in++)                                           
            if(list[out] > list[in])                                        
            {                                                               
                tmp = list[out]
                list[out]=list[in];
                list[in] = tmp                                                                                           
            }    
    }                                                           
}

answered May 25, 2011 at 4:29

CEGRD

7,9655 gold badges27 silver badges35 bronze badges

2 Comments

Aaron Over a year ago

How about the last entered 0 to terminate the program?

CEGRD Over a year ago

@aerohn you can call sort with sort(list, size - 1) and that would solve your problem.

Collectives™ on Stack Overflow

Sorting an array Question

3 Answers 3

11 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

11 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related