Блог

 int main() { 
    int arr[] = { 64, 25, 12, 22, 11 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    
    selectionSort(arr, n); 
   
    return 0;  
}

void selectionSort(int arr[], int n) { 
    int i, j, min_idx; 
  
    // One by one move boundary of unsorted subarray 
    for (i = 0; i < n - 1; i  ) { 
        // Find the minimum element in unsorted array 
        min_idx = i; 
        for (j = i   1; j < n; j  ) 
            if (arr[j] < arr[min_idx]) 
                min_idx = j; 
  
        // Swap the found minimum element with the first element 
        swap(amp;arr[min_idx], amp;arr[i]); 
    } 
} 
 

Я вижу этот код на языке C, который будет выполнять алгоритмы сортировки, называемые сортировкой по выбору. Но мой вопрос в selectionSort функции.

Почему в первом for цикле условие является условием i < n - 1 , тогда как во втором цикле оно есть j < n ?

Что i < n - 1 именно будет делать? и почему разные случаи для второго цикла? Не могли бы вы, пожалуйста, объяснить мне этот код, как будто я учусь в шестом классе начальной школы. Спасибо.

Первый цикл должен повторяться до индекса n-2 (таким образом i < n-1 ), потому что второй цикл for должен проверять числа от i 1 до n-1 (таким образом j < n ). Если i бы можно было получить значение n - 1 , то доступ к if (arr[j] < arr[min_idx]) нему был бы вне пределов, в частности arr[j] , был бы вне пределов для j==n .

Можно подумать, что эта реализация сортировки выбора перемещается слева направо по массиву, оставляя всегда отсортированный массив слева от него. Вот почему второй цикл for начинает посещать элементы из индекса i 1 .

Вы можете найти много ресурсов в Интернете, чтобы наглядно представить, как работает сортировка по выбору, например, сортировка по выбору в Википедии

Реализация в Википедии снабжена комментариями и объясняет это.

 /* advance the position through the entire array */
/*   (could do i < aLength-1 because single element is also min element) */
for (i = 0; i < aLength-1; i  )
 

Сортировка по выбору выполняется путем нахождения наименьшего элемента и замены его на место. Когда остается только один несортированный элемент, он является наименьшим несортированным элементом и находится в конце отсортированного массива.

Например, допустим, у нас есть {3, 5, 1} .

 i = 0 {3, 5, 1}  // swap 3 and 1
       ^
i = 1 {1, 5, 3}  // swap 5 and 3
          ^
i = 2 {1, 3, 5}  // swap 5 and... 5?
             ^
 

Для трех элементов нам нужно всего два обмена. Для n элементов нам нужно всего n-1 обменов.

Это оптимизация, которая может немного повысить производительность на очень маленьких массивах, но в остальном несущественна в алгоритме O (n ^ 2), таком как сортировка по выбору.

Почему в первом цикле for условие i <n-1? Но во втором цикле j < n?

Условие цикла для внутреннего цикла заключается j < n в том, что индекс последнего элемента, подлежащего сортировке n - 1 , равен , так что, когда j >= n мы знаем, что он прошел конец данных.

Условие цикла для внешнего цикла могло быть i < n , но обратите внимание, что тогда на итерации не было бы выполнено никакой полезной работы при i принятии значения n - 1 . Начальное значение j во внутреннем цикле равно i 1 , что в этом случае было бы n . Таким образом, никакие итерации внутреннего цикла не будут выполняться.

Но отсутствие полезной работы — это не то же самое, что отсутствие работы вообще. На каждой итерации внешнего цикла, в которой i принималось значение n - 1 , будет выполняться некоторая бухгалтерия, и arr[i] она будет заменена самой собой. Остановка внешнего цикла на одну итерацию раньше позволяет избежать этой гарантированно бесполезной дополнительной работы.

Все это напрямую связано с тем фактом, что для сортировки одноэлементного массива не требуется никакой работы.

Вот логика этих вложенных циклов:

• для каждой позиции i в массиве
  • найдите наименьший элемент фрагмента, начинающийся с этой позиции и продолжающийся до конца массива
  • поменяйте местами наименьший элемент и элемент в позиции i

Очевидно, что наименьший элемент фрагмента из 1 элемента в конце массива уже на месте, поэтому нет необходимости запускать последнюю итерацию внешнего цикла. Это причина, по которой во внешнем цикле должен быть тест i < n - 1 .

Однако обратите внимание, что в этом тесте есть неприятная ошибка: если вместо int мы используем size_t для типа индекса и количества элементов в массиве, что более правильно, поскольку в настоящее время массивы могут содержать больше элементов, чем диапазон типов int , i < n - 1 было бы верно для i = 0 и n = 0 потому n - 1 , что не отрицательно, а наибольшеезначение size_t , которое огромно. Другими словами, код завершит работу с пустым массивом.

Было бы безопаснее написать:

     for (i = 0; i   1 < n; i  ) { ...