I have a quick question about my sorting algorithm, it is similiar 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;
}
}
>Solution :
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).