A “premature” exit from the do {} while () loop in a quick sorting of an array?

Question

Good day to you and do not judge strictly (less than a month learning C ++).

A recursive quick sort algorithm encountered a problem. In the do{}while() , the output occurs when the r_p and l_p are equal. The fact is that the condition for iterating the loop (l_p<=r_p) , then how can the output occur if r_p==l_p ?

The code itself:

 #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"; } }

In my opinion, the fully planned condition for the continuation of the loop
Did you find out when the debager went completely in function?
@Spectre No, I don’t know how> "walk through the debugger completely in function."
I just look at the output of the values of the variables in the console and the last thing that the program displays before falling into an infinite loop is:> r_p = 2 l_p = 2
You still have a lot of mistakes, for example, inner loops should look something like this: while (mas [r_p]> pivot_value && r_p> l_p) - r_p;

gkuznets gkuznets 1,204 6 ten · Accepted Answer · 2012-01-29T18:18:25

You have some kind of nonsense, you compare the 'index' in the array (pivot) with the values:

 mas[r_p]>pivot

@gkuznets Thank you for pointing out the most important reason for all my troubles.

Answer 2 · 2012-01-29T18:11:36

That was sarcasm? If not, then this code is present before output:

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

which can easily change the values of variables that are involved in the following condition:

  if(l_p<=r_p)

which precedes the console output

Hilarion hilarion eleven 2 · Answer 3 · 2012-01-29T17:53:48

Well, you have the same condition that l_p must be less than or equal to r_p. Try a precondition loop.

A “premature” exit from the do {} while () loop in a quick sorting of an array?

3 answers 3

More articles: