Нерекурсивный QuickSort
Нашел на вашем форуме Функцию (нерекурсивную) быстрой сортировки. Просьба пояснить код программы поэтапно. Особенно хотелось бы пояснения к помеченному элементу кода.
Помеченный элемент кода:
if(i<right)
{
s++;
stack.left=i;
stack.right=right;
}
Код:
#include <cmath>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <windows.h>
#include <mmsystem.h>
#include <fstream>
#pragma comment(lib,"winmm.lib")
using namespace std;
const int N=10;
int main()
{
const int M=30;
int i=0,j=0,left,right,s,x,w;
int elements=N,a[N];
struct{int left,right;} stack[M];
s=0;
stack[0].left=0;
stack[0].right=elements-1;
for (j=0;j<N;j++){
a[j]=-50+rand()%101;
cout<<a[j]<<" ";
}
cout<<endl;
do
{
left=stack.left;
right=stack.right;
s--;
do
{
i=left; j=right;
x=a[(left+right)/2];
do
{
while(a<x) i++;
while (x<a[j]) j--;
if (i<=j)
{
w=a; a=a[j]; a[j]=w;
i++; j--;
}
}
while(i<j);
if(i<right)
{
s++;
stack.left=i;
stack.right=right;
}
right=j;
}
while(left<right);
}
while (s>-1);
for (i=0;i<N;i++)
cout<<a<<" ";
return 0;
}
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <windows.h>
#include <mmsystem.h>
#include <fstream>
#pragma comment(lib,"winmm.lib")
using namespace std;
const int N=10;
int main()
{
const int M=30;
int i=0,j=0,left,right,s,x,w;
int elements=N,a[N];
struct{int left,right;} stack[M];
s=0;
stack[0].left=0;
stack[0].right=elements-1;
for (j=0;j<N;j++){
a[j]=-50+rand()%101;
cout<<a[j]<<" ";
}
cout<<endl;
do
{
left=stack.left;
right=stack.right;
s--;
do
{
i=left; j=right;
x=a[(left+right)/2];
do
{
while(a<x) i++;
while (x<a[j]) j--;
if (i<=j)
{
w=a; a=a[j]; a[j]=w;
i++; j--;
}
}
while(i<j);
if(i<right)
{
s++;
stack.left=i;
stack.right=right;
}
right=j;
}
while(left<right);
}
while (s>-1);
for (i=0;i<N;i++)
cout<<a<<" ";
return 0;
}
Помеченный элемент кода:
if(i<right)
{
s++;
stack
stack
}
В рекурсивном варианте хранилищем промежуточных данных служит стек, в данном нерекурсивном варианте для него выбрали массив структур stack. В помеченном куске (а почему весь код не оформлен как положено?) выполняется "добавление" структуры к массиву stack и сохранение промежуточных данных в ней.
Цитата: Phodopus
В рекурсивном варианте хранилищем промежуточных данных служит стек, в данном нерекурсивном варианте для него выбрали массив структур stack. В помеченном куске (а почему весь код не оформлен как положено?) выполняется "добавление" структуры к массиву stack и сохранение промежуточных данных в ней.
1. А как положено оформлять (на будущее, чтобы знать) ? Так нормально?
2. Про саму структуру stack я понял, меня интересует, почему в том месте для stack.left берется значение i (почему не left), а stack.right=right (почему не j) ?