C++ ⎼ Две аналогичные функции, но очень разные.

Я пишу программу быстрой сортировки. Для этого мне нужно разбить массив. Разделение выполняется с помощью функции paritionIt(). Я написал код разбиения массива, который выглядит следующим образом:C++ ⎼ Две аналогичные функции, но очень разные.

int partition(int beg,int end,double key) 
{ 
    int pLeft = beg; 
    int pRight = end-1; 
    while(pLeft<pRight) 
    { 
     while(array[++pLeft]<key); 
     while(array[--pRight]>key); 
     if(pLeft<pRight) 
      swap(pLeft,pRight); 
    } 
    swap(pLeft,end-1); 
    return pLeft; 
}

Этот блок, кажется, работает, работает хорошо, когда выполняется в изоляции. Однако, когда он работал вместе с другими функциями, он, похоже, порождает неправильный ответ. Следующий код, предоставленный мне, устраняет все проблемы, но он не сильно отличается от моего кода.

int partitionIt(int left, int right, double pivot) 
{ 
    int leftMark = left; //right of first elem 
    int rightMark = right - 1; //left of pivot 
    while(true) 
    { 
     while(theVect[++leftMark] < pivot) //find bigger 
     ; // (nop) 
     while(theVect[--rightMark] > pivot) //find smaller 
     ; // (nop) 
     if(leftMark >= rightMark) //if pointers cross, 
      break; // partition done 
     else //not crossed, so 
      swap(leftMark, rightMark); //swap elements 
    } //end while(true) 
    swap(leftMark, right-1); //restore pivot 
    return leftMark; //return pivot location 
} //end partitionIt()

Блок, похоже, похож на мой, но дает правильный ответ, в то время как мой не является. Не могли бы вы рассказать, какая разница между partition() и partitionIt().

источник

2013-07-30 kusur

Итак, если вы замените свой код (первый блок) на второй блок, все ваши функции будут работать должным образом? – Kevin

Я не вижу никакой функциональной разницы между этими двумя частями кода. –

Да ... на самом деле, весь мой код соответствует коду, указанному в книге (за исключением имен переменных). – kusur

Разница заключается в том, что вы выходите из своей петлевой структуры.

В вашем коде вы делаете две условные проверки, тогда как в данном коде вы делаете только один.

Предположим, вы какое-то время повторяли цикл. (Каламбур не предназначен).

Вы ударите этот код:

if(pLeft<pRight) 
       swap(pLeft,pRight);

Тогда вы попали в нижнюю части цикла в то время, вернуться к началу, а затем снова проверьте, если pLeft<pRight. Если это не так, мы выходим из цикла.

В данном коде, вы выполняете своп, а затем выполнить следующие действия:

while(theVect[++leftMark] < pivot) //find bigger 
    ; // (nop) 
    while(theVect[--rightMark] > pivot) //find smaller 
    ; // (nop)

Вы затем чек, чтобы увидеть, если вы вырваться из петли.

Кажется, что в этом разница.

Редактировать: уточнить - что произойдет, если while(pLeft>=pRight) при первом входе в цикл?

В данном коде вы продолжаете цикл while до тех пор, пока он не сломается, но в коде вы никогда не войдете в тело цикла.

источник

2013-07-30 14:31:14 Kevin

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

@kusur Проверьте изменение - разница заключается в том, где вы выполняете свою условную проверку и выходите из цикла. – Kevin

В любом цикле мы переходим к началу цикла и проверяем условие. В данном коде всегда происходит оценка true. В вашем коде это не так. – Kevin

Единственное, что я вижу сразу, что функции будут вести себя по-другому, если вызывается с left + 1 == right: ваша функция не будет входить в цикл, но вернется beg; функция из книги будет войти в цикл, таким образом, увеличивая leftMark и декремента rightMark, прежде чем делать окончательный обмен и возврат leftMark.

источник

2013-07-30 14:36:40

C++ ⎼ Две аналогичные функции, но очень разные.

ответ

Смежные вопросы