CODEWITHSUNDEEP
arraysalgorithmsortingdata-structuresinsertion-sort
Ashish shah
Ashish shah

Reputation: 19

is there any problem in the terms of time complexity in this code?

So today I was learning selection sort, and gain the concept how actually selection sort it working(i mean we add new element in the sorted array then check that element if it is on its correct position or not, right?) so without watching anyone's pseudo code or code I tried by myself and wrote this code:

vector<int> arr = {6, 5, 4, 3, 2, 1};
    int arrayLength = arr.size();
    for(int i = 0; i < arrayLength; i++){
        for(int j = i; j > 0; j--){
                bool flag = true;
                if(arr[j] < arr[j - 1]){
                        int temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                        flag = false;
                }
                if(flag == true) break;
        }
    }
// output: 1, 2, 3, 4, 5, 6

bool flag = true; //if the newly added element is at its correct position then don't do anything in the next iteration and break the inner iteration because we already have sorted array in which we're adding new element and checking if that element is at its correct position or not, if not then we're swaping it.

Everyone is using while loop which is great but still in both way: best and worst TC is: O(n) and O(n2).

for (int i = 0; i <= n - 1; i++) {
            int j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
                j--;
            }
        }
// output: 1, 2,3 ,4 5, 6

or am I calculating wrong?

So I tried every possible input and even I run this code on GFG https://www.geeksforgeeks.org/user/thisisashishshah/, and this is giving correct as so many ppl using that while loop, I'm little bit confused if am I doing bad in the terms of TC.

Upvotes: 1

Views: 69

Answers (1)

MBo
MBo

Reputation: 80287

This is kind of insertion sort without shift-optimization (better version is the second code at wiki page), not selection sort.

Best and worst times O(n) and O(n^2) are correct for it, but not for true selection sort, where the best case is O(n^2) too.

You can see the table with time and memory here

Upvotes: 1

Related Questions