API tools faq
paste
knightL

sorts.c

knightL
Mar 11th, 2011
286
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 31.68 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <gtk/gtk.h>
  5. #include "sorts.h"
  6.  
  7. GtkWidget *window;
  8. // буффер, в котором будет хранится уже нарисованная легенда
  9. GdkPixmap *legend;
  10. // настройки цветов для рисования фона и переднего плана
  11. GdkGC *gcbg[STATECNT],*gcfg[STATECNT];
  12. // очередь, в которую будут добавляться действия, которые будет необходимо визуализировать; заполняется по мере обычной сортировки массива
  13. GSList *actionqueue=NULL;
  14. // массивы элементов и чисел, которые будут упорядочиваться
  15. element el[N];
  16. int arrv[N];
  17.  
  18. // в зависимости от того, какую сортировку будет визуализировать нам необходимо выводить описания фаз
  19. #if HEAPSORTA || HEAPSORTB
  20. char phasetxt[4][100]={"Построение кучи","Исключение наибольшего элемента","Восстановление кучи","Сортировка окончена"};
  21. #else
  22. char phasetxt[4][100]={"Сортировка","","","Сортировка окончена"};
  23. #endif
  24. // какие типы элементов будут показываться в легенде
  25. #if HEAPSORTA
  26. gboolean legendshow[STATECNT]={TRUE,TRUE,TRUE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE};
  27. #elif HEAPSORTB
  28. gboolean legendshow[STATECNT]={TRUE,TRUE,FALSE,TRUE,TRUE,TRUE,FALSE,FALSE,FALSE};
  29. #elif SHELLSORT
  30. gboolean legendshow[STATECNT]={TRUE,FALSE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,FALSE};
  31. #elif BUBBLESORT
  32. gboolean legendshow[STATECNT]={TRUE,TRUE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,FALSE};
  33. #else
  34. gboolean legendshow[STATECNT]={TRUE,FALSE,FALSE,TRUE,TRUE,FALSE,FALSE,FALSE,TRUE};
  35. #endif
  36.  
  37. // высота легенды с учётом заголовка и описания элементов
  38. int legendheight;
  39. // описание состояний в легенде
  40. char legendtext[STATECNT][100]={"Обычный","На своём месте","В куче","Обрабатывается","Перемещается","Перемещается на своё место","","","Текущий интервал"};
  41. // номер текущей фазы
  42. int phase;
  43. // сколько элементов ещё нужно переместить
  44. int finished;
  45. // координаты левого верхнего угла легенды
  46. int legx,legy;
  47.  
  48. int main(int argc,char * argv[])
  49. {
  50.     int i;
  51.     int maxh;
  52.  
  53.     gtk_init(&argc,&argv);
  54.     // создаём окно и задаём его размер
  55.     window=gtk_window_new(GTK_WINDOW_TOPLEVEL);
  56.     gtk_widget_set_size_request(window,WIDTH,HEIGHT);
  57.  
  58.     srand(time(0));
  59.     // считаем высоту дерева
  60.     for(maxh=0;(1<<maxh)<=N;maxh++);
  61.     // генерируем массив элементов
  62.     for(i=0;i<N;i++)
  63.     {
  64.         el[i].linecoord=getlinecoord(i);
  65.         el[i].treecoord=gettreecoord(i,maxh);
  66.         arrv[i]=el[i].value=rand()%MOD;
  67.         el[i].state=normal;
  68.     }
  69.  
  70.     gtk_widget_show(window);
  71.  
  72.     // подготавливаем программу к визуализации
  73.     init_gc();
  74.     init_sort();
  75.     init_legend();
  76.     g_signal_connect(G_OBJECT(window),"delete-event",G_CALLBACK(delete_event),NULL);
  77.     g_signal_connect(G_OBJECT(window),"expose-event",G_CALLBACK(expose_event),NULL);
  78.  
  79.     // прорисовываем содержимое окна
  80.     expose_event(window,NULL,NULL);
  81.  
  82.     // запускаем бесконечный цикл
  83.     gtk_main();
  84.     return 0;
  85. }
  86.  
  87.  
  88. void init_gc() // создаём цвета, которыми мы будем рисовать элементы в различных состояниях
  89. {
  90.     GdkColor c;
  91.     gcbg[normal]=gdk_gc_new(window->window);
  92.     gcfg[normal]=gdk_gc_new(window->window);
  93.     gcbg[active]=gdk_gc_new(window->window);
  94.     gcfg[active]=gdk_gc_new(window->window);
  95.     gcbg[inplace]=gdk_gc_new(window->window);
  96.     gcfg[inplace]=gdk_gc_new(window->window);
  97.     gcbg[activeinheap]=gcbg[active];
  98.     gcfg[activeinheap]=gcfg[active];
  99.     gcbg[inheap]=gdk_gc_new(window->window);
  100.     gcfg[inheap]=gdk_gc_new(window->window);
  101.     gcbg[activeinplace]=gdk_gc_new(window->window);
  102.     gcfg[activeinplace]=gdk_gc_new(window->window);
  103.     gcbg[inheap]=gdk_gc_new(window->window);
  104.     gcfg[inheap]=gdk_gc_new(window->window);
  105.     gcbg[activeinplace]=gdk_gc_new(window->window);
  106.     gcfg[activeinplace]=gdk_gc_new(window->window);
  107.     gcbg[processed]=gdk_gc_new(window->window);
  108.     gcfg[processed]=gdk_gc_new(window->window);
  109.     gcbg[activeproc]=gcbg[active];
  110.     gcfg[activeproc]=gcfg[active];
  111.     gcbg[activeinterval]=gcbg[inplace];
  112.     gcfg[activeinterval]=gcfg[inplace];
  113.    
  114.     c.red=255*257;
  115.     c.green=250*257;
  116.     c.blue=173*257;
  117.     gdk_gc_set_rgb_fg_color(gcbg[normal],&c);
  118.    
  119.     c.red=97*257;
  120.     c.green=78*257;
  121.     c.blue=0*257;
  122.     gdk_gc_set_rgb_fg_color(gcfg[normal],&c);
  123.    
  124.     c.red=255*257;
  125.     c.green=255*257;
  126.     c.blue=255*257;
  127.     gdk_gc_set_rgb_fg_color(gcbg[active],&c);  
  128.    
  129.     c.red=118*257;
  130.     c.green=0*257;
  131.     c.blue=0*257;  
  132.     gdk_gc_set_rgb_fg_color(gcfg[active],&c);
  133.        
  134.     c.red=205*257;
  135.     c.green=188*257;
  136.     c.blue=0*257;  
  137.     gdk_gc_set_rgb_fg_color(gcbg[inplace],&c);
  138.    
  139.     c.red=0*257;
  140.     c.green=0*257;
  141.     c.blue=0*257;  
  142.     gdk_gc_set_rgb_fg_color(gcfg[inplace],&c);
  143.    
  144.     c.red=246*255;
  145.     c.green=197*255;
  146.     c.blue=0*255;
  147.     gdk_gc_set_rgb_fg_color(gcbg[inheap],&c);
  148.    
  149.     c.red=97*257;
  150.     c.green=78*257;
  151.     c.blue=0*257;
  152.     gdk_gc_set_rgb_fg_color(gcfg[inheap],&c);
  153.  
  154.     c.red=255*257;
  155.     c.green=255*257;
  156.     c.blue=255*257;
  157.     gdk_gc_set_rgb_fg_color(gcbg[activeinplace],&c);   
  158.    
  159.     c.red=97*257;
  160.     c.green=78*257;
  161.     c.blue=0*257;
  162.     gdk_gc_set_rgb_fg_color(gcfg[activeinplace],&c);
  163.    
  164.     c.red=169*257;
  165.     c.green=255*257;
  166.     c.blue=142*257;
  167.     gdk_gc_set_rgb_fg_color(gcbg[processed],&c);   
  168.    
  169.     c.red=0*257;
  170.     c.green=0*257;
  171.     c.blue=0*257;
  172.     gdk_gc_set_rgb_fg_color(gcfg[processed],&c);
  173.    
  174. }
  175.  
  176. void init_sort() // подготавливаем визуализатор к работе
  177. {
  178.     // устанавливаем в качестве текущей фазы нулевую
  179.     phase=0;
  180.     // говорим, что все элементы перемещены
  181.     finished=0;
  182.     // сортируем массив arrv, чтобы заполнить очередь событий задержками, обменами и т.д.
  183.     sort(arrv);
  184.     // визуализируем очередь
  185.     g_timeout_add(SORTDELAY,(GSourceFunc) visualize,NULL);
  186. }
  187.  
  188. // создаёт легенду в буфере GdkPixmap* legend, инициализируем положение легенды
  189. // и рассчитываем высоту легенды
  190. void init_legend()
  191. {
  192.     int i;
  193.     int legendshowcnt;
  194.     element e;
  195.     legx=-1;
  196.     legy=-1;
  197.     legendshowcnt=0;
  198.     for(i=0;i<STATECNT;i++)
  199.         if(legendshow[i]) legendshowcnt++;
  200.     legendheight=LEGENDINNEROFFSETY+2*RAD*legendshowcnt+GAP*(legendshowcnt-1)+LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
  201.     legend=gdk_pixmap_new(window->window,LEGENDWIDTH+2,legendheight+2,-1);
  202.     gdk_draw_rectangle(legend,window->style->bg_gc[GTK_WIDGET_STATE(window)],TRUE,0,0,LEGENDWIDTH+2,legendheight+2);
  203.  
  204.     draw_text_in_center(LEGENDHEADER,window,legend,window->style->black_gc,LEGENDWIDTH/2,LEGENDHEADERHEIGHT/2);
  205.     gdk_draw_rectangle(legend,window->style->white_gc,FALSE,1,LEGENDHEADERHEIGHT,LEGENDWIDTH-1,legendheight-LEGENDHEADERHEIGHT-1);
  206.     gdk_draw_rectangle(legend,window->style->black_gc,FALSE,2,LEGENDHEADERHEIGHT+1,LEGENDWIDTH-1,legendheight-LEGENDHEADERHEIGHT-1);
  207.     e.linecoord.x=LEGENDINNEROFFSETX;
  208.     e.linecoord.y=LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
  209.     e.treecoord.x=LEGENDINNEROFFSETX+2*RAD+5;
  210.     e.treecoord.y=LEGENDINNEROFFSETY+LEGENDHEADERHEIGHT;
  211.     e.value=00;
  212.  
  213.     for(i=0;i<STATECNT;i++)
  214.     {
  215.         if(!legendshow[i]) continue;
  216.         e.state=i;
  217.         draw_element(window,legend,&e);
  218.         draw_text_in_center_y(legendtext[i],window,legend,window->style->black_gc,e.linecoord.x+4*RAD+2*GAP+LEGENDINNEROFFSETX,e.linecoord.y+RAD);
  219.         e.linecoord.y+=2*RAD+GAP;
  220.         e.treecoord.y+=2*RAD+GAP;
  221.     }
  222. }
  223.  
  224. // визуализируем очередь actionqueue, последовательно доставая элементы из неё и обробатывая их
  225. gboolean visualize(gpointer data)
  226. {
  227.     action cur;
  228.     while(actionqueue) // пока очередь действий не пустая
  229.     {
  230.         cur=*((action*) actionqueue->data); //получаем действие из головы очереди
  231.         free(actionqueue->data); // освобождаем память выделенную под действие
  232.         actionqueue=g_slist_remove(actionqueue,actionqueue->data); //удаляем первый элемент списка
  233.         switch(cur.type)
  234.         {
  235.         case acsleep:
  236.             //если текущее действие - ждать, то мы добавляем ожидание и прекращаем выполнение этой функции
  237.             g_timeout_add(cur.param.time,(GSourceFunc) visualize,actionqueue);
  238.             return FALSE;
  239.         case acswap:
  240.             //если текущее действие - обмен, мы активируем функцию обмена двух элементов и прекращаем выполнение этой функции
  241.             swapvis(cur.param.swap.id1,cur.param.swap.id2);
  242.             return FALSE;
  243.         case acchangestate:
  244.             //если текущее действие - смена статуса, мы меняем его и перерисовываем элемент
  245.             el[cur.param.chgst.id].state=cur.param.chgst.state;
  246.             draw_element(window,window->window,&(el[cur.param.chgst.id]));
  247.             break;
  248.         case acchangephase:
  249.             //если текущее действие - смена фазы, мы меняем номер текущей фазы и отображаем новый текст
  250.             phase=cur.param.phase;
  251.             displayphasetxt();
  252.             break;
  253.         }
  254.     }
  255.     return FALSE;
  256. }
  257.  
  258. gboolean expose_event(GtkWidget *w, GdkEvent *e, gpointer data) // если необходима перересовка, то перерисуем всё
  259. {
  260.     int i;
  261.     displayphasetxt();
  262.     draw_legend();
  263.     for(i=0;i<N;i++)
  264.     {
  265.         draw_element(w,w->window,&el[i]);
  266.     }
  267.     return TRUE;
  268. }
  269.  
  270. // получаем координаты вершины в дереве
  271. GdkPoint gettreecoord(int n,int maxh)
  272. {
  273.     GdkPoint res;
  274.     int h;
  275.     // определяем слой, в котором находится вершина
  276.     for(h=0;(1<<h)<=n+1;h++);
  277.     // высчитываем по формуле координаты вершины
  278.     res.x=TREEOFFSETX+((1<<(maxh-h))-1)*(2*RAD+GAP)/2.0+( (1<<(maxh-h))*GAP+((1<<(maxh-h)))*2*RAD)*(n-(1<<(h-1))+1);
  279.     res.y=TREEOFFSETY+(h-1)*(2*RAD+GAP);
  280.     return res;
  281. }
  282.  
  283. // получаем координаты вершины в массиве
  284. GdkPoint getlinecoord(int n)
  285. {
  286.     GdkPoint res;
  287.     res.x=LINEOFFSETX+(2*RAD+GAP)*n;
  288.     res.y=LINEOFFSETY;
  289.     return res;
  290. }
  291.  
  292. // отрисовка элемента e в d, используя w для получения PangoContext в draw_text_in_center
  293. void draw_element(GtkWidget *w,GdkDrawable *d, element *e)
  294. {
  295.     // печатаем число в массив s
  296.     char s[10];
  297.     sprintf(s,"%.2d",e->value);
  298.    
  299.     // рисуем элемент массива в виде прямоугольник с рамкой и текстом s
  300.     gdk_draw_rectangle(d,gcbg[e->state],TRUE,e->linecoord.x,e->linecoord.y,2*RAD,2*RAD);
  301.     gdk_draw_rectangle(d,gcfg[e->state],FALSE,e->linecoord.x,e->linecoord.y,2*RAD,2*RAD);
  302.     draw_text_in_center(s,w,d,gcfg[e->state],e->linecoord.x+RAD,e->linecoord.y+RAD);
  303. #if HEAPSORTA || HEAPSORTB
  304.     // если происходит отрисовка дерева, то мы рисуем элемент дерева в виде окружности с рамкой и текстом s
  305.     gdk_draw_arc(d,gcbg[e->state],TRUE,e->treecoord.x,e->treecoord.y,2*RAD,2*RAD,0,64*360);
  306.     gdk_draw_arc(d,gcfg[e->state],FALSE,e->treecoord.x,e->treecoord.y,2*RAD,2*RAD,0,64*360);
  307.     draw_text_in_center(s,w,d,gcfg[e->state],e->treecoord.x+RAD,e->treecoord.y+RAD);
  308. #endif
  309. }
  310.  
  311. // рисуем текст text в d при помощи графического контекста gc с центром в (xc,yc) используя w для получения PangoContext
  312. void draw_text_in_center(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint xc, gint yc)
  313. {
  314.     PangoContext *context=gtk_widget_create_pango_context(w);
  315.     PangoLayout *layout= pango_layout_new(context);
  316.     gint width,height;
  317.     pango_layout_set_text(layout,text,-1);
  318.     pango_layout_get_pixel_size(layout,&width,&height);
  319.     gdk_draw_layout (d,gc,xc-width/2,yc-height/2,layout);
  320.     g_object_unref(context); g_object_unref(layout);
  321. }
  322.  
  323. // рисуем текст text в d при помощи графического контекста gc с центром по y в yc и координатой по x x
  324. // используя w для получения PangoContext
  325. void draw_text_in_center_y(gchar * text, GtkWidget *w, GdkDrawable *d, GdkGC *gc, gint x, gint yc)
  326. {
  327.     PangoContext *context=gtk_widget_create_pango_context(w);
  328.     PangoLayout *layout= pango_layout_new(context);
  329.     gint width,height;
  330.     pango_layout_set_text(layout,text,-1);
  331.     pango_layout_get_pixel_size(layout,&width,&height);
  332.     gdk_draw_layout (d,gc,x,yc-height/2,layout);
  333.     g_object_unref(context); g_object_unref(layout);
  334. }
  335.  
  336.  
  337. // отрисовать легенду
  338. void draw_legend()
  339. {
  340.     // если легенда уже была нарисована, то очищаем её предыдущее местонахождение
  341.     if(legx>0&&legy>0)
  342.         gdk_window_clear_area(window->window,legx,legy,legx+LEGENDWIDTH,legy+legendheight);
  343.     // устанавливаем новое положение легенды
  344.     legx=window->allocation.width-LEGENDOFFSETX-LEGENDWIDTH;
  345.     legy=LEGENDY;
  346.     // отрисовываем легенду из GdkPixmap *legend по новым координатам
  347.     gdk_draw_drawable(window->window,window->style->fg_gc[GTK_WIDGET_STATE(window)],legend,0,0,legx,legy,-1,-1);
  348. }
  349.  
  350. // отрисовываем описание фазы
  351. void displayphasetxt()
  352. {
  353.     // очищаем верхнюю часть окна
  354.     gdk_window_clear_area(window->window,0,0,window->allocation.width,2*CENTERTEXTOFFSETY+2);
  355.     // рисуем описание фазы с тенью
  356.     draw_text_in_center(phasetxt[phase],window,window->window,window->style->white_gc,window->allocation.width/2+SHADOWOFFSET,CENTERTEXTOFFSETY+SHADOWOFFSET);
  357.     draw_text_in_center(phasetxt[phase],window,window->window,window->style->black_gc,window->allocation.width/2,CENTERTEXTOFFSETY);
  358.     // пишем CENTERTEXTHEADER в той же строке, что и описание фазы, но только слева, а не по центру
  359.     draw_text_in_center_y(CENTERTEXTHEADER,window,window->window,window->style->black_gc,10,CENTERTEXTOFFSETY);
  360. }
  361.  
  362. // начинаем перемещение элементов по путям p1 и p2 ( в каждом пути также хранится номер элемента, который перемещается)
  363. void startmoving(elpath *p1,elpath *p2)
  364. {
  365.     // говорим, что перемещаются ещё 2 элемента
  366.     finished+=2;
  367.     // добавляем два таймера, которые будут периодически вызывать функцию move. В качестве параметра будет передаваться адрес на путь,
  368.     // чтобы его можно было изменять в процессе изменения
  369.     g_timeout_add(MOVEDELAY,(GSourceFunc) move,(gpointer) p1);
  370.     g_timeout_add(MOVEDELAY,(GSourceFunc) move,(gpointer) p2);
  371. }
  372.  
  373. //добавляем в очередь actionqueue события:
  374. //обмен двух элментов
  375. void insertswap(int idx1,int idx2)
  376. {
  377.     action *n=(action*) malloc(sizeof(action));
  378.     n->type=acswap;
  379.     n->param.swap.id1=idx1;
  380.     n->param.swap.id2=idx2;
  381.     actionqueue=g_slist_append(actionqueue,n);
  382. }
  383. //смена состояния элемента
  384. void insertchangestate(int idx,elstate newstate)
  385. {
  386.     action *n=(action*) malloc(sizeof(action));
  387.     n->type=acchangestate;
  388.     n->param.chgst.id=idx;
  389.     n->param.chgst.state=newstate;
  390.     actionqueue=g_slist_append(actionqueue,n);
  391. }
  392. //ожидание t милисекунд
  393. void insertsleep(int t)
  394. {
  395.     action *n=(action*) malloc(sizeof(action));
  396.     n->type=acsleep;
  397.     n->param.time=t;
  398.     actionqueue=g_slist_append(actionqueue,n);
  399. }
  400. //смена текущей фазы
  401. void insertchangephase(int np)
  402. {
  403.     action *n=(action*) malloc(sizeof(action));
  404.     n->type=acchangephase;
  405.     n->param.phase=np;
  406.     actionqueue=g_slist_append(actionqueue,n);
  407. }
  408. //перемещение элемента p->elnum по траектории, указанной в p->linecurve и p->treecurve
  409. gboolean move(elpath* p)
  410. {
  411.     int i;
  412.     GdkPoint lc,tc;
  413.     // получчаем текущие координаты
  414.     lc=el[p->elnum].linecoord;
  415.     tc=el[p->elnum].treecoord;
  416.     // очищаем окно в том месте, где находился элемент
  417.     gdk_window_clear_area(window->window,el[p->elnum].linecoord.x,el[p->elnum].linecoord.y,2*RAD+1,2*RAD+1);
  418.     gdk_window_clear_area(window->window,el[p->elnum].treecoord.x,el[p->elnum].treecoord.y,2*RAD+1,2*RAD+1);
  419.    
  420.     // если мы ещё не исчерпали очередь точек p->linecurve, которая является путём элемента в массиве,
  421.     // то мы достаём из очереди координаты и удаляем первый элемент
  422.     if(p->linecurve!=NULL)
  423.     {
  424.         el[p->elnum].linecoord=*((GdkPoint*) p->linecurve->data);
  425.         free(p->linecurve->data);
  426.         p->linecurve=g_list_remove(p->linecurve,p->linecurve->data);
  427.     }
  428.     // аналогично для элемента в дереве
  429.     if(p->treecurve!=NULL)
  430.     {
  431.         el[p->elnum].treecoord=*((GdkPoint*) p->treecurve->data);
  432.         free(p->treecurve->data);
  433.         p->treecurve=g_list_remove(p->treecurve,p->treecurve->data);
  434.     }
  435.     //перерисовываем все те элементы, которые мы могли затронуть при обмене, кроме своего элемента
  436.     for(i=0;i<N;i++)
  437.     {
  438.         if(i==p->elnum) continue;
  439.         if((el[i].linecoord.x+2*RAD+1>=lc.x&&el[i].linecoord.x<=lc.x+2*RAD+1&&el[i].linecoord.y+2*RAD+1>=lc.y&&el[i].linecoord.y<=lc.y+2*RAD+1)||
  440.            (el[i].treecoord.x+2*RAD+1>=tc.x&&el[i].treecoord.x<=tc.x+2*RAD+1&&el[i].treecoord.y+2*RAD+1>=tc.y&&el[i].treecoord.y<=tc.y+2*RAD+1))
  441.         {
  442.             draw_element(window,window->window,&el[i]);
  443.         }
  444.     }
  445.     if(p->linecurve==NULL&&p->treecurve==NULL)
  446.     {
  447.         //если очередь закончилась, то тогда возвращаем элемент в его обычное состояние
  448.         switch(el[p->elnum].state)
  449.         {
  450.             case activeinplace:
  451.                 el[p->elnum].state=inplace;
  452.                 break;
  453.             case activeinheap:
  454.                 el[p->elnum].state=inheap;
  455.                 break;
  456.             case activeproc:
  457.                 el[p->elnum].state=processed;
  458.                 break;
  459.             default:
  460.                 el[p->elnum].state=normal;
  461.         }
  462.     }
  463.     // рисуем текущий элемент
  464.     draw_element(window,window->window,&el[p->elnum]);
  465.     if(p->linecurve==NULL&&p->treecurve==NULL)
  466.     {
  467.         //если списки закончились, то тогда мы говорим, что перемещаются на один элемент меньше
  468.         // и освобождаем память, которая была занята под путь
  469.         finished--;
  470.         free(p);
  471. //      if(finished==0&&phase==1)
  472. //          phase=2;
  473.         // если мы закончили перемещать все элементы, вызываем визуализацию
  474.         if(finished==0)
  475.             g_timeout_add(SORTDELAY,(GSourceFunc) visualize,NULL);
  476.         return FALSE;
  477.     }
  478.     return TRUE;
  479. }
  480.  
  481. // обменивает два элемента массива arrv и сохраняем в очередь действий этот обмен
  482. void swap(int idx1,int idx2)
  483. {
  484.     if(idx1!=idx2)
  485.     {
  486.         int t=arrv[idx1];
  487.         arrv[idx1]=arrv[idx2];
  488.         arrv[idx2]=t;
  489.         insertswap(idx1,idx2);
  490.     }
  491. }
  492.  
  493. // обменивает два элемента массива el, генерирует путь для перемещения элементов и запускает процесс перемещения
  494. void swapvis(int idx1,int idx2)
  495. {
  496.     elpath *p1,*p2;
  497.     int i;
  498.     element t;
  499.     t=el[idx1];
  500.     el[idx1]=el[idx2];
  501.     el[idx2]=t;
  502.     // создаём два пути
  503.     p1=(elpath*) malloc(sizeof(elpath));
  504.     p2=(elpath*) malloc(sizeof(elpath));
  505.     // генерируем путь для вершин idx1 и idx2 соответственно. для вершины idx1 и idx2 в массиве создадим путь вида
  506.     //       ___idx2___
  507.     //       |        /|\
  508.     //      \|/        |
  509.     //-------------------------
  510.     //       |        /|\
  511.     //      \|/        |
  512.     //  ____idx1____
  513.     //
  514.     // и прямой обмен между вершинами в дереве
  515.     *p1=makepath(idx1,el[idx1].linecoord,el[idx2].linecoord,-RISE,VCOUNT,HCOUNT,VCOUNT,el[idx1].treecoord,el[idx2].treecoord,2*VCOUNT+HCOUNT-2);
  516.     *p2=makepath(idx2,el[idx2].linecoord,el[idx1].linecoord,+RISE,VCOUNT,HCOUNT,VCOUNT,el[idx2].treecoord,el[idx1].treecoord,2*VCOUNT+HCOUNT-2);
  517.     switch(el[idx1].state)
  518.     {
  519.         case inplace:
  520.             el[idx1].state=activeinplace;
  521.             break;
  522.         case inheap:
  523.             el[idx1].state=activeinheap;
  524.             break;
  525.         case processed:
  526.             el[idx1].state=activeproc;
  527.             break;
  528.         default:
  529.             el[idx1].state=active;
  530.     }
  531.     switch(el[idx2].state)
  532.     {
  533.         case inplace:
  534.             el[idx2].state=activeinplace;
  535.             break;
  536.         case inheap:
  537.             el[idx2].state=activeinheap;
  538.             break;
  539.         case processed:
  540.             el[idx2].state=activeproc;
  541.             break;
  542.         default:
  543.             el[idx2].state=active;
  544.     }
  545.    
  546.     // запускаем перемещение по путям p1 и p2 соответственно
  547.     startmoving(p1,p2);
  548. }
  549.  
  550. // возвращает в списке l очередь точек, начиная с точки s до t исключительно, разделённый на (cnt-1) вершин
  551. void genline(GdkPoint s, GdkPoint t,int cnt,GList ** l)
  552. {
  553.     GdkPoint m,*c;
  554.     int i;
  555.     m=s;
  556.     for(i=1;i<cnt;i++)
  557.     {
  558.         c=(GdkPoint*) malloc(sizeof(GdkPoint));
  559.         *c=m;
  560.         *l=g_list_append(*l,c);
  561.         m.x=s.x+i*1.0*(t.x-s.x)/(cnt-1);
  562.         m.y=s.y+i*1.0*(t.y-s.y)/(cnt-1);
  563.     }
  564. }
  565.  
  566. // создаёт путь для вершины idx путь в массиве начиная с точки listb до точки liste
  567. // точка сначала поднимется на dy вверх, перемещается до liste.x и опускается на dy вниз.
  568. // на каждом этапе будет соответственно listc1-1, listc2-1 и listc3-1 точки. Также в конце будет добавлена точка t
  569. // для дерева будет создан отрезок из treep1 в treep2 исключительно длинной в treec-1 и добавлена вершина treep2
  570. elpath makepath(gint idx,GdkPoint listb,GdkPoint liste, gint dy, gint listc1, gint listc2,gint listc3,GdkPoint treep1,GdkPoint treep2, gint treec)
  571. {
  572.     GdkPoint s,t,*c;
  573.     elpath res;
  574.     double tx,ty;
  575.     GList *listl=NULL,*treel=NULL;
  576.     int i;
  577.     s=t=listb;
  578.     t.y+=dy;
  579.     genline(s,t,listc1,&listl);
  580.    
  581.     s=listb;
  582.     s.y+=dy;
  583.     t=liste;
  584.     t.y+=dy;
  585.     genline(s,t,listc2,&listl);
  586.    
  587.     s=liste;
  588.     s.y+=dy;
  589.     t=liste;
  590.     genline(s,t,listc3,&listl);
  591.    
  592.     c=(GdkPoint*) malloc(sizeof(GdkPoint));
  593.     *c=t;
  594.     listl=g_list_append(listl,c);
  595.    
  596.     genline(treep1,treep2,treec,&treel);
  597.    
  598.     c=(GdkPoint*) malloc(sizeof(GdkPoint));
  599.     *c=treep2;
  600.     treel=g_list_append(treel,c);
  601.    
  602.     res.linecurve=listl;
  603.     res.treecurve=treel;
  604.     res.elnum=idx;
  605.    
  606.     return res;
  607. }
  608.  
  609. // Один из этапов пирамидальной сортировки. Мы пытаемся поднять вершину наверх.
  610. // Для этого мы сравниваем текущую вершину i  с вершиной (i-1)/2. Если он больше, то мы
  611. // меняем элементы и поднимаемся наверх
  612. void upHeap(int* array, int i)
  613. {
  614.     if(i>0)
  615.     {
  616.         if(array[i]>array[(i-1)/2])
  617.         {
  618.             swap(i,(i-1)/2);
  619.             upHeap(array,(i-1)/2);
  620.         }
  621.     }
  622. }
  623.  
  624. // Один из этапов пирамидальной сортировки. Мы пытаемся опустить вершину вниз.
  625. // Для этого мы определяем наибольшую вершину среди детей i-той вершины и сравниваем. Если наш
  626. // элемент меньше, то мы меняем их и спускаемся вниз
  627. void downHeap(int* array, int i,int cnt)
  628. {
  629.     int child=i*2+1;
  630.     if(child<cnt)
  631.     {
  632.         if(child+1<cnt&&array[child]<array[child+1])
  633.             child++;
  634.         if(array[child]>array[i])
  635.         {
  636.             swap(child,i);
  637.             downHeap(array,child,cnt);
  638.         }
  639.     }
  640. }
  641.  
  642. // упорядочиваем массив array, составляю очередь действий
  643. void sort(int *array)
  644. {
  645.     int i;
  646. #ifdef HEAPSORTA
  647.     //добавляем в очередь смену состояния корня и добавляем задержку
  648.     insertchangestate(0,inheap);
  649.     insertsleep(SORTDELAY);
  650.     for(i=1;i<N;i++)
  651.     {
  652.         //меняем состояние i-той вершины, добавляем задержку и пытаемся просеять эту вершину вверх
  653.         insertchangestate(i,inheap);
  654.         insertsleep(REDRAWDELAY);
  655.         upHeap(array,i);
  656.         insertsleep(SORTDELAY);
  657.     }
  658.     // очищаем состояния всех вершин
  659.     for(i=0;i<N;i++)
  660.     {
  661.         insertchangestate(i,normal);
  662.     }
  663.     insertsleep(SORTDELAY);
  664.     for(i=N-1;i>0;i--)
  665.     {
  666.         // меняем фазу на "Исключение наибольшего элемента", говорим, что первый элемент на месте и меняем его с последним элементом массива
  667.         insertchangephase(1);
  668.         insertchangestate(0,inplace);
  669.         swap(i,0);
  670.         insertchangephase(2);
  671.         insertsleep(REDRAWDELAY);
  672.         //просеиваем новый первый элемент вниз
  673.         downHeap(array,0,i);
  674.         insertsleep(SORTDELAY);
  675.     }
  676.     insertchangestate(0,inplace);
  677.     insertchangephase(3);
  678. #elif HEAPSORTB
  679.     // говорим, что обработали последнюю половину элементов
  680.     for(i=N-1;2*i+1>=N;i--)
  681.     {
  682.         insertchangestate(i,processed);
  683.     }
  684.     for(i=N/2-1;i>=0;i--)
  685.     {
  686.         //меняем состояние i-той вершины и пытаемся просеять её вниз
  687.         insertchangestate(i,processed);
  688.         downHeap(array,i,N);
  689.         insertsleep(SORTDELAY);
  690.     }
  691.     // очищаем состояния всех вершин
  692.     for(i=0;i<N;i++)
  693.     {
  694.         insertchangestate(i,normal);
  695.     }
  696.     insertsleep(SORTDELAY);
  697.     for(i=N-1;i>0;i--)
  698.     {
  699.         // меняем фазу на "Исключение наибольшего элемента", говорим, что первый элемент на месте и меняем его с последним элементом массива
  700.         insertchangephase(1);
  701.         insertchangestate(0,inplace);
  702.         swap(i,0);
  703.         insertchangephase(2);
  704.         insertsleep(REDRAWDELAY);
  705.         //просеиваем новый первый элемент вниз
  706.         downHeap(array,0,i);
  707.         insertsleep(SORTDELAY);
  708.     }
  709.     insertchangestate(0,inplace);
  710.     insertchangephase(3);
  711. #elif SHELLSORT
  712.     int h = 1;
  713.     int prev;
  714.     // в качестве последовательности шагов мы будем рассматривать последовательность 1, 4, 13, 40,...
  715.     while ( h <= N / 9 )
  716.         h = 3 * h + 1;
  717.  
  718.     while ( h > 0 ) {
  719.         // сортируем массив какой-нибудь сортировкой. ниже реализован алгоритм, похожий на сортировку вставками
  720.         for ( i = h; i < N; i++ ) {
  721.             int k;
  722.             // рассмотрим последовательность вершин, которые находятся раньше текущей и расположены на расстоянии h,2*h,3*h,... от ней
  723.             // подсветим их все
  724.             for(k=i;k>=0;k-=h)
  725.                 insertchangestate(k,processed);
  726.             insertsleep(REDRAWDELAY);
  727.             int j;
  728.             prev=i;
  729.             // так как эта последовательность отсортирована, то достаточно перемещать последний элемент массива влево, пока он меньше предыдущего
  730.             for ( j = i; j >= h && array[j - h] > array[j]; j -= h )
  731.             {
  732.                 swap(j,j-h);
  733.             }
  734.             // возвращаем всем вершинам нашей последовательности состояние normal
  735.             for(k=i;k>=0;k-=h)
  736.                 insertchangestate(k,normal);
  737.             insertsleep(REDRAWDELAY);
  738.         }
  739.         h /= 3;
  740.     }
  741.     insertchangephase(3);
  742. #elif BUBBLESORT
  743.     for(i=0;i<N;i++)
  744.     {
  745.         int j;
  746.         for(j=0;j<N-i-1;j++)
  747.         {
  748.             // подсвечиваем j тый и j+1 ый элементы
  749.             insertchangestate(j,processed);
  750.             insertchangestate(j+1,processed);
  751.             insertsleep(REDRAWDELAY);
  752.             if(array[j]>array[j+1])
  753.             {
  754.                 // если они неправильно стоят, меняем их местами
  755.                 swap(j,j+1);
  756.             }
  757.             //возвращаем нормальное состояние элементам
  758.             insertchangestate(j,normal);
  759.             insertchangestate(j+1,normal);
  760.             insertsleep(REDRAWDELAY);
  761.         }
  762.         // говорим, что последний элемент на месте
  763.         insertchangestate(j,inplace);
  764.         insertsleep(REDRAWDELAY);
  765.     }
  766.     insertchangephase(3);
  767. #else
  768.     quicksort(N-1,array,0);
  769.     insertchangephase(3);
  770. #endif
  771. }
  772.  
  773. // сортируем массив a, содержащий n элементов, который является массивом array с пропущенными offset первыми элементами
  774. void quicksort(int n,int *a,int offset)
  775. {
  776.     int i=0,j=n,k;
  777.     int p=a[n>>1];
  778.    
  779.     // подсвечиваем текущий интервал
  780.     for(k=0;k<=n;k++)
  781.     {
  782.         insertchangestate(k+offset,activeinterval);
  783.     }
  784.     insertsleep(REDRAWDELAY);
  785.     insertchangestate(i+offset,processed);
  786.     insertchangestate(j+offset,processed);
  787.     do
  788.     {
  789.         // находим первый элемент с начала массива, который не меньше p
  790.         while(a[i]<p)
  791.         {
  792.             insertchangestate(i+offset,activeinterval);
  793.             i++;
  794.             if(i<=j)insertchangestate(i+offset,processed);
  795.             insertsleep(REDRAWDELAY);
  796.         }
  797.         insertsleep(REDRAWDELAY);
  798.         // находим первый элемент с конца массива, который не больше p
  799.         while(a[j]>p)
  800.         {
  801.             insertchangestate(j+offset,activeinterval);
  802.             j--;
  803.             if(i<=j)insertchangestate(j+offset,processed);
  804.             insertsleep(REDRAWDELAY);
  805.         }
  806.         insertsleep(REDRAWDELAY);
  807.         // если индекс i, который пробегает массив с начала, больше, чем индекс j, который пробегает массив с конца,
  808.         // то обменивать нечего, иначе
  809.         if(i<=j)
  810.         {
  811.             // меняем эти два элемента и перемещаем указатели i и j
  812.             swap(offset+i,offset+j);
  813.             insertchangestate(i+offset,activeinterval);
  814.             insertchangestate(j+offset,activeinterval);
  815.             i++;
  816.             j--;
  817.             if(i<=j)
  818.             {
  819.                 insertchangestate(i+offset,processed);
  820.                 insertchangestate(j+offset,processed);
  821.                 insertsleep(REDRAWDELAY);
  822.             }
  823.         }
  824.     }
  825.     while(i<=j);
  826.     // убираем подсветку активного диапазона
  827.     for(k=0;k<=n;k++)
  828.     {
  829.         insertchangestate(k+offset,normal);
  830.     }
  831.     // если интервал 0..j не состоит из одного элемента, то вызываем quicksort для него
  832.     if(j>0) quicksort(j,a,offset);
  833.     // если интервал i..n не состоит из одного элемента, то вызываем quicksort для него
  834.     if(i<n) quicksort(n-i,a+i,offset+i);
  835. }
  836.  
  837. //если окно было закрыто, завершаем работу
  838. gboolean delete_event(GtkWidget *w,GdkEvent *e, gpointer data)
  839. {
  840.     gtk_main_quit();
  841.     return TRUE;
  842. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!