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 &lt; l_len; ++i)
{
  if (list[i] &lt; 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 &lt; l_len; ++i)
  {
    if (list[i] &lt; 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?

Виктория Благодер
  • 17

1 Answers1

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