CODEWITHSUNDEEP
performancesortingtime-complexitycomplexity-theoryselection-sort
VivekPrasad
VivekPrasad

Reputation: 1

What will be the time complexity of this modified selectionSort code?

void simpleSort(int arr[], int arrSize){

    /*initial searchSpace bounds*/
    int left = 0;
    int right = arrSize-1;
    
    int maxElem, minElem, maxElemIndex, minElemIndex;

    while(left < right){

        /*setting default value for max and min in the array*/
        maxElem = minElem = arr[left];
        minElemIndex = maxElemIndex = left;

        //1. iterate array to find index of min and max elements
        for(int i = left; i<= right; i++){
            if(arr[i] >= maxElem){
                maxElem = arr[i];
                maxElemIndex = i;
            }
            if(arr[i] <= minElem){
                minElem = arr[i];
                minElemIndex = i;
            }
        }

        //2. swap the min and max elements with leftmost and rightmost elements (for sorting in            ascending order)
        if(left == maxElemIndex && right == minElemIndex){
            /*here if we do 2 swaps then both swaps will nullify each other*/
            swap(arr[left], arr[minElemIndex]);
        }
        else if(left == maxElemIndex){
            swap(arr[right], arr[maxElemIndex]);
            swap(arr[left], arr[minElemIndex]);
        }
        else{
            swap(arr[left], arr[minElemIndex]);
            swap(arr[right], arr[maxElemIndex]);
        }

        //3. converging the searchSpace window as the leftmost and rightmost elements are sorted now
        left++;
        right--;
    }
}

Here I have tried to improve up on the selection sort algorithm by finding the minimum as well as the maximum element during each pass and then swapping them with the rightmost and leftmost elements of the search space. The search space is initially equal to the size of the input array and it decreases by 2 after each pass as we sort 2 elements in each pass.

I think its time-complexity to be O(n^2) because of the nested loops I've used.

Upvotes: -1

Views: 55

Answers (1)

forest-spells
forest-spells

Reputation: 158

The time complexity of this implementation in O-notation is O(n^2), since the constant in O-notation is omitted.

If you want to significantly reduce the computational complexity, I suggest using Merge Sort, whose complexity is O(n*log(n)). The principle of the algorithm is shown here: Merge Sort

Upvotes: 0

Related Questions