Выбор алгоритма сортировки

Анализируйте сортировку выбора с помощью асимптотики Big O построчно!

ОБЗОР

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

arr[] = 65 25 12 22 10

// Find the minimum element in arr[0...4]
// and place it at beginning
10 30 12 22 65

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
10 12 30 22 65

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
10 12 22 30 65

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
10 12 22 30 65

Код сортировки выбора

Выборка Сортировка анализа программы C

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

 // C program for implementation of selection sort
//NOTE: REMOVE The Line Numbers (e.g. Line 1.) if you want to run this code
// I inserted them to help with the analysis
#include <stdio.h>
void selectionSort(int arr[], int n)
{
 Line 1.int i, j, min_idx;
  
  // One by one move boundary of unsorted subarray
 Line 2. for (i = 0; i < n; i++){
// Find the minimum element in unsorted array
 Line 3.    min_idx = i;
 Line 4. for (j = i+1; j < n; j++){
 Line 5.        if (arr[j] < arr[min_idx])
 Line 6.           min_idx = j;}
// Swap the found minimum element with the first element
 Line 7.    int temp = arr[min_dx];
 Line 8.    arr[min_dx] = arr[i];
 Line 9.    arr[i] = temp;
   }
}
/* Function to print an array */
void printArray(int arr[], int size){
  int i;
  for (i=0; i < size; i++)
     printf("%d ", arr[i]);
  printf("\n");
}
// Driver program to test above functions
int main(){
  int arr[] = {64, 25, 12, 22, 11};
  int n = sizeof(arr)/sizeof(arr[0]);
  selectionSort(arr, n);
  printf("Sorted array: \n");
  printArray(arr, n);
return 0;
}

randerson112358 / C-программы
C-программы -: dog: Fun C Programs github.com

Внутри функции selectionSort:

Строка 1: COST = C1, TIME = 1, где C1 - некоторая константа
Строка 2: COST = C2, ВРЕМЯ = n + 1, где C2 - некоторая константа
Строка 3: COST = C3, TIME = n, где C3 - некоторая константа
Строка 4: СТОИМОСТЬ = C4, ВРЕМЯ = (n²-n) / 2 + n, где C4 - некоторая константа
Строка 5: COST = C5, TIME = (n²-n) / 2, где C5 - некоторая константа
Строка 6: COST = C6, ВРЕМЯ = (n²-n) / 2, где C6 - некоторая константа
Строка 7: COST = C7, TIME = n , где C7 - некоторая константа
Строка 8: COST = C8, TIME = n, где C5 - некоторая константа
Строка 9: СТОИМОСТЬ = C9, ВРЕМЯ = n, где C9 - некоторая константа.

Видео, показывающее, как я вычислил ВРЕМЯ для каждой выполняемой строки кода, находится ниже, или вы можете нажать здесь, чтобы посмотреть. Теперь, когда у нас есть все затраты и времена, мы должны суммировать все затраты, умноженные на время выполнения:

Время выполнения = (C1 * 1) + (C2 * (n + 1)) + (C3 * n) + (C4 * ((n²-n) / 2) + n) + (C5 * (n²-n) / 2) + (C6 * (n²-n) / 2) + (C7 * n) + (C8 * n) + (C9 * n)

Где U, V и W - константы
= U + Vn + Wn²
= O (n²)

Если вы хотите узнать больше об Анализ алгоритмов, вы можете пройти мой онлайн-курс здесь. У меня также есть курс на Udemy.com под названием Recurrence Relation Made Easy, где я помогаю студентам понять, как решать повторяющиеся отношения и асимптотические термины, такие как Big-O, Big Omega и Theta. Вы можете посмотреть мой канал на YouTube с видео, где я решаю рекуррентные отношения и выполняю анализ алгоритмов кода, который любой может проверить бесплатно!

Введение в анализ алгоритмов [для начинающих]
Понимание и решение алгоритмов с использованием временной сложности Big O, Big Omega и Theta. www.udemy.com

Упрощение отношений повторяемости | Udemy
Руководство по решению любой программы рекурсии или отношения повторения. www.udemy.com

Спасибо за прочтение этой статьи, надеюсь, она будет вам полезна! Продолжайте учиться, и если вы хотите больше видео по информатике, программированию и анализу алгоритмов, посетите и подпишитесь на мои каналы YouTube (randerson112358 и compsci112358)