[ create a new paste ] login | about

Link: http://codepad.org/qK2sD1jn    [ raw code | output | fork ]

C++, pasted on Dec 2:
#include <iostream>

int main()
{
    int i; 
    int tmp; 
    int comp; // количество сравнений
    int per; //  количество перестановок
    int N=10;
    int a[11];
 
//заполнение массива почти отсортированными данными
    for (i = 0; i < N-1; ++i) // цикл проходов, i - номер прохода
    {
        a[i]=i+1; 
    }
  a[N-1]=0;       
 
  for (int i = 0; i <= N-1; i++) {
        std::cout << a[i] <<" ";
    }

  std::cout<<" Исходный массив (почти отсортированный)"<<std::endl; 
   per=0;
   comp=0;
   for (int i = 1, j; i < N; ++i) // цикл проходов, i - номер прохода
    {
      tmp = a[i]; 
      for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
    {      
    a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
    ++per;  
    ++comp;
 }
          a[j + 1] = tmp; // место найдено, вставить элемент    
    ++per; 
   }

     for (int i = 0; i <= N-1; i++) {
        std::cout << a[i] << " ";
    }
     std::cout<<" Массив, отсортированный методом вставки"<<std::endl; 
     std::cout<<per<<" перестановок "<<comp<<" сравнений"<< std::endl; 



//заполнение массива случайными данными
    for (i = 0; i < N; ++i) // цикл проходов, i - номер прохода
    {
        a[i]=rand() % 9 ; 
    }

  for (int i = 0; i <= N-1; i++) {
        std::cout << a[i] << " ";
    }
  std::cout<<" Исходный массив (случайный)"<<std::endl; 
   per=0;
   comp=0;

  for (int i = 1, j; i < N; ++i) // цикл проходов, i - номер прохода
    {
      tmp = a[i]; 
      for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
    {      
    a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
    ++per;  
    ++comp;
 }
          a[j + 1] = tmp; // место найдено, вставить элемент    
    ++per; 
   }
     for (int i = 0; i <= N-1; i++) {
        std::cout << a[i] << " ";
    }
     std::cout<<" Массив, отсортированный методом вставки"<<std::endl; 
     std::cout<<per<<" перестановок "<<comp<<" сравнений"<< std::endl; 

//заполнение массива перевёрнутыми данными данными
    for (i = 0; i < N; ++i) // цикл проходов, i - номер прохода
    {
        a[i]=N-i-1; 
    }

  for (int i = 0; i <= N-1; i++) {
        std::cout << a[i] <<" ";
    }
  std::cout<<" Исходный массив (перевёрнутый)"<<std::endl; 
   per=0;
   comp=0;
     std::cout<<per<<" перестановок "<<comp<<" сравнений"<< std::endl; 

   for (int i = 1, j; i < N; ++i) // цикл проходов, i - номер прохода
    {
      tmp = a[i]; 
      for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
    {      
    a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
    ++per;  
    ++comp;
 }
          a[j + 1] = tmp; // место найдено, вставить элемент    
    ++per; 
   }
     for (int i = 0; i <= N-1; i++) {
        std::cout << a[i] << " ";
    }
     std::cout<<" Массив, отсортированный методом вставки"<<std::endl; 
     std::cout<<per<<" перестановок "<<comp<<" сравнений"<< std::endl; 




  return 0;
}


Output:
1
2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9 0  Исходный массив (почти отсортированный)
0 1 2 3 4 5 6 7 8 9  Массив, отсортированный методом вставки
18 перестановок 9 сравнений
1 7 0 7 5 7 1 3 6 1  Исходный массив (случайный)
0 1 1 1 3 5 6 7 7 7  Массив, отсортированный методом вставки
30 перестановок 21 сравнений
9 8 7 6 5 4 3 2 1 0  Исходный массив (перевёрнутый)
0 перестановок 0 сравнений
0 1 2 3 4 5 6 7 8 9  Массив, отсортированный методом вставки
54 перестановок 45 сравнений


Create a new paste based on this one


Comments: