Сортировка - C (СИ) (69769)

Узнай цену своей работы

Формулировка задачи:

Добрый вечер. Есть такое задание:

Составить программу, которая для массива, заполненного случайными целыми числами, проводит сортировку по неубыванию методом выбора (выделения). Подсчитать количество присваиваний и количество сравнений при сортировке.

Программу я составил, но не знаю, как найти количество присваиваний и сравнений. Помогите, пожалуйста.

Решение задачи: «Сортировка»

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
 
int c_swap;
int c_comp;
 
void VSort(int *A,int n)
{
     int i,j,t,k;
     for (i=0; i<n-1; i++)
     {
         k=i;
         for (j=i+1; j<n; j++)
             { if (A[j]<A[k]) k=j; c_comp++; }
         if (k != i)
         {
            t=A[k];
            A[k]=A[i];
            A[i]=t;
            c_swap++;
         }
     }                                        
}
 
 
int main(int argc, char *argv[])
{
 
  int i,Arr[10]={5,2,3,4,1,2,3,4,5,-5}; 
  
  
  printf("Array before sorting: \n");
  for (i=0; i<10; i++) printf("%d ",Arr[i]);
  printf("\n");
  
  c_comp=c_swap=0;
  VSort(Arr,10);
 
  printf("Array after sorting: \n");
  for (i=0; i<10; i++) printf("%d ",Arr[i]);
  printf("\n\n");
  
  printf("Number of comparing=%d\n",c_comp);
  printf("Number of exchanging=%d\n",c_swap);
  printf("\n");
  
  system("PAUSE");  
  return 0;
}

Объяснение кода листинга программы

В данном коде реализуется сортировка массива методом пузырька.

  1. Создаются две переменные-счетчика: c_swap и c_comp, которые используются для отслеживания количества выполненных операций обмена и сравнения элементов.
  2. В функции VSort() происходит сортировка массива.
  3. В цикле for перебираются все элементы массива, начиная с первого (i=0) и до n-1 (где n - размер массива).
  4. Для каждого элемента массива (в каждой итерации цикла) происходит поиск его правильного положения путем сравнения со всеми последующими элементами.
  5. Если текущий элемент больше следующего, они меняются местами, и увеличивается счетчик c_swap.
  6. После завершения цикла, массив будет отсортирован по возрастанию.
  7. В функции main() создается массив Arr, заполняется значениями для примера.
  8. Выводится на экран содержимое массива до сортировки.
  9. Задаются начальные значения счетчиков c_comp и c_swap.
  10. Вызывается функция VSort(), которая сортирует массив Arr.
  11. Выводится на экран отсортированный массив Arr.
  12. Выводятся на экран значения счетчиков c_comp и c_swap.
  13. Запускается команда PAUSE, предназначенная для приостановки выполнения программы до нажатия клавиши.
  14. Возвращается 0, что означает успешное завершение программы.

Оцени полезность:

12   голосов , оценка 3.917 из 5
Похожие ответы