5

code should do this: a) Given an unsorted array of integers, your task is to sort the array by applying the following algorithm (Assume that the input doesn’t contain duplicates ): Execute the following steps starting from the first element in the array: – Count the number of smaller elements to find the correct position i. – If the element is in its correct position, move to the succeeding element. – Otherwise, swap the current element with the one found in position i. – Repeat the previous steps till you reach the last element.

Example: 5 7 3 6 9 check a[0], there is one element smaller that it, so it shoould be swapped with the element at position1. 7 5 3 6 9 check the new element a[0]. it should move to position 3. 6 5 3 7 9 check the new element a[0]. it should move to position 2. 3 5 6 7 9 check the new element a[0]. it is in its correct position, so we move to the succeeding element a[1].

public class  Assignment1_T11_25_2729_Sara_Aly {
private int[] a;
private int max;
private int n;
int position=0;
public  Assignment1_T11_25_2729_Sara_Aly (int max){
    a= new int[max];
}
public void insert(int x){
    a[n]=x;
    n++;
        }
public void sort(){
    int out=0, smaller=0;
    while(out<n){
        for(int in=out+1;in<n;n++){
            if(a[in]<a[out])
                smaller++;
        }
        if (smaller==0){
            out++;
        }
        else {
            swap(a[out], a[smaller]);
        }
    }
    }
private void swap (int one, int two){
    int temp=a[one];
    a[one]=a[two];
    a[two]=temp;
}
    public void display(){
        for (int i=0;i<n;i++){
            System.out.print(a[i]+ " ");
        }
        System.out.println("");
    }
public static void main(String[]args){
    int maxsize=5;
    Assignment1_T11_25_2729_Sara_Aly trial;
    trial= new  Assignment1_T11_25_2729_Sara_Aly(maxsize);
    trial.insert(5);
    trial.insert(7);
    trial.insert(3);
    trial.insert(6);
    trial.insert(9);
    trial.display();
    trial.sort();
    trial.display();
}
}

    Tried a few algorithims to get it to work but for some reason it won't sort any suggestions??

also tried this the sorting method but no luck.

public void sort(){
boolean finished = false;
int position =0;
    while (position<max){
        if (finished==true){
        position++;
        finished =false;
        }
        else {
            int smaller=0;
            for (int j = position+1; j<max; j++){
            int temp=a[position];
                if (a[j] <a[position]){
                    smaller++;
                }
            }
            if (smaller==0){
                finished= true;
            }
            else {
                int temp= a[smaller];
                a[smaller]=a[position];
                a[position]=temp;
                }
                }
            }
        }
4

1 回答 1

2

Though you have not described exactly what the problem is, I would assume that, in your first code, the for-loop inside the while loop of your sort method is giving you a problem: -

    for(int in = out+1; in < n; n++) {
        if(a[in] < a[out])
            smaller++;
    }

Here, you are incrementing n++ rather than in++. Check onto that. Change it to in++. You might be getting into infinite loop because of that.

Also, there is a problem in your swap method. You have invoked your swap method with actual array element, but you are considering them as indices in the method.

swap(a[out], a[smaller]);  // Called with element `a[out]`

private void swap (int one, int two) {

    int temp=a[one];    // This is equivalent to a[a[out]]
    a[one]=a[two];
    a[two]=temp;
}

You can just pass index to your method: -

So, invoke your swap method like : - swap(out, smaller);

UPDATE: -In your while loop of sort method, add smaller = 0; as the first statement. To re-initialize it to 0.

于 2012-10-13T10:40:14.437 回答