Есть ли разница между двумя функциями?

Question

[Vadim kyklaed]

Привет, подскажите есть ли разница между двумя функциями ? за какое время они выполняются ?
Первую написал я, вторую нашел в интернете, суть в том что бы циклично сдвигать элементы в массиве на определенный шаг.

моя функция первая там я использую доп память- лучше вариант так и не смог придумать

#include <iostream>
using namespace std;

void rotate(int a[], unsigned size, int shift)
{
    int b[size]={};
  	if (shift> size){
  		shift=size;   
	}
	for (int i=shift;i<size;i++){
			b[i - shift]=a[i];    
	        } 
	for (int i=size-shift;i<size;i++){
		b[i]=a[i-(size-shift)];
	}
	a=b;
    for (int i=0;i<size;i++){
		cout<<b[i]<<" ";
	}
	
}

void rotate2(int a[], unsigned size, int shift){
	
	int temp;
    for (int i = 0, j; i < shift; ++i)
    {
        temp = a[0];
        for (j = 0; j < size - 1; ++j)
            a[j] = a[j + 1];
        a[j] = temp;
    }
     for (int i=0;i<size;i++){
		cout<<a[i]<<" ";
	}
}




int main(){
	int shift = 7;
	unsigned size = 7;
	int a[size]={1,2,3,4,5,6,7};
	
	rotate2(a, size , shift);
	return 0;
}

Comments

[Roman]

"за какое время они выполняются ?" если Вы имеете ввиду нотацию О(n) то там не время а рост кол-ва операций

Answer 1

[Roman]

не изобретайте велосипед)))
библиотека STL
используйте std::vector
и std::rotate

определение и пример
en.cppreference.com/w/cpp/algorithm/rotate

Answer 2

[Adamos]

Мы же говорим о С++, судя по вашим тегам, а не о С, правда?
В С++ логичнее сделать класс-обертку массива, который при обращении к его элементам будет производить элементарную арифметику пересчета индекса. А не колупаться в памяти, как будто вы на калькуляторе программируете.

Answer 3

[Mercury13]

1. Будьте осторожны, перед нами динамический массив, сделанный расширением стека. Не на всех компиляторах есть, плюс стек ограничен парой мегабайт.
Нормализацию размера лучше сделать shift %= size;
Подпрограмма работает с локальной переменной и всё, что она делает, идёт на экран и больше никуда.
(вообще стоит разделять обработку и вывод!)
Время работы size.

2. Сдвигаем на один элемент нужное количество раз. Время работы shift·size.

3. Как за size «на месте»…

квоПрох := НОД(shift, size)
для i = [0..квоПрох)
  i1 := i
  tmp := a[i]
  вечный цикл
    i2 := (i1 + shift) % size
    если i2 = i
      прервать вечный цикл
    a[i1] := a[i2]    
    i1 := i2
  a[i1] := tmp

Answer 4

[res2001]

Ваша функция работает делает свое дело за 1 проход по массиву, второй вариант - за shift проходов - сложность O(N) и O(N*shift) соответственно. Во втором случае скорость зависит от величины сдвига, что очень плохо для такого алгоритма.

Циклический сдвиг массива "на месте" реализуется с помощью трех операций revers (операция изменения порядка элементов на противоположный):
1.весь массив делится на 2 массива в точке сдвига (условно, без выделения памяти)
2.revers первой части
3.revers второй части
4.revers всего массива
Встречал на stackoverflow реализацию на Си.
Работает за 2 полных прохода с операциями swap по массиву - O(2*N), но каждая операция тяжелее чем в ваших вариантах. Но быстродействие не зависит от величины сдвига и не требует дополнительной памяти, что может быть важно при работе с массивами большой размерности.
UPD: вспомнил, этот способ был описан в книге Бентли "Жемчужины программирования"!