4 Replies - 425 Views - Last Post: 12 February 2014 - 03:57 PM Rate Topic: -----

#1 KnifeTea  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 138
  • Joined: 21-November 13

Bubble sort array (beginner)

Posted 12 February 2014 - 04:28 AM

I'm going through this article at the moment, and there's a program that sorts an array of number's into size order.

I'm trying to follow through how the sort process is working though, here's the program :

#include <stdio.h>

#define MAX 4

int a[MAX];
int rand_seed=170;

/* from K&R
   - returns random number between 0 and 32767.*/
int rand()
{
    rand_seed = rand_seed * 1103515245 +12345;
    return (unsigned int)(rand_seed / 65536) % 32768;
}

int main()
{
    int i,t,x,y;

    /* fill array */
    for (i=0; i < MAX; i++)
    {
        a[i]=rand();
        printf("%d\n",a[i]);
    }

   
    /* bubble sort the array */
    for (x=0; x < MAX-1; x++)
        {
            for (y=0; y < MAX-x-1; y++)
                if (a[y] > a[y+1])
                {
                    t=a[y];
                    a[y]=a[y+1];
                    a[y+1]=t;
                }
        }
    
    /* print sorted array */
    
    printf("--------------------\n");
        for (i=0; i < MAX; i++)
            printf("%d\n",a[i]);

    return 0;
}



**Random numbers are :

11697 = a[0]
5078 = a[1]
31364 = a[2]
26294 = a[3]

So the sorting starts at line 29 - (to my understanding) the for loop with x will run 3 times.... x < 3(MAX-1)

0
1
2

then it hit's MAX-1(3) and will stop...

for every iteration of 'loop x' there is a nested loop with the variable y... this loop cuts off when y < MAX-x-1... which would allow it to run

0
1
2

When x is 0... Then when x = 1

0
1

So for every iteration of x loop y loop runs twice : 0, 1

Nested in y loop there is an if statement. This will be ran twice before reset(one for each iteration of y loop) and measures whether
a[0] > a[1] on the first iteration. And a[1] > a[2] on the second.

So if this program was run the first if statement would be working whether

a[y] 11697 > a[y+1] 5078

Which is true so we go into the if statement.

t = a[y]
So t = 11697

a[y] = a [y+1]
So a[0] = a[1] ---- a[0] = 5078

a[y+1] = t
So a[1] = 5078


Our array values have been effectively swapped. The random number array would now read

a[0] = 5078
a[1] = 11697
a[2] = 31364
a[3] = 26294


the next time the y loop runs the same process would be used, but the if statement would be checking if a[1] > a[2]

Which it isn't so the if statement doesn't run....

I'm not quite finishing it off though... I don't get how y ever references a[3] as it... ahh [y+1] stupid me

So this process runs for the second time, doing the same swap process to the array values a[1] and a[2]

a[1] is not greater than a[2], so the if statement doesn't execute...

On the last run of y a[2] is referenced against a[3], which is greater so they swap

a[0] = 5078
a[1] = 11697
a[2] = 26294
a[3] = 31364


X will now run again, but as the array's are in order the loops will exit.


Is this right? I think it works, but hopefully it show's any constructs that I'm not really communicating well, missed or don't seem to be understanding.

Is This A Good Question/Topic? 0
  • +

Replies To: Bubble sort array (beginner)

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3652
  • View blog
  • Posts: 11,421
  • Joined: 05-May 12

Re: Bubble sort array (beginner)

Posted 12 February 2014 - 07:14 AM

So your are basically asking us if your implementation works correctly?

Typically, the approach to this is come up with various test cases that try out various conditions. Some conditions to consider are:
- an array that is already in order
- an array that has no elements
- an array that has one element
- an array that has two elements
- an array that has only two elements that require swapping
- etc.

And since it's not practical to test every permutation, so you do your testing the same you would do a proof by induction.
Was This Post Helpful? 0
  • +
  • -

