What is time complexity of my sorting algorithm?

Question

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;
}   
}

You say this is "similar to insertion sort", but it seems to be identical to the pseudocode of insertion sort from wikipedia: en.wikipedia.org/wiki/Insertion_sort#Algorithm . Do you think it's different because you use a comparator rather than just <= ? The time complexity of a sort counts the number of comparisons performed no matter what they are or how complicated. — Paul Hankin
– Paul Hankin, Commented Feb 3, 2022 at 8:59
It's not your question, but std::sort from the C++ standard library allows you to specify a comparator, and using standard library sort is likely to be more efficient than a hand-written sort. — Paul Hankin
– Paul Hankin, Commented Feb 3, 2022 at 9:02

user1984 · Accepted Answer · 2022-02-02 18:51:23Z

3

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

answered Feb 2, 2022 at 18:51

user1984

6,9383 gold badges17 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What is time complexity of my sorting algorithm?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related