0

Доброго вам времени суток и не судите строго (меньше месяца изучаю C++).

В рекурсивном алгоритме быстрой сортировки столкнулся с проблемой. В цикле do{}while() происходит выход когда переменные r_p и l_p равны. Дело в том, что условие для итерации цикла (l_p<=r_p), тогда как может происходить выход, если r_p==l_p?

Сам код:

#include <iostream>
#include <stdlib.h>

void quick_sort(int mas[],int left,int right);
void swap(int &n1,int &n2);
void printm(int mas[],int n);
using namespace std;

int main()
{
    int mas1[5]={5,4,3,2,1};
    int mas2[5]={5,4,3,2,1};
    cout << "***Quick Sort***\n" << endl;
    cout<<"Before mas1: ";
    printm(mas1,5);
    quick_sort(mas1,0,4);
    cout<<"After mas1: ";
    printm(mas1,5);
    return 0;
}
void quick_sort(int mas[],int left,int right)
{
    int l_p=left;
    int r_p=right;
    int pivot=(l_p+r_p)/2;
    do
    {
        while(mas[r_p]>pivot)
            r_p--;
        //cout<<r_p<<" ";
        while(mas[l_p]<pivot)
            l_p++;
        //cout<<l_p<<" ";
        if(l_p<=r_p)
        {
            cout<<"r_p="<<r_p<<" l_p="<<l_p<<"\n";
            cout<<"OK 1\n";
            swap(mas[l_p],mas[r_p]);
            r_p--;
            l_p++;
            cout<<"r_p="<<r_p<<" l_p="<<l_p<<"\n";
        }
    }while(l_p<=r_p);   //<<-----------"Преждевременный" выход из цикла?
    //cout<<"OK 3 \n";
    if(left<r_p)
        quick_sort(mas,left,r_p);
    if(l_p<right)
        quick_sort(mas,l_p,right);
}
void swap(int &n1,int &n2)
{
    cout<<"OK 2\n";
    int temp=n1;
    n1=n2;
    n2=temp;
}
void printm(int mas[],int n)
{
    if(n<0)
    {
        cout<<"\nError! n must be >= 0.\n";
        exit(1);
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            cout<<mas[i]<<", ";
        }
        cout<<"\n";
    }
}
6
  • 2
    почему именно "Преждевременный" выход из цикла? по-моему полностью запланированое условие продолжение выполнения цикла. А выход будет произведён когда l_p будет больше r_p
    – Spectre
    29 янв 2012 в 17:48
  • Выходит когда l_p==r_p :(
    – hal9000
    29 янв 2012 в 17:57
  • вы это выяснили когда прошли дебагером полностью по функции?
    – Spectre
    29 янв 2012 в 18:01
  • @Spectre Не я не знаю как >"пройтись дебагером полностью по функции". Я просто смотрю на вывод значений переменных в консоли и последнее, что программа выводит прежде чем впасть в бесконечный цикл это: >r_p=2 l_p=2
    – hal9000
    29 янв 2012 в 18:06
  • У вас еще много ошибок, например внутренние циклы должны выглядеть как-то так: while(mas[r_p] > pivot_value && r_p >l_p) --r_p; Сейчас же на некоторых входных данных индексы могут выйти за пределы массива.
    – gkuznets
    29 янв 2012 в 18:30

3 ответа 3

1

У вас вообще ерунда какая-то, вы сравниваете 'индекс' в массиве (pivot) со значениями:

mas[r_p]>pivot
2
  • @gkuznets Спасибо вы указали на самую важную причину всех моих неприятностей.
    – hal9000
    29 янв 2012 в 18:26
  • @gkuznets, согласен, какой-то эзотерический QuickSort
    – Spectre
    29 янв 2012 в 18:30
1

Это был сарказм? Если нет, то перед выводом присутствует вот этот код:

    while(mas[r_p]>pivot)
        r_p--;
    //cout<<r_p<<" ";
    while(mas[l_p]<pivot)
        l_p++;
    //cout<<l_p<<" ";

который с лёгкостью может изменить значения переменных, которые участвуют в следующем условии:

 if(l_p<=r_p)

которое предшествует выводу в консоль

1
  • @Spectre Спасибо за вашу помощь. Я должен подумать.
    – hal9000
    29 янв 2012 в 18:20
0

Ну у вас же условие, что l_p должен быть меньше или равен r_p. Попробуйте цикл с предусловием.

2
  • Выходит когда l_p==r_p :(
    – hal9000
    29 янв 2012 в 17:58
  • А если строго меньше? 29 янв 2012 в 18:08

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.