#3 KnifeTea  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 138
  • Joined: 21-November 13

Re: Bubble sort array (beginner)

Posted 12 February 2014 - 11:09 AM

View PostSkydiver, on 12 February 2014 - 07:14 AM, said:

So your are basically asking us if your implementation works correctly?


Yeah, just wanted to see if I was understanding it really seeing as I don't have anyone to ask.

Skydiver said:

And since it's not practical to test every permutation, so you do your testing the same you would do a proof by induction.


Never heard of 'proof by induction' before.... Google tells me it's maths, not sure if this is something I'm expected to be au fait with or not... Is it some kind of formula / method to check one's working? Is my working out (what I've written) enough to show proof of understanding? I think a lot of what's there would probably be internal for someone thats comfortable with it all, but as I'm new it's all still a bit hieroglyphic.

If I can ask another question though seeing as it's relating to this program and another thread would probably waste space...

It say's "Try this yourself" and ask's to write the for loop (I say's the first piece of code so I'm guesing its the one that fills the array out.) into one line.

So

    for (i=0; i < MAX; i++)
    {
        a[i]=rand();
        printf("%d\n",a[i]);
    }
  



into one line

I've written it out as

 for (i=0; i < MAX;a[i]=rand(),printf("%d\n",a[i]), i++);



And this works, though I initially wrote it out without the semi colon on the end (forgot / typo...) and the results returned were different

Without colon

Posted Image

With colon

Posted Image

The one that doesn't print out correctly isn't the printf that's actually in the for loop with the missing semi colon. I don't really understand why this has happened?

Thank you
Was This Post Helpful? 0
  • +
  • -

#4 AKMafia001  Icon User is offline

  • </code.in.dream>

Reputation: 187
  • View blog
  • Posts: 624
  • Joined: 11-June 11

Re: Bubble sort array (beginner)

Posted 12 February 2014 - 12:12 PM

Well! You might know that when we omit braces from loops then the only one next statement is considered as part of the body...

e.g.
for( ; ; )
   printf("Hello\n");



Sometimes, when we wish not to have a body of the loop we do something like this,
for( ; ; );    // put a semi-colon

// or

for( ; ; ) {}   // put empty braces, denotes no statements in body



In the first case in the above example, there is a one single statement, just as in the printf("Hello\n"); example...

You could see it as
for( ; ; )
    ;    // no braces, will consider 1 statement, in this case semi-colon



So, the point is, when you omitted that semi-colon, the loop consider the Bubble sort loop as it's body which in turn had its own body enclosed in braces...

Hope this Helps!

This post has been edited by AKMafia001: 12 February 2014 - 12:14 PM

Was This Post Helpful? 0
  • +
  • -

#5 KnifeTea  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 138
  • Joined: 21-November 13

Re: Bubble sort array (beginner)

Posted 12 February 2014 - 03:57 PM

Hey AKMafia001 thanks for the response

View PostAKMafia001, on 12 February 2014 - 12:12 PM, said:

when we omit braces from loops then the only one next statement is considered as part of the body...


Ok cool, that makes sense I'd never thought of it TBH.

So the program hit's the 'Fill Array' loop, runs the for loop,and the following loop (bubble sort the array) becomes nested in the fill array loop.

I'm having a bit of trouble following through the working's of the loop even though your answer makes sense though...

The section that's affected is outside of the 'fill array' loops scope whether the semicolon's there or not, so why is it's print values effected rather than the print statement that becomes nested in the array loop?

It hit's the 'fill' loop, fills the array up with the values and prints them to the screen....

At the same time as these values are filled (because without the semi colon the loops nested) the array is being sorted by the second for loop... For some reason the first two values ( a[o] and a[1] ) are set to zero, but I don't get why this is happening... is it something to do with y / x being re-initialised each time?
And why does it print a[0] and a[3] in positions a[2] and a[3]... a[3] doesn't move from the first but a[0] does...

Hmm! Probably painfully basic but it's confused me

Cheers
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1