Блог

Главная - Вопросы по программированию - Невозможно использовать swap без временной переменной

Невозможно использовать swap без временной переменной

#c #quicksort

#c #быстрая сортировка

Вопрос:

Программа быстрой сортировки

 #include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;

// constant
enum {MAX = 10};

// class
class A
{
private:
    int arr[MAX];
public:
    A() // constructor
    {
        srand(time(0));
        for(int i = 0; i < MAX; i  )
            arr[i] = rand() % 100;
    }
    // accessing array
    int get(int i)
    {
       return arr[i];
    }
    // quick sort
    int Partition(int left, int right);
    void quickSort(int left, int right);
    void Swap(intamp;, intamp;);
};

// member function definition
int A::Partition(int left, int right)
{
    int pivot = arr[right], i = left - 1;
    for(int j = left; j <= right-1; j  )
    {
        if(arr[j] < pivot)
        {
            i  ;
            Swap(arr[i], arr[j]);
        }
    }
    Swap(arr[i 1], arr[right]);
    return i 1;
}

void A::quickSort(int left, int right)
{
    if(left < right)
    {
        int pi = Partition(left, right);
        quickSort(left, pi-1);
        quickSort(pi 1, right);
    }
}

void A::Swap(intamp; a, intamp; b)
{
    a = a b;
    b = a-b;
    a = a-b;
}

// driver
int main(void)
{
    A obj1;

    //-------Array initialized--------
    cout << "Before sorting:" << endl;
    for(int i = 0; i < MAX; i  )
        cout << setw(4) << obj1.get(i);

    //--------Sorting Array-----------
    obj1.quickSort(0, MAX-1);

    //--------Sorted Array------------
    cout << "nAfter sorting:" << endl;
    for(int i = 0; i < MAX; i  )
        cout << setw(4) << obj1.get(i);

    return 0;
}

Проблема внутри функции swap() . Когда я меняю местами значения, используя переменную int temp, значения меняются местами, а массив сортируется в порядке возрастания.

Но когда я меняю местами значения без использования временной переменной int, я получаю 0 в отсортированном массиве. Как показано ниже:

Вывод

 Before sorting:
   89   43   18   98   23   88   52   18   1   25
After sorting:
   1   18   0   0   25   43   0   88   89   98

Комментарии:

1. Я подозреваю, что проблема не в swap, а в неопределенном поведении где-то еще в коде. Это просто проявляется на основе той или иной реализации.

2. Замена с помощью арифметики не была эффективным методом с тех пор, как джинсы-клеш вышли из моды в первый раз.

3. Все эти 1 настройки и - 1 корректировки делают маловероятным, что у вас где-то нет случайной ошибки. Обычные полуоткрытые интервалы являются обычными по уважительным причинам, одна из которых заключается в том, насколько приятнее становится разделять интервалы. (Также: тестирование со случайными числами — плохая идея, если вы не используете начальное значение повторно. Тестовые примеры должны быть небольшими и систематическими, а не большими и произвольными.)

4. Просто используйте std::swap .

Ответ №1:

Ошибка не из-за swap, она возникает из-за вызывающей функции, которая отправила ту же переменную для обмена. Это приводит к тому, что арифметика выдает ноль для a-b .

В следующем коде:

 int A::Partition(int left, int right)
{
    int pivot = arr[right], i = left - 1;
    for(int j = left; j <= right-1; j  )
    {
        if(arr[j] < pivot)
        {
            i  ;
            Swap(arr[i], arr[j]); // i = j in the first run
    }
}
   Swap(arr[i 1], arr[right]); // here also exists case that i 1 = right
   return i 1;
}

Для теста: используя условие if для фильтрации сталкивающихся индексов, это работает:

  if (i != j)Swap(arr[i], arr[j]);

и

  if ((i 1) != right) Swap(arr[i 1], arr[right]);