Будет ли этот код сортировки выбора работать в O (n) для лучшего случая?

Question

Я ищу всюду в целых числах rnet для наилучшей временной сложности выбора сортировки, которая равна o (n ^ 2). Но я пишу и тестирую приведенный ниже код сортировки выбора, который может работать в O (n) для лучшего случая (то есть массив уже отсортирован). Пожалуйста, найдите ошибку в этой программе

Это мой код:

#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

Answer 1

Да, ваш алгоритм имеет наилучшее время выполнения Θ (n), потому что если массив уже находится в возрастающем порядке, то count будет равно n - 1 на первой итерации внешнего l oop, поэтому алгоритм завершится рано.

Ваш алгоритм отличается от стандартного алгоритма сортировки выбора, который выглядит следующим образом:

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

Алгоритм сортировки выбора итеративно ищет минимальный оставшийся элемент и переставляет это на место. Это не создает возможности обнаружить, что массив уже находится в возрастающем порядке, поэтому нет возможности завершить его раньше, и поэтому наилучшее время выполнения сортировки выбора составляет Θ (n ² ).

Answer 2

Сортировка выбора: Идея. Задан массив из n элементов. 1. Найдите самый большой элемент x в диапазоне [0… n − 1]. 2. Поменяйте местами x с (n − 1) -ым элементом. 1 и go до шага 1

Функция сортировки выбора, которую вы можете использовать, используя следующий алгоритм, имеет подсказку для написания кода: