Доброго вам времени суток и не судите строго (меньше месяца изучаю 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";
}
}
l_p
будет большеr_p