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.

       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

Answer 1

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 n2 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

Answer 2

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

Answer 3

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                                                                                           
            }    
    }                                                           
}