home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c480 / 17.ddi / SAMPLES / SORTDEMO / SORTDEMO.C_ / SORTDEMO.C
Encoding:
C/C++ Source or Header  |  1993-02-08  |  35.8 KB  |  1,212 lines
  1. /****************************************************************************
  2.  
  3.     PROGRAM: Sortdemo.c
  4.  
  5.     PURPOSE: Demonstrates several sorting algorithms in a Windows-hosted
  6.              application.
  7.  
  8.     FUNCTIONS:
  9.  
  10.     WinMain() - calls initialization function, processes message loop
  11.     InitApplication() - initializes window data and registers window
  12.     InitInstance() - saves instance handle and creates main window
  13.     MainWndProc() - processes messages
  14.     InitStats() -  initializes statistics for Stats dialog box
  15.     InitPrevRandom() - initializes array and display to last randomized values
  16.     InitSort() - initializes sort and statistics and gets a device content
  17.     EndSort() - releases the device context and sets the cursor to an arrow
  18.     SetNewColors() - sets a new color that's different from the previous bar
  19.     DrawBar() -  erases a bar and draws a new bar in its place
  20.     DrawTime() - paints the statistics on the window during the sort
  21.     Swaps() -  exchanges two bar structures
  22.     SwapBars() - draws the two swapped bars and the statistics
  23.     Sleep() - pauses for a specified number of microseconds
  24.     Beep() - sounds the speaker at a frequency for a duration
  25.     InitBars() - initializes a random set of bars
  26.     InsertionSort() - performs an insertion sort on abarWork
  27.     BubbleSort() - performs a bubble sort on abarWork
  28.     HeapSort() - performs a heap sort on abarWork
  29.     PercolateUp() - converts elements into a reverse heap
  30.     PercolateDown() - converts reverse heap into a sorted heap
  31.     ExchangeSort() - performs an exchange sort on abarWork
  32.     ShellSort() - performs a shell sort on abarWork
  33.     QuickSort() -  performs a quick sort on abarWork
  34.     About() - processes messages for "About" dialog box
  35.     Stats() - processes messages for the "Statistics" dialog box
  36.     Pause() - processes messages for the "Pause" dialog box
  37.  
  38.  
  39. ****************************************************************************/
  40.  
  41. #include "windows.h"
  42. #include <time.h>
  43. #include <string.h>
  44. #include <conio.h>
  45. #include <math.h>
  46. #include <malloc.h>
  47. #include <stdlib.h>
  48. #include <stdio.h>
  49.  
  50. #include "sortdemo.h"
  51. #include "resource.h"
  52.  
  53. ///////////////////////////////////////////////////////////////////////
  54. // Global variables
  55. ///////////////////
  56.  
  57. short cxClient, cyClient;
  58. int fTallest;
  59. BOOL sound = FALSE;
  60. BOOL NewRandom = TRUE;
  61. clock_t clStart, clFinish;
  62. clock_t clPause = 30L; //  determines speed of swaps
  63. float fTime;
  64. HCURSOR hCross, hArrow, hHour;
  65. HDC TempDC = NULL;
  66. int nBar=NUMBARS, iSwaps, iCompares, nCurrentColor;
  67. BAR abarWork[NUMBARS], abarPerm[NUMBARS], abarTemp[NUMBARS];
  68.  
  69. TIMESTRUCT Insertion = { (float)0.0, 0, 0, FALSE };
  70. TIMESTRUCT Bubble = { (float)0.0, 0, 0, FALSE };
  71. TIMESTRUCT Heap = { (float)0.0, 0, 0, FALSE };
  72. TIMESTRUCT Exchange = { (float)0.0, 0, 0, FALSE };
  73. TIMESTRUCT Shell = { (float)0.0 , 0, 0, FALSE };
  74. TIMESTRUCT Quick = { (float)0.0, 0, 0, FALSE };
  75. RECT rectPage = {0, 1000, 1000, 0};
  76. RECT rectData = {50, 50, 950, 850};
  77.  
  78. HANDLE hInst;
  79.  
  80. /****************************************************************************
  81.  
  82.     FUNCTION: WinMain(HANDLE, HANDLE, LPSTR, int)
  83.  
  84.     PURPOSE: calls initialization function, processes message loop
  85.  
  86. ****************************************************************************/
  87.  
  88. int PASCAL WinMain(HANDLE hInstance, HANDLE hPrevInstance, 
  89.                     LPSTR lpCmdLine, int nCmdShow)
  90.  
  91. {
  92.     MSG msg;
  93.  
  94.     if (!hPrevInstance)
  95.     if (!InitApplication(hInstance))
  96.         return (FALSE);
  97.  
  98.     if (!InitInstance(hInstance, nCmdShow))
  99.         return (FALSE);
  100.  
  101.     while (GetMessage(&msg, NULL, NULL, NULL)) {
  102.     TranslateMessage(&msg);
  103.     DispatchMessage(&msg);
  104.     }
  105.     return (msg.wParam);
  106. }
  107.  
  108.  
  109. /****************************************************************************
  110.  
  111.     FUNCTION: InitApplication(HANDLE)
  112.  
  113.     PURPOSE: Initializes window data and registers window class
  114.  
  115. ****************************************************************************/
  116.  
  117. BOOL InitApplication(HANDLE hInstance)
  118.  
  119. {
  120.     WNDCLASS  wc;
  121.  
  122.     wc.style = CS_HREDRAW | CS_VREDRAW;
  123.     wc.lpfnWndProc = MainWndProc;
  124.     wc.cbClsExtra = 0;
  125.     wc.cbWndExtra = 0;
  126.     wc.hInstance = hInstance;
  127.     wc.hIcon = LoadIcon(hInstance, "sort");
  128.     wc.hCursor = LoadCursor(NULL, IDC_ARROW);
  129.     wc.hbrBackground = GetStockObject(WHITE_BRUSH);
  130.     wc.lpszMenuName =  "MainMenu";
  131.     wc.lpszClassName = "SortDemoClass";
  132.  
  133.     return (RegisterClass(&wc));
  134. }
  135.  
  136.  
  137. /****************************************************************************
  138.  
  139.     FUNCTION:  InitInstance(HANDLE, int)
  140.  
  141.     PURPOSE:  Saves instance handle and creates main window
  142.  
  143. ****************************************************************************/
  144.  
  145. BOOL InitInstance(HANDLE hInstance, int nCmdShow)
  146.  
  147. {
  148.     HWND            hWnd;
  149.  
  150.     hInst = hInstance;
  151.  
  152.     hWnd = CreateWindow(
  153.         "SortDemoClass",
  154.         "SortDemo Sample Application",
  155.         WS_OVERLAPPEDWINDOW,
  156.         CW_USEDEFAULT,
  157.         CW_USEDEFAULT,
  158.         CW_USEDEFAULT,
  159.         CW_USEDEFAULT,
  160.         NULL,
  161.         NULL,
  162.         hInstance,
  163.         NULL
  164.     );
  165.  
  166.     if (!hWnd)
  167.         return (FALSE);
  168.  
  169.     ShowWindow(hWnd, nCmdShow);
  170.     UpdateWindow(hWnd);
  171.     return (TRUE);
  172.  
  173. }
  174.  
  175. /****************************************************************************
  176.  
  177.     FUNCTION: MainWndProc(HWND, UINT, UINT, LONG)
  178.  
  179.     PURPOSE:  Processes messages
  180.  
  181.     MESSAGES:
  182.  
  183.     WM_COMMAND    - application menu
  184.     WM_CREATE     - create window and objects
  185.     WM_PAINT      - update window, draw objects
  186.     WM_DESTROY    - destroy window
  187.  
  188.  
  189. ****************************************************************************/
  190.  
  191. long FAR PASCAL __export MainWndProc(HWND hWnd,UINT message, UINT wParam, 
  192.                                                     LONG lParam)
  193.  
  194. {
  195.     FARPROC lpProcAbout;
  196.     FARPROC lpProcStats;
  197.     FARPROC lpProcPause;
  198.     HMENU menu;
  199.  
  200.     switch (message) {
  201.     case WM_COMMAND: {
  202.         switch(wParam) {
  203.  
  204.             case IDM_EXIT:
  205.                 DestroyWindow(hWnd);
  206.                 return 0;
  207.  
  208.             case IDM_INSERT:
  209.                 InitSort(hWnd);
  210.                 InsertionSort();
  211.                 EndSort(hWnd);
  212.                 InitStats(&Insertion);
  213.                 return 0;
  214.  
  215.             case IDM_BUBBLE:
  216.                 InitSort(hWnd);
  217.                 BubbleSort();
  218.                 EndSort(hWnd);
  219.                 InitStats(&Bubble);
  220.                 return 0;
  221.  
  222.             case IDM_HEAP:
  223.                 InitSort(hWnd);
  224.                 HeapSort();
  225.                 EndSort(hWnd);
  226.                 InitStats(&Heap);
  227.                 return 0;
  228.  
  229.             case IDM_EXCHANGE:
  230.                 InitSort(hWnd);
  231.                 ExchangeSort();
  232.                 EndSort(hWnd);
  233.                 InitStats(&Exchange);
  234.                 return 0;
  235.  
  236.             case IDM_SHELL:
  237.                 InitSort(hWnd);
  238.                 ShellSort();
  239.                 EndSort(hWnd);
  240.                 InitStats(&Shell);
  241.                 return 0;
  242.  
  243.             case IDM_QUICK:
  244.                 InitSort(hWnd);
  245.                 QuickSort(0, nBar-1);
  246.                 EndSort(hWnd);
  247.                 InitStats(&Quick);
  248.                 return 0;
  249.  
  250.             case IDM_RAND: // initialize random numbers into abarPerm array
  251.                 InitBars();
  252.                 Insertion.done=FALSE;
  253.                 Bubble.done = FALSE;
  254.                 Heap.done = FALSE;
  255.                 Exchange.done = FALSE;
  256.                 Shell.done = FALSE;
  257.                 Quick.done = FALSE;
  258.                 NewRandom = TRUE;   // set new random flag so first sort after randomize
  259.                                     // will use new random data
  260.  
  261.                 InvalidateRect(hWnd, NULL, TRUE);
  262.                 return 0;
  263.  
  264.             case IDM_SOUND:
  265.                 sound = !sound;
  266.                 // check or uncheck menu
  267.                 menu = GetMenu(hWnd);
  268.                 sound?   CheckMenuItem(menu, IDM_SOUND, MF_CHECKED)
  269.                         :CheckMenuItem(menu, IDM_SOUND, MF_UNCHECKED);
  270.                 return 0;
  271.  
  272.             case IDM_STATS:
  273.                 lpProcStats = MakeProcInstance(Stats, hInst);
  274.                 DialogBox(hInst,"Stats", hWnd, lpProcStats);
  275.                 FreeProcInstance(lpProcStats);
  276.                 return 0;
  277.  
  278.             case IDM_PAUSE:
  279.                 lpProcPause = MakeProcInstance(Pause, hInst);
  280.                 DialogBox(hInst,"Pause", hWnd,lpProcPause);
  281.                 FreeProcInstance(lpProcStats);
  282.                 return 0;
  283.  
  284.             case IDM_ABOUT:
  285.                 lpProcAbout = MakeProcInstance(About, hInst);
  286.                 DialogBox(hInst, "AboutBox", hWnd, lpProcAbout);
  287.                 FreeProcInstance(lpProcAbout);
  288.                 return 0;
  289.  
  290.             default:
  291.                 return (DefWindowProc(hWnd, message, wParam, lParam));
  292.         } //switch wParam
  293.     } // Case WM_COMMAND
  294.     case WM_CREATE:
  295.         hArrow = LoadCursor(NULL, IDC_ARROW);
  296.         hHour = LoadCursor(NULL, IDC_WAIT);
  297.         InitBars();
  298.         return 0;
  299.  
  300.     case WM_PAINT:{
  301.         RenderBars(hWnd);
  302.         return 0;
  303.     }
  304.  
  305.     case WM_DESTROY:
  306.         PostQuitMessage(0);
  307.         return 0;
  308.  
  309.     default:
  310.         return (DefWindowProc(hWnd, message, wParam, lParam));
  311.     }
  312.     return 0;
  313. }
  314.  
  315. //RenderBars: paints the randomized sort bars on the window
  316. void RenderBars(HWND hWnd)
  317. {
  318.     HDC hDC;                          /* display-context variable  */
  319.     PAINTSTRUCT ps;                   /* paint structure           */
  320.     float flFraction;
  321.     short nWidth, i, nCurrentHeight, nNewHeight;
  322.     COLOR Color;
  323.     RECT rectBar;
  324.     HPEN hWhitePen, hOldPen;
  325.     HBRUSH hNewBrush, hOldBrush,hNewBarBrush, hOldBarBrush ;
  326.  
  327.     InvalidateRect(hWnd, NULL, TRUE); //invalidate entire window
  328.     hDC = BeginPaint(hWnd, &ps);
  329.     cxClient = ps.rcPaint.right - ps.rcPaint.left;
  330.     cyClient = ps.rcPaint.bottom - ps.rcPaint.top;
  331.  
  332.     SetMapMode(hDC, MM_ANISOTROPIC);
  333.     SetWindowExt(hDC, rectPage.right, rectPage.top);
  334.     SetViewportExt(hDC, cxClient, -cyClient); // Set up Window
  335.     SetViewportOrg (hDC, 0, cyClient);
  336.  
  337.     // A rectangle around the chart.
  338.     //
  339.     hWhitePen = CreatePen(PS_SOLID, 1, RGB(255, 255, 255));
  340.     hOldPen = SelectObject(hDC, hWhitePen);
  341.     Rectangle(hDC, rectData.left,rectData.top, rectData.right, rectData.bottom );
  342.  
  343.     // Create and select the brush to draw the chart data itself
  344.     //
  345.     hNewBrush = CreateSolidBrush(RGB(0, 0, 0));
  346.     hOldBrush = SelectObject(hDC, hNewBrush);
  347.  
  348.     SelectObject(hDC, hOldPen);
  349.     DeleteObject(hWhitePen);
  350.  
  351.     flFraction = ((rectData.right - rectData.left) / nBar);
  352.     nWidth = (short) flFraction;
  353.  
  354.     for (i = 0; i < nBar; i++)
  355.     {
  356.         nNewHeight = abarWork[i].len;
  357.         Color = abarWork[i].clr;
  358.  
  359.         // Calculate the size of the bar.
  360.         //
  361.         flFraction = (float) nNewHeight / (float) fTallest;
  362.         nCurrentHeight = (short) (flFraction * (rectData.bottom - rectData.top));
  363.  
  364.         rectBar.left = rectData.left + (nWidth * i);
  365.         rectBar.top = nCurrentHeight + rectData.top;
  366.         rectBar.right = rectData.left + nWidth * (i+1);
  367.         rectBar.bottom = rectBar.top - nCurrentHeight;
  368.  
  369.         hNewBarBrush = CreateSolidBrush(RGB(Color.nRed, Color.nGreen, Color.nBlue));
  370.         hOldBarBrush =  SelectObject(hDC, hNewBarBrush);
  371.  
  372.         Rectangle(hDC, rectBar.left,rectBar.top,rectBar.right,rectBar.bottom);
  373.  
  374.         // Delete the brush, after selecting the old one back into the DC.
  375.         SelectObject(hDC, hOldBarBrush);
  376.         DeleteObject(hNewBarBrush);
  377.     }
  378.  
  379.     // Delete the brush, after selecting the old one back in the DC.
  380.     //
  381.     SelectObject(hDC, hOldBrush);
  382.     DeleteObject(hNewBrush);
  383.     EndPaint (hWnd, &ps);
  384. }
  385.  
  386.  
  387. // InitStats: initializes statistics for Stats dialog box
  388. void InitStats(TIMESTRUCT *tm)
  389. {
  390.     tm->time = fTime;
  391.     tm->swaps = iSwaps;
  392.     tm->compares = iCompares;
  393.     tm->done = TRUE;
  394. }
  395.  
  396.  
  397. // InitPrevRandom: initializes abarWork to previous random values and
  398. // repaints random display
  399. void InitPrevRandom(HWND hWnd)
  400. {
  401.     int iRow;
  402.     for( iRow = 0; iRow < nBar; iRow++ )
  403.     {
  404.         abarWork[iRow] = abarPerm[iRow];
  405.         abarTemp[iRow] = abarPerm[iRow];
  406.     }
  407.     RenderBars(hWnd);
  408. }
  409.  
  410.  
  411. //InitSort: Initializes everything for a new sort and gets a device context
  412. //
  413. void InitSort(HWND hWnd)
  414. {
  415.     if (NewRandom)              // if randomize just occurred
  416.         NewRandom = FALSE;      // make sure next sorts use new data
  417.     else                        // if first sort has already been done
  418.         InitPrevRandom(hWnd);   // restore last randomized bars
  419.  
  420.     TempDC = GetDC(hWnd);
  421.     SetMapMode(TempDC, MM_ANISOTROPIC);
  422.     SetWindowExt(TempDC, rectPage.right, rectPage.top);
  423.     SetViewportExt(TempDC, cxClient, -cyClient); // Set up Window
  424.     SetViewportOrg (TempDC, 0, cyClient);
  425.     SetCursor(hHour);
  426.  
  427.     clStart = clock();
  428.     clFinish = 0;
  429.     iSwaps = 0;
  430.     iCompares = 0;
  431. }
  432.  
  433. // EndSort: Releases the device context and sets cursor back to an arrow
  434. //
  435. void EndSort(HWND hWnd)
  436. {
  437.     DrawTime();
  438.     ReleaseDC(hWnd, TempDC);
  439.     TempDC = NULL;
  440.     SetCursor(hArrow);
  441. }
  442.  
  443. // SetNewColors: Sets a new color that's different from the previous bar.
  444. COLOR SetNewColors()
  445. {
  446.     COLOR newColor;
  447.     nCurrentColor++;
  448.     nCurrentColor %= NUMBARS;
  449.     newColor.nBlue = (nCurrentColor & 1) ? 255 : 0;
  450.     newColor.nGreen = (nCurrentColor & 2) ? 255 : 0;
  451.     newColor.nRed = (nCurrentColor & 4) ? 255 : 0;
  452.     return newColor;
  453. }
  454.  
  455.  
  456. // DrawBar: Erases a bar and draws a new bar in its place
  457. //
  458. void DrawBar( int Bar )
  459. {
  460.     RECT rectBar;
  461.     HPEN hWhitePen, hOldPen;
  462.     HBRUSH hWhiteBrush, hOldBrush, hBarBrush;
  463.     float flFraction;
  464.     short nCurrentHeight, nWidth;
  465.  
  466.     flFraction = ((rectData.right  - rectData.left) / nBar);
  467.     nWidth = (short) flFraction;
  468.  
  469.     // draw white rectangle over old bar
  470.     flFraction = (float) abarTemp[Bar].len / (float) fTallest;
  471.     nCurrentHeight = (short) (flFraction * (rectData.bottom - rectData.top));
  472.  
  473.     rectBar.left = rectData.left + (nWidth * Bar);
  474.     rectBar.top = nCurrentHeight + rectData.top;
  475.     rectBar.right = rectData.left + nWidth * (Bar+1);
  476.     rectBar.bottom = rectBar.top - nCurrentHeight;
  477.  
  478.     hWhitePen = CreatePen(PS_SOLID, 1, RGB(255, 255, 255));
  479.     hOldPen = SelectObject(TempDC, hWhitePen);
  480.  
  481.     hWhiteBrush = CreateSolidBrush(RGB(255, 255, 255));
  482.     hOldBrush = SelectObject(TempDC, hWhiteBrush);
  483.     Rectangle(TempDC, rectBar.left, rectBar.top, rectBar.right, rectBar.bottom);
  484.     SelectObject(TempDC, hOldPen);
  485.     DeleteObject(hWhitePen);
  486.     SelectObject(TempDC, hOldBrush);
  487.     DeleteObject(hWhiteBrush);
  488.  
  489.     // draw new colored rectangle
  490.     flFraction = (float) abarWork[Bar].len / (float) fTallest;
  491.     nCurrentHeight = (short) (flFraction * (rectData.bottom - rectData.top));
  492.  
  493.  
  494.     rectBar.left = rectData.left + (nWidth * Bar);
  495.     rectBar.top = nCurrentHeight + rectData.top;
  496.     rectBar.right = rectData.left + nWidth * (Bar+1);
  497.     rectBar.bottom = rectBar.top - nCurrentHeight;
  498.  
  499.  
  500.  
  501.     hBarBrush = CreateSolidBrush(RGB(   abarWork[Bar].clr.nRed,
  502.                                         abarWork[Bar].clr.nGreen,
  503.                                         abarWork[Bar].clr.nBlue));
  504.     hOldBrush = SelectObject(TempDC, hBarBrush);
  505.  
  506.     Rectangle(TempDC,rectBar.left,rectBar.top,rectBar.right, rectBar.bottom);
  507.     // Delete the brush, after selecting the old one back into the DC.
  508.     //
  509.     SelectObject(TempDC, hOldBrush);
  510.     DeleteObject(hBarBrush);
  511.  
  512.     abarTemp[Bar] = abarWork[Bar];
  513.  
  514.     if( sound == TRUE)
  515.     {
  516.         Beep( 60 * Bar, 75 );   // Play note
  517.         Sleep( clPause - 75L );  // Pause adjusted for note duration
  518.     }
  519.     else
  520.     Sleep( clPause );        // Pause
  521.  
  522. }
  523.  
  524. //DrawTime: Paints the statistics on the window during the sort
  525. //
  526. void DrawTime()
  527. {
  528.     char szTime[30], szSwaps[20], szCompares[20];
  529.  
  530.     clFinish = clock();
  531.  
  532.     fTime =  (float)(clFinish - clStart) / CLOCKS_PER_SEC ;
  533.  
  534.     sprintf(szTime, "Seconds: %5.2f",fTime);
  535.     sprintf(szSwaps, "Swaps: %4.i", iSwaps);
  536.     sprintf(szCompares, "Compares: %4.i", iCompares);
  537.  
  538.  
  539.     // Print the number of seconds elapsed
  540.     TextOut(TempDC, 50, 975, szTime, strlen(szTime));
  541.     TextOut(TempDC, 425, 975, szSwaps, strlen(szSwaps));
  542.     TextOut(TempDC, 750, 975, szCompares, strlen(szCompares));
  543.  
  544. }
  545.  
  546.  
  547. // Swaps: Exchanges two bar structures.
  548. //
  549. void Swaps( BAR *bar1, BAR *bar2 )
  550. {
  551.     BAR barTmp;
  552.  
  553.     ++iSwaps;
  554.     barTmp = *bar1;
  555.     *bar1  = *bar2;
  556.     *bar2  = barTmp;
  557. }
  558.  
  559.  
  560. // SwapBars - Calls DrawBar twice to switch the two bars in iRow1 and
  561. // iRow2, then calls DrawTime to update the time.
  562. //
  563. void SwapBars( int iRow1, int iRow2 )
  564. {
  565.     DrawBar( iRow1 );
  566.     DrawBar( iRow2 );
  567.     DrawTime();
  568. }
  569.  
  570. // Sleep: Pauses for a specified number of microseconds.
  571. //
  572. void Sleep( clock_t wait )
  573. {
  574.     clock_t goal;
  575.  
  576.     goal = wait + clock();
  577.     while( goal >= clock() );
  578. }
  579.  
  580.  
  581. // Beep: Sounds the speaker for a time specified in microseconds by
  582. // duration at a pitch specified in hertz by frequency.
  583. //
  584. void Beep( int frequency, int duration )
  585. {
  586.  
  587.     int control;
  588.  
  589.     // If frequency is 0, Beep doesn't try to make a sound. It
  590.     // just sleeps for the duration.
  591.  
  592.     if( frequency )
  593.     {
  594.         // 75 is about the shortest reliable duration of a sound.
  595.         if( duration < 75 )
  596.             duration = 75;
  597.  
  598.         // Prepare timer by sending 10111100 to port 43.
  599.         _outp( 0x43, 0xb6 );
  600.  
  601.         // Divide input frequency by timer ticks per second and
  602.         // write (byte by byte) to timer.
  603.  
  604.         frequency = (unsigned)(1193180L / frequency);
  605.         _outp( 0x42, (char)frequency );
  606.         _outp( 0x42, (char)(frequency >> 8) );
  607.  
  608.         // Save speaker control byte.
  609.         control = _inp( 0x61 );
  610.  
  611.         // Turn on the speaker (with bits 0 and 1).
  612.         _outp( 0x61, control | 0x3 );
  613.     }
  614.  
  615.     Sleep( (clock_t)duration );
  616.  
  617.     // Turn speaker back on if necessary.
  618.     if( frequency )
  619.         _outp( 0x61, control );
  620.  
  621. }
  622.  
  623.  
  624. // InitBars: Initializes a random set of bars
  625. //
  626. void InitBars()
  627. {
  628.     int aTemp[NUMBARS], iRow, iRowMax, iRand, iLength;
  629.     float flFraction;
  630.     short nWidth;
  631.  
  632.     // Seed the random-number generator.
  633.     srand( (unsigned)time( NULL ) );
  634.  
  635.  
  636.     // Randomize an array of rows.
  637.     for( iRow = 0; iRow < nBar; iRow++ )
  638.            aTemp[iRow] = iRow + 1;
  639.     iRowMax = nBar - 1;
  640.  
  641.     flFraction = ((rectData.right - rectData.left) / nBar);
  642.     nWidth = (short) flFraction;
  643.  
  644.  
  645.     nCurrentColor = 0;
  646.     fTallest = 0;
  647.     for( iRow = 0; iRow < nBar; iRow++ )
  648.     {
  649.         // Find a random element in aTemp between 0 and iRowMax,
  650.         // then assign the value in that element to iLength.
  651.  
  652.         iRand = GetRandom( 0, iRowMax );
  653.         iLength = aTemp[iRand];
  654.  
  655.         // Overwrite the value in aTemp[iRand] with the value in
  656.         // aTemp[iRowMax] so the value in aTemp[iRand] is
  657.         // chosen only once.
  658.         //
  659.         aTemp[iRand] = aTemp[iRowMax];
  660.  
  661.         // Decrease the value of iRowMax so that aTemp[iRowMax] can't
  662.         // be chosen on the next pass through the loop.
  663.         //
  664.         --iRowMax;
  665.         abarPerm[iRow].len = iLength;
  666.         if (iLength > fTallest) fTallest = iLength;
  667.         abarPerm[iRow].clr = SetNewColors();
  668.     }
  669.  
  670.     // Assign permanent sort values to temporary and draw unsorted bars.
  671.  
  672.     for( iRow = 0; iRow < nBar; iRow++ )
  673.     {
  674.         abarWork[iRow] = abarPerm[iRow];
  675.         abarTemp[iRow] = abarPerm[iRow];
  676.     }
  677. }
  678.  
  679. // InsertionSort: InsertionSort compares the length of each element
  680. // with the lengths of all the preceding elements. When the appropriate
  681. // place for the new element is found, the element is inserted and
  682. // all the other elements are moved down one place.
  683. //
  684. void InsertionSort()
  685. {
  686.     BAR barTemp;
  687.     int iRow, iRowTmp, iLength;
  688.  
  689.     // Start at the top.
  690.     for( iRow = 0; iRow < nBar; iRow++ )
  691.     {
  692.         barTemp = abarWork[iRow];
  693.         iLength = barTemp.len;
  694.  
  695.         // As long as the length of the temporary element is greater than
  696.         // the length of the original, keep shifting the elements down.
  697.         //
  698.         for( iRowTmp = iRow; iRowTmp; iRowTmp-- )
  699.         {
  700.             iCompares++;
  701.             if( abarWork[iRowTmp - 1].len > iLength )
  702.             {
  703.                 ++iSwaps;
  704.                 abarWork[iRowTmp] = abarWork[iRowTmp - 1];
  705.                 DrawBar( iRowTmp );         // Print the new bar
  706.                 DrawTime();        // Print the elapsed time
  707.             }
  708.             else                              // Otherwise, exit
  709.                 break;
  710.         }
  711.  
  712.         // Insert the original bar in the temporary position.
  713.         abarWork[iRowTmp] = barTemp;
  714.         DrawBar( iRowTmp );
  715.         DrawTime();
  716.     }
  717. }
  718.  
  719.  
  720. // BubbleSort: BubbleSort cycles through the elements, comparing
  721. // adjacent elements and swapping pairs that are out of order. It
  722. // continues to do this until no out-of-order pairs are found.
  723. //
  724. void BubbleSort()
  725. {
  726.     int iRow, iSwitch, iLimit = nBar-1;
  727.  
  728.     // Move the longest bar down to the bottom until all are in order.
  729.     do
  730.     {
  731.         iSwitch = 0;
  732.         for( iRow = 0; iRow < iLimit; iRow++ )
  733.         {
  734.             // If two adjacent elements are out of order, swap their values
  735.             // and redraw those two bars.
  736.             //
  737.             iCompares++;
  738.             if( abarWork[iRow].len > abarWork[iRow + 1].len )
  739.             {
  740.                 Swaps( &abarWork[iRow], &abarWork[iRow + 1] );
  741.                 SwapBars( iRow, iRow + 1 );
  742.                 iSwitch = iRow;
  743.             }
  744.         }
  745.  
  746.         // Sort on next pass only to where the last switch was made.
  747.         iLimit = iSwitch;
  748.     } while( iSwitch );
  749. }
  750.  
  751.  
  752. /* HeapSort:  HeapSort (also called TreeSort) works by calling
  753.    PercolateUp and PercolateDown. PercolateUp organizes the elements
  754.    into a "heap" or "tree," which has the properties shown below:
  755.  
  756.                               element[1]
  757.                             /            \
  758.                  element[2]                element[3]
  759.                 /          \              /          \
  760.           element[4]     element[5]   element[6]    element[7]
  761.           /        \     /        \   /        \    /        \
  762.          ...      ...   ...      ... ...      ...  ...      ...
  763.  
  764. */
  765. //  Each "parent node" is greater than each of its "child nodes"; for
  766. //  example, element[1] is greater than element[2] or element[3];
  767. //  element[4] is greater than element[5] or element[6], and so forth.
  768. //  Therefore, once the first loop in HeapSort is finished, the
  769. //  largest element is in element[1].
  770. //
  771. //  The second loop rebuilds the heap (with PercolateDown), but starts
  772. //  at the top and works down, moving the largest elements to the bottom.
  773. //  This has the effect of moving the smallest elements to the top and
  774. //  sorting the heap.
  775.  
  776. void HeapSort()
  777. {
  778.     int i;
  779.  
  780.     for( i = 1; i < nBar; i++ )
  781.         PercolateUp( i );
  782.  
  783.     for( i = nBar - 1; i > 0; i-- )
  784.     {
  785.         Swaps( &abarWork[0], &abarWork[i] );
  786.         SwapBars( 0, i );
  787.         PercolateDown( i - 1 );
  788.     }
  789. }
  790.  
  791.  
  792. // PercolateUp: Converts elements into a "heap" with the largest
  793. // element at the top (see the diagram above).
  794.  
  795. void PercolateUp( int iMaxLevel )
  796. {
  797.     int i = iMaxLevel, iParent;
  798.  
  799.     // Move the value in abarWork[iMaxLevel] up the heap until it has
  800.     // reached its proper node (that is, until it is greater than either
  801.     // of its child nodes, or until it has reached 1, the top of the heap).
  802.  
  803.     while( i )
  804.     {
  805.         iParent = i / 2;    // Get the subscript for the parent node
  806.         iCompares++;
  807.         if( abarWork[i].len > abarWork[iParent].len )
  808.         {
  809.             // The value at the current node is bigger than the value at
  810.             // its parent node, so swap these two array elements.
  811.             //
  812.             Swaps( &abarWork[iParent], &abarWork[i] );
  813.             SwapBars( iParent, i );
  814.             i = iParent;
  815.         }
  816.         else
  817.             // Otherwise, the element has reached its proper place in the
  818.             // heap, so exit this procedure.
  819.  
  820.             break;
  821.     }
  822. }
  823.  
  824.  
  825. // PercolateDown: Converts elements to a "heap" with the largest elements
  826. // at the bottom. When this is done to a reversed heap (largest elements
  827. // at top), it has the effect of sorting the elements.
  828. //
  829. void PercolateDown( int iMaxLevel )
  830. {
  831.     int iChild, i = 0;
  832.  
  833.     // Move the value in abarWork[0] down the heap until it has reached
  834.     // its proper node (that is, until it is less than its parent node
  835.     // or until it has reached iMaxLevel, the bottom of the current heap).
  836.  
  837.     while( TRUE )
  838.     {
  839.         // Get the subscript for the child node.
  840.         iChild = 2 * i;
  841.  
  842.         // Reached the bottom of the heap, so exit this procedure.
  843.         if( iChild > iMaxLevel )
  844.             break;
  845.  
  846.         // If there are two child nodes, find out which one is bigger.
  847.         if( iChild + 1 <= iMaxLevel )
  848.         {
  849.             iCompares++;
  850.             if( abarWork[iChild + 1].len > abarWork[iChild].len )
  851.                 iChild++;
  852.         }
  853.  
  854.         iCompares++;
  855.         if( abarWork[i].len < abarWork[iChild].len )
  856.         {
  857.             // Move the value down since it is still not bigger than
  858.             // either one of its children.
  859.  
  860.             Swaps( &abarWork[i], &abarWork[iChild] );
  861.             SwapBars( i, iChild );
  862.             i = iChild;
  863.         }
  864.         else
  865.             // Otherwise, abarWork has been restored to a heap from 1 to
  866.             // iMaxLevel, so exit.
  867.  
  868.             break;
  869.     }
  870. }
  871.  
  872.  
  873. // ExchangeSort: The ExchangeSort compares each element--starting with
  874. // the first--with every following element. If any of the following
  875. // elements is smaller than the current element, it is exchanged with
  876. // the current element and the process is repeated for the next element.
  877. //
  878. void ExchangeSort()
  879. {
  880.     int iRowCur, iRowMin, iRowNext;
  881.  
  882.     for( iRowCur = 0; iRowCur < nBar; iRowCur++ )
  883.     {
  884.         iRowMin = iRowCur;
  885.         for( iRowNext = iRowCur; iRowNext < nBar; iRowNext++ ){
  886.             iCompares++;
  887.             if( abarWork[iRowNext].len < abarWork[iRowMin].len ){
  888.                 iRowMin = iRowNext;
  889.                 DrawTime();
  890.             }
  891.         }
  892.  
  893.         // If a row is shorter than the current row, swap those two
  894.         // array elements.
  895.  
  896.         if( iRowMin > iRowCur ){
  897.             Swaps( &abarWork[iRowCur], &abarWork[iRowMin] );
  898.             SwapBars( iRowCur, iRowMin );
  899.         }
  900.     }
  901. }
  902.  
  903.  
  904. // ShellSort: ShellSort is similar to the BubbleSort. However, it
  905. // begins by comparing elements that are far apart (separated by the
  906. // value of the iOffset variable, which is initially half the distance
  907. // between the first and last element), then comparing elements that
  908. // are closer together. When iOffset is one, the last iteration is
  909. // merely a bubble sort.
  910. //
  911. void ShellSort()
  912. {
  913.     int iOffset, iSwitch, iLimit, iRow;
  914.  
  915.     // Set comparison offset to half the number of bars.
  916.     iOffset = nBar  / 2;
  917.  
  918.     while( iOffset )
  919.     {
  920.         // Loop until offset gets to zero.
  921.         iLimit = nBar - iOffset - 1 ;
  922.         do
  923.         {
  924.             iSwitch = FALSE;     // Assume no switches at this offset.
  925.  
  926.             // Compare elements and switch ones out of order.
  927.             for( iRow = 0; iRow <= iLimit; iRow++ )
  928.             {
  929.                 iCompares++;
  930.                 if( abarWork[iRow].len > abarWork[iRow + iOffset].len )
  931.                 {
  932.                     Swaps( &abarWork[iRow], &abarWork[iRow + iOffset] );
  933.                     SwapBars( iRow, iRow + iOffset );
  934.                     iSwitch = iRow;
  935.                 }
  936.             }
  937.  
  938.             // Sort on next pass only to where last switch was made.
  939.             iLimit = iSwitch - iOffset;
  940.         } while( iSwitch );
  941.  
  942.         // No switches at last offset, try one half as big.
  943.         iOffset = iOffset / 2;
  944.     }
  945. }
  946.  
  947.  
  948. // QuickSort: QuickSort works by picking a random "pivot" element,
  949. // then moving every element that is bigger to one side of the pivot,
  950. // and every element that is smaller to the other side. QuickSort is
  951. // then called recursively with the two subdivisions created by the pivot.
  952. // Once the number of elements in a subdivision reaches two, the recursive
  953. // calls end and the array is sorted.
  954. //
  955. void QuickSort( int iLow, int iHigh )
  956. {
  957.     int iUp, iDown, iBreak;
  958.  
  959.     if( iLow < iHigh )
  960.     {
  961.         // Only two elements in this subdivision; swap them if they are
  962.         // out of order, then end recursive calls.
  963.         //
  964.         if( (iHigh - iLow) == 1 )
  965.         {
  966.             iCompares++;
  967.             if( abarWork[iLow].len > abarWork[iHigh].len )
  968.             {
  969.                 Swaps( &abarWork[iLow], &abarWork[iHigh] );
  970.                 SwapBars( iLow, iHigh );
  971.             }
  972.         }
  973.         else
  974.         {
  975.             iBreak = abarWork[iHigh].len;
  976.             do
  977.             {
  978.                 // Move in from both sides towards the pivot element.
  979.                 iUp = iLow;
  980.                 iDown = iHigh;
  981.                 iCompares++;
  982.                 while( (iUp < iDown) && (abarWork[iUp].len <= iBreak) )
  983.                     iUp++;
  984.                 iCompares++;
  985.                 while( (iDown > iUp) && (abarWork[iDown].len >= iBreak) )
  986.                     iDown--;
  987.                 // If we haven't reached the pivot, it means that two
  988.                 // elements on either side are out of order, so swap them.
  989.                 //
  990.                 if( iUp < iDown )
  991.                 {
  992.                     Swaps( &abarWork[iUp], &abarWork[iDown] );
  993.                     SwapBars( iUp, iDown );
  994.                 }
  995.             } while ( iUp < iDown );
  996.  
  997.             // Move pivot element back to its proper place in the array.
  998.             Swaps( &abarWork[iUp], &abarWork[iHigh] );
  999.             SwapBars( iUp, iHigh );
  1000.  
  1001.             // Recursively call the QuickSort procedure (pass the smaller
  1002.             // subdivision first to use less stack space).
  1003.             //
  1004.             if( (iUp - iLow) < (iHigh - iUp) )
  1005.             {
  1006.                 QuickSort( iLow, iUp - 1 );
  1007.                 QuickSort( iUp + 1, iHigh );
  1008.             }
  1009.             else
  1010.             {
  1011.                 QuickSort( iUp + 1, iHigh );
  1012.                 QuickSort( iLow, iUp - 1 );
  1013.             }
  1014.         }
  1015.     }
  1016. }
  1017.  
  1018.  
  1019.  
  1020. /****************************************************************************
  1021.  
  1022.     FUNCTION: About(HWND, unsigned, WORD, LONG)
  1023.  
  1024.     PURPOSE:  Processes messages for "About" dialog box
  1025.  
  1026.     MESSAGES:
  1027.  
  1028.     WM_INITDIALOG - initialize dialog box
  1029.     WM_COMMAND    - Input received
  1030.  
  1031. ****************************************************************************/
  1032.  
  1033. BOOL FAR PASCAL __export About(hDlg, message, wParam, lParam)
  1034. HWND hDlg;
  1035. unsigned message;
  1036. WORD wParam;
  1037. LONG lParam;
  1038. {
  1039.     switch (message) {
  1040.     case WM_INITDIALOG:
  1041.         return (TRUE);
  1042.  
  1043.     case WM_COMMAND:
  1044.         if (wParam == IDOK
  1045.                 || wParam == IDCANCEL) {
  1046.         EndDialog(hDlg, TRUE);
  1047.         return (TRUE);
  1048.         }
  1049.         break;
  1050.     }
  1051.     return (FALSE);
  1052. }
  1053.  
  1054. /****************************************************************************
  1055.  
  1056.     FUNCTION: Stats(HWND, unsigned, WORD, LONG)
  1057.  
  1058.     PURPOSE:  Processes messages for "Stats" dialog box
  1059.  
  1060.     MESSAGES:
  1061.  
  1062.     WM_INITDIALOG - initialize dialog box
  1063.     WM_COMMAND    - Input received
  1064.  
  1065. ****************************************************************************/
  1066. BOOL FAR PASCAL __export Stats(hDlg, message, wParam, lParam)
  1067. HWND hDlg;
  1068. unsigned message;
  1069. WORD wParam;
  1070. LONG lParam;
  1071. {
  1072.     char temp[10];
  1073.     LPSTR farStr;
  1074.  
  1075.     switch (message) {
  1076.     case WM_INITDIALOG:
  1077.         farStr = (LPSTR) _fmalloc(10);
  1078.         if (Insertion.done) {
  1079.             sprintf(temp,"%2.2f",Insertion.time);
  1080.             _fstrcpy(farStr,(LPSTR)temp);
  1081.             SetDlgItemText(hDlg, ID_I_TIME, farStr);
  1082.             SetDlgItemInt(hDlg, ID_I_SWAP, Insertion.swaps, FALSE);
  1083.             SetDlgItemInt(hDlg, ID_I_COMPARE, Insertion.compares, FALSE);
  1084.         }
  1085.  
  1086.         if (Bubble.done) {
  1087.             sprintf(temp,"%2.2f",Bubble.time);
  1088.             _fstrcpy(farStr,(LPSTR)temp);
  1089.             SetDlgItemText(hDlg, ID_B_TIME, farStr);
  1090.             SetDlgItemInt(hDlg, ID_B_SWAP, Bubble.swaps, FALSE);
  1091.             SetDlgItemInt(hDlg, ID_B_COMPARE, Bubble.compares, FALSE);
  1092.         }
  1093.  
  1094.         if (Heap.done) {
  1095.             sprintf(temp,"%2.2f",Heap.time);
  1096.             _fstrcpy(farStr,(LPSTR)temp);
  1097.             SetDlgItemText(hDlg, ID_H_TIME, farStr);
  1098.             SetDlgItemInt(hDlg, ID_H_SWAP, Heap.swaps, FALSE);
  1099.             SetDlgItemInt(hDlg, ID_H_COMPARE, Heap.compares, FALSE);
  1100.         }
  1101.  
  1102.         if (Exchange.done) {
  1103.             sprintf(temp,"%2.2f",Exchange.time);
  1104.             _fstrcpy(farStr,(LPSTR)temp);
  1105.             SetDlgItemText(hDlg, ID_E_TIME, farStr);
  1106.             SetDlgItemInt(hDlg, ID_E_SWAP, Exchange.swaps, FALSE);
  1107.             SetDlgItemInt(hDlg, ID_E_COMPARE, Exchange.compares, FALSE);
  1108.         }
  1109.  
  1110.  
  1111.         if (Shell.done) {
  1112.             sprintf(temp,"%2.2f",Shell.time);
  1113.             _fstrcpy(farStr,(LPSTR)temp);
  1114.             SetDlgItemText(hDlg, ID_S_TIME, farStr);
  1115.             SetDlgItemInt(hDlg, ID_S_SWAP, Shell.swaps, FALSE);
  1116.             SetDlgItemInt(hDlg, ID_S_COMPARE, Shell.compares, FALSE);
  1117.         }
  1118.  
  1119.         if (Quick.done) {
  1120.             sprintf(temp,"%2.2f",Quick.time);
  1121.             _fstrcpy(farStr,(LPSTR)temp);
  1122.             SetDlgItemText(hDlg, ID_Q_TIME, farStr);
  1123.             SetDlgItemInt(hDlg, ID_Q_SWAP, Quick.swaps, FALSE);
  1124.             SetDlgItemInt(hDlg, ID_Q_COMPARE, Quick.compares, FALSE);
  1125.         }
  1126.  
  1127.         _ffree(farStr);
  1128.  
  1129.         return (TRUE);
  1130.  
  1131.     case WM_COMMAND:
  1132.         if (wParam == IDOK
  1133.                 || wParam == IDCANCEL) {
  1134.         EndDialog(hDlg, TRUE);
  1135.         return (TRUE);
  1136.         }
  1137.         break;
  1138.     }
  1139.     return (FALSE);
  1140. }
  1141.  
  1142.  
  1143. /****************************************************************************
  1144.  
  1145.     FUNCTION: Pause (HWND, unsigned, WORD, LONG)
  1146.  
  1147.     PURPOSE:  Processes messages for "Pause" dialog box
  1148.  
  1149.     MESSAGES:
  1150.  
  1151.     WM_INITDIALOG - initialize dialog box
  1152.     WM_COMMAND    - Input received
  1153.  
  1154. ****************************************************************************/
  1155. BOOL FAR PASCAL __export Pause(hDlg, message, wParam, lParam)
  1156. HWND hDlg;
  1157. unsigned message;
  1158. WORD wParam;
  1159. LONG lParam;
  1160. {
  1161.     char temp[10];
  1162.     LPSTR farStr;
  1163.     static clock_t tmpPause;
  1164.  
  1165.     switch (message) {
  1166.     case WM_INITDIALOG:
  1167.         tmpPause = clPause;
  1168.         farStr = (LPSTR) _fmalloc(10);
  1169.         sprintf(temp,"%3.3u", tmpPause/30);
  1170.         _fstrcpy(farStr,(LPSTR)temp);
  1171.         SetDlgItemText(hDlg, ID_PAUSE, farStr);
  1172.         _ffree(farStr);
  1173.         return (TRUE);
  1174.  
  1175.     case WM_COMMAND:
  1176.         switch (wParam) {
  1177.         case IDOK:
  1178.             clPause = tmpPause;
  1179.             EndDialog(hDlg, TRUE);
  1180.             return (TRUE);
  1181.             break;
  1182.         case IDCANCEL:
  1183.             EndDialog(hDlg, TRUE);
  1184.             return (TRUE);
  1185.             break;
  1186.  
  1187.         case ID_SLOWER:
  1188.             if( tmpPause <= 900L ){
  1189.                 tmpPause += 30L;
  1190.                 farStr = (LPSTR) _fmalloc(10);
  1191.                 sprintf(temp,"%3.3u", tmpPause/30);
  1192.                 _fstrcpy(farStr,(LPSTR)temp);
  1193.                 SetDlgItemText(hDlg, ID_PAUSE, farStr);
  1194.                 _ffree(farStr);
  1195.             }
  1196.             break;
  1197.  
  1198.         case ID_FASTER:
  1199.             if( tmpPause ){
  1200.                 tmpPause -= 30L;
  1201.                 farStr = (LPSTR) _fmalloc(10);
  1202.                 sprintf(temp,"%3.3u", tmpPause/30);
  1203.                 _fstrcpy(farStr,(LPSTR)temp);
  1204.                 SetDlgItemText(hDlg, ID_PAUSE, farStr);
  1205.                 _ffree(farStr);
  1206.             }
  1207.             break;
  1208.         }
  1209.     }
  1210.     return (FALSE);
  1211. }
  1212.