пузырьковая сортировка с помощью xor или temp

Question

пузырьковая сортировка с помощью xor или temp

в сценарии сортировки массива с использованием алгоритма пузырьковой сортировки, который более эффективен при создании временной переменной внутри вложенного цикла или с помощью оператора xor:

#include <iostream>

int main()
{
int array[5] = {7, 2, 5, 3, 4};

/*1: using temporary variable

for(int i(0); i < 5; i++)
{
for(int j(i + 1); j < 5; j++)
{
if(array[i] > array[j])
{
int tmp  = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
*/

//2: using xor ^ swapper
for(int i = 0; i < 5; i++)
{
for(int j(i + 1); j < 5; j++)
{
if(array[i] > array[j])
{
array[i] ^= array[j];
array[j] ^= array[i];
array[i] ^= array[j];
}
}
}for( i = 0; i < 5; i++)
std::cout << array[i] << ", ";

std::cout << std::endl;
return 0;
}

Я только хочу знать, какой из них быстрее и эффективнее, зная, что оба метода работают нормально.

1

bubble-sort c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Как уже отмечали другие, единственный способ узнать наверняка — это измерить его.

«как измерить это?» был бы предметом совершенно другого вопроса, если бы такой вопрос был по теме на stackoverflow. Но это не так.

Google твой друг. Погугли это. Ищите такие ключевые слова, как «тест» или «профиль» вместе с «C ++» и, возможно, название используемой IDE.

Кроме того, я могу дать вам довольно хорошее представление о том, какой из них будет быстрее, просто изучив инструкции.

Последовательность команд

  a ^= b;
b ^= a;
a ^= b;

переводит в следующие неоптимизированные инструкции:

  load  register from a            ;memory reference
xor   register with b            ;memory reference
store register to a              ;memory reference
load  register from b            ;memory reference
xor   register with a            ;memory reference
store register to b              ;memory reference
load  register from a            ;memory reference
xor   register with b            ;memory reference
store register to a              ;memory reference

которые могут быть оптимизированы следующим образом:

  load  register1 from a           ;memory reference
load  register2 from b           ;memory reference
xor register1 with register2
xor register2 with register1
xor register1 with register2
store register1 to a             ;memory reference
store register2 to b             ;memory reference

Последовательность команд

  int tmp  = a;
a = b;
b = tmp;

переводит в следующие неоптимизированные инструкции:

  load  register from a            ;memory reference
store register to tmp            ;memory reference
load  register from b            ;memory reference
store register to a              ;memory reference
load  register from tmp          ;memory reference
store register to b              ;memory reference

которые могут быть оптимизированы следующим образом:

  load register1 from a            ;memory reference
load register2 from b            ;memory reference
store register1 to b             ;memory reference
store register2 to a             ;memory reference

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

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

1