CODEWITHSUNDEEP
java
Lifter
Lifter

Reputation: 77

Index sort. Something really weird is going on

       public int[] indexSort(){
    int[] sortedarr = new int[max];

    for(int i=0;i<max;i++){
        int key=0;
        int duplicates = 0;
        for(int j=0;j<max;j++){
            if(arr[i]>arr[j]) key++;
            else if(arr[i]==arr[j]) duplicates++;

        }
        while(duplicates>0&&key<max){


            sortedarr[key] = arr[i];
            key++;
            duplicates--;
        }
    }
    return sortedarr; }

How comes does the while loop work? Even when there are no duplicates(duplicates=0), the while loop is still executed.

My mind is puzzled. Also is index sort supposed to run by O(n^3)?

Upvotes: 0

Views: 62

Answers (1)

Denys S&#233;guret
Denys S&#233;guret

Reputation: 382150

There's always a "duplicate" : when i == j.

You should probably start the inner loop at i+1 :

for(int i=0;i<max;i++){
    int key=0;
    int duplicates = 0;
    for(int j=i+1;j<max;j++){

Upvotes: 1

Related Questions