Some Data Structure Problem

[mzd12111]

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 :

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

[zigpy_siva]

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)

[Aia]

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[]

[thekashyap]

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.

[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 , 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

[Aia]

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. :)

[mzd12111]

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