воскресенье, 18 июля 2010 г.

Quick sort

Сегодня разминки ради скрипел мозгами над quick sort.

Накнопал вот такой прекрасный код:
#include <iostream>
#include <stack>

using namespace std;

void showM(int M[], int l, int r)
{
 for(int i = l; i <= r; i++) cout << M[i] << " ";
 cout << endl;
}

int main ()
{

 const int size = 8;
 int M[size] = {1,5,2,4,5,3,2,0};

 stack<int> st;

 int ret_flag = 0; int t;

 int s = 0, e = size-1;

 showM(M, 0, size-1);

func:
 int l = s, r = e;
 
 int G = M[l];

m3:
 while (M[l]<G) l++;
 while (M[r]>G) r--;

 if (l>r) goto m4;
 t=M[l]; M[l]=M[r];M[r]=t;
 l++;r--;
 goto m3;
m4:
 if(l<=r) goto m5;
 if(M[r]<=M[l]) goto m5;
 t=M[l]; M[l]=M[r]; M[r]=t;
m5:

 if(l-s <= 1) goto m1;
 st.push(s); st.push(e); st.push(l); st.push(ret_flag);
 ret_flag = 2;
 e = l-1;
 goto func;
ret2:
 ret_flag=st.top();st.pop();l=st.top();st.pop();e=st.top();st.pop();s=st.top();st.pop();

m1:
 if(e-l < 1) goto m2;

 st.push(s); st.push(e); st.push(l); st.push(ret_flag);
 ret_flag = 1;
 s = l;
 goto func;
ret1:
 ret_flag=st.top();st.pop();l=st.top();st.pop();e=st.top();st.pop();s=st.top();st.pop();
m2:

 if(ret_flag==1) goto ret1;
 if(ret_flag==2) goto ret2;

 showM(M, 0, size-1);

 return 0;
}

Поразительно, как раньше люди писали программы, когда языки не поддерживали красивую структурную вложенность? Я сломал себе половину мозга, пока реализовал это несложный алгоритм.
Отдельной проблемой было представить как правильно реализовать рекурсию без такой структуры, как "функция". Пришлось писать "болванку" с переходами для того, чтобы представить себе как рекурсивная функция должна вызываться из двух мест собственного тела.
Естественно, столкнулся с проблемой "кочующей переменной", когда значение переменной приходит из другой части кода, а не должно (забыл положить в стек L).
Опять-таки непонятно как вообще можно написать что-то существенное на языке, который не поддерживает действительноДлинныеИменаПеременных.
Вы спросите, для чего же было терпеть все эти мучения и ужас? Дело в том, что мне нужно реализовать это на ассемблере. Думаю, что такой код теперь не сложно будет перевести.

Комментариев нет:

Отправить комментарий