DaniWeb Forum Index > Software Development > C++

C++ RSS

Some Data Structure Problem

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

•

Join Date: Nov 2006

Posts: 48

Reputation: mzd12111 is an unknown quantity at this point

Solved Threads: 0

mzd12111

Offline

Light Poster

Some Data Structure Problem

Mar 12th, 2007

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 :

 Help with Code Tags 
 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

•

Join Date: Mar 2007

Posts: 9

Reputation: zigpy_siva is an unknown quantity at this point

Solved Threads: 4

zigpy_siva zigpy_siva is offline

Offline

Newbie Poster

Re: Some Data Structure Problem

Mar 12th, 2007

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)

•

Join Date: Dec 2006

Posts: 2,031

Reputation: Aia has much to be proud of

Solved Threads: 177

Aia

Offline

Postaholic

Re: Some Data Structure Problem

Mar 12th, 2007

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:

•

int[]A

Should be: int A[]

•

Join Date: Feb 2007

Posts: 539

Reputation: thekashyap will become famous soon enough

Solved Threads: 50

thekashyap thekashyap is offline

Offline

Posting Pro

Re: Some Data Structure Problem

Mar 13th, 2007

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"

•

Join Date: Nov 2006

Posts: 48

Reputation: mzd12111 is an unknown quantity at this point

Solved Threads: 0

mzd12111

Offline

Light Poster

Re: Some Data Structure Problem

Mar 13th, 2007

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

•

Join Date: Dec 2006

Posts: 2,031

Reputation: Aia has much to be proud of

Solved Threads: 177

Aia

Offline

Postaholic

Re: Some Data Structure Problem

Mar 13th, 2007

•

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.

•

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.

•

Join Date: Nov 2006

Posts: 48

Reputation: mzd12111 is an unknown quantity at this point

Solved Threads: 0

mzd12111

Offline

Light Poster

Re: Some Data Structure Problem

Mar 14th, 2007

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