rotate algorithm

Hi,

ich habe versucht std::rotate zu implementieren, der code ist mehr c style as c++...aber egal.
kann man den algo noch verbessern?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void my_rotate(vector<int> &num, int pos) {
	bool rotate_left = false;

	if(pos < 0) {
		rotate_left = true;
	}

	pos = abs(pos);
	pos = pos % num.size();

	if(rotate_left) {
		int index_i = 0;
		int index_j = pos;

		while(index_j < num.size()) {
			swap(num[index_i], num[index_j]);

			index_i++;
			index_j++;
		}		
	}
	else {	
		int last_index = num.size() - 1;
		int index_i = last_index;
		int index_j = last_index - pos;

		while(index_j >= 0) {
			swap(num[index_i], num[index_j]);

			index_i--;
			index_j--;
		}
	}
}

int main() {
	vector<int> vec1 = {1, 1, 4, 7, 10, 13};

	for_each(vec1.begin(), vec1.end(), [](int val){ cout << val << ' ';});
	cout << '\n';

	my_rotate(vec1, -2);

	for_each(vec1.begin(), vec1.end(), [](int val){ cout << val << ' ';});

	return 0;
}

Skym0sh0

Welches Ziel verfolgst du?

Wenn du einfach mal dich zu Übungszwecken an std::rotate versuche willst, ok, das hast du hiermit getan. Wenn du was besseres willst, dann recherchier mehr/besser.

Willst du einen Algorithmus für den Produktiveinsatz, dann nimm std::rotate oder gib stichhaltige Gründe an, was dagegen spricht.

Your Turn...

Deine Funktion ist nicht vergleichbar mit std::rotate .

du übergibst z.B. einen std::vector, welcher <int> hält. Schau dir mal an was da std::rotate macht. Was für Daten dort übergeben werden und wie damit umgegangen wird.

meine frage war, wie man die zeitkomplexitaet des algos verbessert.

ich weiss wohl das rotate iteratoren nimmt...

ist nur ne vorbereitung fuer eine interview...

volkard

Ist Deine Funktion wirklich korrekt?

Ich würde noch in Erwähnung bringen den Zwei-Hände-Trick, den Jon Bentley in Programming Pearls zeigt.

Columbo

volkard schrieb:

Ich würde noch in Erwähnung bringen den Zwei-Hände-Trick, den Jon Bentley in Programming Pearls zeigt.

Warum nicht den Block-Swap Algo?

@volkard: meinst du den hier?

Algorithm:

rotate(arr[], d, n)
  reverse(arr[], 1, d) ;
  reverse(arr[], d + 1, n);
  reverse(arr[], l, n);

Let AB are the two parts of the input array where A = arr[0..d-1] and B = arr[d..n-1]. The idea of the algorithm is:
Reverse A to get ArB. /* Ar is reverse of A */
Reverse B to get ArBr. /* Br is reverse of B */
Reverse all to get (ArBr) r = BA.

For arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2 and n = 7

A = [1, 2] and B = [3, 4, 5, 6, 7]

Reverse A, we get ArB = [2, 1, 3, 4, 5, 6, 7]
Reverse B, we get ArBr = [2, 1, 7, 6, 5, 4, 3]
Reverse all, we get (ArBr)r = [3, 4, 5, 6, 7, 1, 2]

volkard

mike1 schrieb:

@volkard: meinst du den hier?

Ja.