0

Я хочу понять циклическую сортировку. Приведенный ниже код не мой.

#include <stdio.h>
#include <stdlib.h>
 
int cycleSort(int * list, size_t l_len);
void show_array(int * array, size_t a_len);
 
/*
 * Sort an array in place and return the number of writes.
 */
int cycleSort(int * list, size_t l_len)
{
  int writes = 0;
 
  /* Loop through the array to find cycles to rotate. */
  for (int cycleStart = 0; cycleStart < l_len - 1; ++cycleStart)
  {
    int item = list[cycleStart];
    int swap_tmp;
 
    /* Find where to put the item. */
    int pos = cycleStart;
    for (int i = cycleStart + 1; i < l_len; ++i)
    {
      if (list[i] < item)
      {
        ++pos;
      }
    }
 
    /* If the item is already there, this is not a cycle. */
    if (pos == cycleStart)
    {
      continue;
    }
 
    /* Otherwise, put the item there or right after any duplicates. */
    while (item == list[pos])
    {
      ++pos;
    }
    swap_tmp = list[pos];
    list[pos] = item;
    item = swap_tmp;
    ++writes;
 
    /* Rotate the rest of the cycle. */
    while (pos != cycleStart)
    {
      /* Find where to put the item. */
      pos = cycleStart;
      for (int i = cycleStart + 1; i < l_len; ++i)
      {
        if (list[i] < item)
        {
          ++pos;
        }
      }
 
      /* Put the item there or right after any duplicates. */
      while (item == list[pos])
      {
        ++pos;
      }
      swap_tmp = list[pos];
      list[pos] = item;
      item = swap_tmp;
      ++writes;
    }
  }
 
  return writes;
}
 
int main(int argc, char ** argv)
{
  int arr[] = { 0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6, };
  int arr_k = sizeof(arr) / sizeof(arr[0]);
  int writes;
 
  show_array(arr, arr_k);
  writes = cycleSort(arr, arr_k);
  show_array(arr, arr_k);
  printf("writes: %d\n", writes);
 
  return 0;
}
 
void show_array(int * array, size_t a_len)
{
  for (int ix = 0; ix < a_len; ++ix)
  {
    printf("%d ", array[ix]);
  }
  putchar('\n');
 
  return;
}
  1. При инициализации функции cycleSort() указывается int *list, size_t l_len. Правильно ли я понимаю, что int *list - это указатель на целочисленный массив? Правильно ли я понимаю, что size_tl_len - это размер массива? Если да, то как еще можно представить size_t, например, int SIZE?

  2. Строка int main(int argc, char **argv) {. Почему мы вообще объявили int argc, char **argv? Я спрашиваю, потому что я не видел переменную argc в теле main() и абсолютно не понимал, что такое **argv. Является ли это двойным указателем на массив? Тогда возникает вопрос, чем его можно заменить, например, *mass? Или ** означает указатель на динамический массив? Нужно ли использовать имена argc и **argv, например, мне нравятся просто variable и **pointer_dynamic_mass?

1 ответ 1

1
  1. Верно, int *list — это указатель на массив целочисленных данных, равно как и size_t l_len — размер массива. Что же касается других вариантов, то можно использовать и int в качестве типа — если точно уверены, что передастся именно неотрицательное число. size_t, как можно выяснить из ответов к этому вопросу, есть псевдоним для одного из беззнаковых типов (32 или 64-битного целого типа), предназначенный для отображения размера любого объекта в байтах.
  2. Мы можем и не объявлять параметры int argc, char** argv, т.е. это необязательные аргументы, предназначенные для количества аргументов командной строки и массива всех строк этой же командной строки соответственно. Более подробную информацию Вы можете прочесть, например, здесь.
1
  • Благодарю. Эмпирическим путем до получения вашего ответа на 2 вопрос дошел! Commented 15 мая 2022 в 20:26

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.