Оптимизированный выбор Сортировка?

Question

Я прочитал источники, которые говорят, что временные сложности для выбора рода являются:

• Лучший случая: O (N^2)
• Средне-случай: O (N^2)
• Худшая -случае: O (N^2)

было интересно, если это стоит «оптимизировать» алгоритм, добавив определенную строку кода, чтобы сделать алгоритм «короткое замыкание» само по себе, если оставшаяся часть уже отсортирована.

Вот код, написанный на C:

Я также добавил комментарий, который указывает, какие строки являются частью «оптимизации» части.

void printList(int* num, int numElements) 
{ 
    int i; 
    for(i = 0; i < numElements; i ++) { 
     printf("%d ", *(num + i)); 
    } 
    printf("\n"); 
} 

int main() { 

    int numElements = 0, i = 0, j = 0, min = 0, swap = 0, numSorted = 0; 

    printf("Enter number of elements: "); 
    scanf("%d", &numElements); 

    int* num = malloc(sizeof(int) * numElements); 

    for(i = 0; i < numElements; i ++) { 
     printf("Enter number = "); 
     scanf(" %d", num + i); 
    } 

    for(i = 0; i < numElements-1; i++) { 

     numSorted = i + 1; // "optimized" 
     min = i; 

     for(j = i + 1; j < numElements; j++) { 
      numSorted += *(num + j - 1) <= *(num + j); // "optimized" 
      if(*(num + min) > *(num + j)) 
       min = j; 
     } 

     if (numSorted == numElements) // "optimized" 
      break; 

     if (min != i) { 
      swap = *(num + i); 
      *(num + i) = *(num + min); 
      *(num + min) = swap; 
     } 

     printList(num, numElements); 
    } 

    printf("Sorted list:\n"); 
    printList(num, numElements); 

    free(num); 

    getch(); 
    return 0; 

} 

Answer 1

Оптимизация выбора сортировки немного глупо. У этого есть ужасная случайная, средняя и худшая временная сложность, поэтому, если вы хотите удаленно оптимизированную сортировку, вы бы (почти?) Всегда выбираете другой вид. Даже сортировка вставки имеет тенденцию быть более быстрой, и ее вряд ли намного сложнее реализовать.

Более подробно, проверяя, отсортирован ли список, увеличивается время, затрачиваемое алгоритмом на сценарии наихудшего случая (средний случай тоже я склонен думать). И даже в основном отсортированный список не обязательно будет идти быстрее: рассмотрите 1,2,3,4,5,6,7,9,8. Несмотря на то, что в списке требуется только два элемента, замененных в конце, алгоритм не будет замыкаться, поскольку он никогда не сортируется до конца.