Ad:

C++ Discussion Thread
Marked Solved
Views: 3204

Mar 12th, 2007

Some Data Structure Problem

Expand Post »

hi Guys
this is my problem :
a) what should i have to show to Proove that a sort algorithm work well
b)what is the order of this algorithm :

c Syntax (Toggle Plain Text)
     void mySort(int[]A , int n){
          int t,i;
          for (i=1 ; i<=n; i++){
               while(A[i] != i){
                    t = A[i];
                    A[i] = A[t];
                    A[t] = t;
                 }
           }
    }
     void mySort(int[]A , int n){
          int t,i;
          for (i=1 ; i<=n; i++){
               while(A[i] != i){
                    t = A[i];
                    A[i] = A[t];
                    A[t] = t;
                 }
           }
    }

notice that indexes of array start with 1 and ends with n
Thanks everyone

Last edited by WaltP; Mar 13th, 2007 at 3:58 am. Reason: Please use CODE tags

Similar Threads

Data Structure question in C++
a question about heap data structure in C
Data Structure Using JAVA in Java
Data Structure Problem in C
How to delete a data structure in Builder 6.0? in C++

mzd12111

Reputation Points: 7

Solved Threads: 0

Light Poster

Offline

48 posts
since Nov 2006

Permalink

Mar 12th, 2007

Re: Some Data Structure Problem

hi
a) Sorting algoritham must work for a wide range eg if i give 3 values like 1,2,3 it is ok but what if i give values 25,520,1000......

b) Order Meanse ?????(i am also new)

zigpy_siva

Reputation Points: 10

Solved Threads: 5

Newbie Poster

Offline

16 posts
since Mar 2007

Permalink

Mar 12th, 2007

Re: Some Data Structure Problem

Let's say you pass the array int A[] = { 1, 2, 3, 4 };
and that the int n is iqual to the number of elements in the array,
in this case 3 since starts at element 0.
This sorting function is going to do the following:

the for loop will start with a 1 as an indexer.

For loop checks that 1 is less or iqual to n, which has a value of 3 (four elements in the array). Is 1 <= 3?. Yes.
The block that belongs to the for loop is executed.

The while loop checks: Is it true that what A[1] (whatever value is in A[1],second element of the array; this case a 2) is not 1?. 2 != 1?. Yes.

The block belonging to the while loop is execute.

variable t gets the value of A[1] which is 2; A[1] gets A[t] which is 3 now, since
A[t] is A[2] or third array element; A[t](or A[2]) gets whatever is in t, at this time a 2.

Then while loop is finished in this round, and for loop increments n by one, making it this time a 2.

So far then we have after this round:
A[0] = 1 (the function loops will never touch this element, as is written)
A[1] = 3
A[2] = 2
A[3] = 4

Do we want to go another round with it. What the heck, let's do it, since I believe
here is were it will get interesting.

Is 2 <= 3?. Yes. Keep going down.
Is A[2] not 2?. Or Is 2 not 2?. No.
The swapping will not start this round. Nothing changes and the for loop will increase n to 3, and gets at it once more. I am too tired thinking what is going to happen.

I hope you get the idea. Is that what you intended to happen?. Doubtful.
Check the logic to make it work with any numbers that get passed as paramenters in the function.

* May I suggest also that you work in a better spacing and indenting in your code. Here's a great link for formatting c/c++ code. This one will help you to post code correctly.

By the way, in the function, this part:

Quote ...

int[]A

Should be: int A[]

Aia

Reputation Points: 2224

Solved Threads: 218

Nearly a Posting Maven

Offline

2,304 posts
since Dec 2006

Permalink

Mar 13th, 2007

Re: Some Data Structure Problem

To detect the order you need some help from teh algorithm, no outside code can independencly establish that.
The order of the algorithm means how many operations would the algo perform to sort a list of 'n' elements.
Bubble sort is of order n*n (i.e. n-square).
Anyway, just increment a static variable within the code of 'operation' (in your case it's a 'swap', inside the while loop). At the end of the run the value of this variable will give you the order for a given sequence.
Remember this is different than the theoratical order. Anyway see this link.

Last edited by thekashyap; Mar 13th, 2007 at 12:44 am. Reason: Added ", inside the while loop"

thekashyap

Reputation Points: 254

Solved Threads: 74

Practically a Posting Shark

Offline

804 posts
since Feb 2007

Permalink

Mar 13th, 2007

Re: Some Data Structure Problem

all of yur Replies are True , Sorry To say that , But Not as much usefull as i thought them to be , beacuse i knew All of them before , maybe i didnt Express The Real Problem :
i've Got DS (Data structure Course) This term and this is one of the Exersices which the Professor gave us . in the first part The problem ask us to Say that which parameters should be Shown TO show that a sort algorithm Works well , and in the second part it wants us to Calculate the Order of this Sort algorithm (for example O(n) i meant)
thanks for yur help

mzd12111

Reputation Points: 7

Solved Threads: 0

Light Poster

Offline

48 posts
since Nov 2006

Permalink

Mar 13th, 2007

Re: Some Data Structure Problem

Click to Expand / Collapse Quote originally posted by mzd12111 ...

all of yur Replies are True , Sorry To say that , But Not as much usefull as i thought them to be , beacuse i knew All of them before ,

I am very sorry that we couldn't help you. I thought that by going down with what your code would do, step by step you would see that it has some problems. My bad there.

I understand that english is not your native language, and I know how hard is to express your ideas. Could you say it onces more in other words, I not quite sure what you are asking, especially this part.

Quote ...

to Say that which parameters should be Shown TO show that a sort algorithm Works well

parameters are the ones that you passed inside the parenthesis of the function, and they are OK. You are passing an integer array and an integer which are what you need to do the sorting. However I got the
feeling that's not what you are asking.

Let me ask you a question. What are you trying to do with the sort?.
Are you trying to sort the elements from largest to smaller?. Are you
trying to arrange them from smaller to greater?.

I commend you for going back and tagging your code to look neater.

Aia

Reputation Points: 2224

Solved Threads: 218

Nearly a Posting Maven

Offline

2,304 posts
since Dec 2006

Permalink

Mar 14th, 2007

Re: Some Data Structure Problem

hi there Guys
Yes , English is not my native language , beacuse Persian is my native one,
and i found the Solution , i mean the Order of this algorithm , it's O(n) , beacuse in every While process , at least one number goes to it's Appropriate Location , and then , that number Never Changes It's location anymore
we have N Numbers . so at most we have N Computation

mzd12111

Reputation Points: 7

Solved Threads: 0

Light Poster

Offline

48 posts
since Nov 2006

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: How to controll I/O in soundcard

Next Thread in C++ Forum Timeline: Making array length

DaniWeb Message

Cancel Changes

User Name
Password