CODEWITHSUNDEEP
algorithmsortingtime-complexitycomplexity-theoryselection-sort
Asad Ali Bhatti
Asad Ali Bhatti

Reputation: 1

Will this Selection Sort Code work in O(n) for best case?

I search everywhere on the internet for the best case time complexity of selection sort that is o(n^2). But i write and tested this below code of selection sort that can work in O(n) for best case (that is array is already sorted). Please find the mistake in this program

This is my code:

#include <bits/stdc++.h>
using namespace std;
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selectionSort(int arr[], int n)
{
    int i, j, max_idx;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n - 1; i++)
    {
        cout << endl;
        printArray(arr, n);

        // Find the minimum element in unsorted array
        max_idx = 0;
        int count = 0;
        for (j = 1; j < n - i; j++)
        {
            if (arr[j] >= arr[max_idx])
            {
                max_idx = j;
                count++;
            }
        }

        if (count != n - i - 1)
        {   //swap only if not already sorted
            // Swap the found minimum element with the first element
            swap(&arr[max_idx], &arr[n - i - 1]);
        }
        else //already Sorted so returning
        {
            return;
        }
        //cout << "Sorted array: \n";
        printArray(arr, n);
    }
}

// Driver program to test above functions
int main()
{
    int arr[] = {2, 1, 4, 3, 6, 5, 8, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

// This is code is contributed by www.bhattiacademy.com

Upvotes: 0

Views: 840

Answers (2)

user607464
user607464

Reputation: 23

Selection Sort: Idea Given an array of n items 1.Find the largest item x, in the range of [0…n−1] 2.Swap x with the (n−1)th item 3.Reduce n by 1 and go to Step 1

Selection sort function you can use following algorithm has hint to write the code: enter image description here

Upvotes: 0

kaya3
kaya3

Reputation: 51102

Yes, your algorithm has a best case running time of Θ(n), because if the array is already in ascending order then count will equal n - 1 on the first iteration of the outer loop, so the algorithm will terminate early.

Your algorithm is different to the standard selection sort algorithm, which looks like this:

for(int i = 0; i < n - 1; i++) {
    int min_idx = i;
    for(int j = i + 1; j < n; j++) {
        if(arr[j] < arr[min_idx]) {
            min_idx = j;
        }
    }
    swap(&arr[i], &arr[min_idx]);
}

The selection sort algorithm iteratively searches for the minimum remaining element and swaps it into place. This doesn't create an opportunity to detect that the array is already in increasing order, so there's no opportunity to terminate early, and selection sort's best case running time is therefore Θ(n2).

Upvotes: 2

Related Questions