CODEWITHSUNDEEP
c++algorithmsorting
Filgum0326
Filgum0326

Reputation: 75

What is time complexity of my sorting algorithm?

It is similar to insertion sort with swap, and for three standards. For example if user inputs 1,2,3 the priority is to sort by height, then weight and then age. I have comparator as well. The thing is I am not sure about time complexity. Is it going to be O(n^2)? If yes can anyone explain why? Ofc I'm talking about the worst scenario.

struct Person{
string name;
float height;       // 1
int weight;         // 2
short int age;      // 3
};

bool comparePeople(Person a, Person b, short int standardOne, short int standardTwo, short int standardThree )
{

if(standardOne == 1 ){  
        if( standardTwo == 2){

        if (a.height != b.height)
        return a.height < b.height;

        if (a.weight != b.weight)
        return a.weight < b.weight;

        return (a.age < b.age); 
    }
    else{ // 1,3,2
        if (a.height != b.height)
        return a.height < b.height;

        if (a.age != b.age)
        return a.age < b.age;

        return (a.weight < b.weight);   
    }
}else if(standardOne == 2 ){ 
    if( standardTwo == 1){
        if (a.weight != b.weight)
        return a.weight < b.weight;

        if (a.height != b.height)
        return a.height < b.height;

        return (a.age < b.age); 
    }
    else{ 
        if (a.weight != b.weight)
        return a.weight < b.weight;

        if (a.age != b.age)
        return a.age < b.age;

        return (a.height < b.height);   
    }
}else if(standardOne == 3 ){ 
    if( standardTwo == 1){
        if (a.age != b.age)
        return a.age < b.age;

        if (a.height != b.height)
        return a.height < b.height;

        return (a.weight < b.weight);   
    }
    else{ //3,2,1
        if (a.age != b.age)
        return a.age < b.age;

        if (a.weight != b.weight)
        return a.weight < b.weight;

        return (a.height < b.height);   
    }
}
}

void sort(Person *GroupOne, short int standardOne, short int standardTwo, short int standardThree, int n){
for(int i = 1; i < n; i++) {
    Person key = GroupOne[i];
    int j = i - 1;
    while (j >= 0 && comparePeople(GroupOne[j],GroupOne[j+1], standardOne, standardTwo, standardThree)) {
        Person temp = GroupOne[j+1];
        GroupOne[j+1] = GroupOne[j];
        GroupOne[j] = temp;
        j--;
    }
    GroupOne[j+1] = key;
}   
}

Upvotes: 3

Views: 111

Answers (1)

user1984
user1984

Reputation: 6808

Yes, it's a quadratic sorting algorithm as you stated in your question. The reasoning is this:

The main part of the code runs a nested loop as follows:

for(int i = 1; i < n; i++) {
   int j = i-1
   while (j >= 0...

where you do constant work inside the inner loop.

In the worst case, the inner loop iterates i times for each iteration of the outer loop. This create the following famous sequence: 1 + 2 +...+ n-1 + n, which equals n * (n+1)/2. In Big O terms this is O(n^2).

Upvotes: 3

Related Questions