home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD1.bin / gnu / man / cat3 / qsort.0 < prev    next >
Text File  |  1993-12-07  |  4KB  |  133 lines
  1.  
  2. QSORT(3)                   UNIX Programmer's Manual                   QSORT(3)
  3.  
  4. NNAAMMEE
  5.      qqssoorrtt,, hheeaappssoorrtt - sort functions
  6.  
  7. SSYYNNOOPPSSIISS
  8.      ##iinncclluuddee <<ssttddlliibb..hh>>
  9.  
  10.      _v_o_i_d
  11.      qqssoorrtt(_v_o_i_d _*_b_a_s_e, _s_i_z_e___t _n_m_e_m_b, _s_i_z_e___t _s_i_z_e,
  12.              _i_n_t _(_*_c_o_m_p_a_r_)_(_c_o_n_s_t _v_o_i_d _*_, _c_o_n_s_t _v_o_i_d _*_))
  13.  
  14.      _i_n_t
  15.      hheeaappssoorrtt(_v_o_i_d _*_b_a_s_e, _s_i_z_e___t _n_m_e_m_b, _s_i_z_e___t _s_i_z_e,
  16.              _i_n_t _(_*_c_o_m_p_a_r_)_(_c_o_n_s_t _v_o_i_d _*_, _c_o_n_s_t _v_o_i_d _*_))
  17.  
  18. DDEESSCCRRIIPPTTIIOONN
  19.      The qqssoorrtt() function is a modified partition­exchange sort, or quicksort.
  20.      The hheeaappssoorrtt() function is a modified selection sort.
  21.  
  22.      The qqssoorrtt() and hheeaappssoorrtt() functions sort an array of _n_m_e_m_b objects, the
  23.      initial member of which is pointed to by _b_a_s_e. The size of each object is
  24.      specified by _s_i_z_e.
  25.  
  26.      The contents of the array are sorted in ascending order according to a
  27.      comparison function pointed to by _c_o_m_p_a_r, which is called with two argu­
  28.      ments that point to the objects being compared.
  29.  
  30.      The comparison function must return an integer less than, equal to, or
  31.      greater than zero if the first argument is considered to be respectively
  32.      less than, equal to, or greater than the second.
  33.  
  34.      The functions qqssoorrtt() and hheeaappssoorrtt() are _n_o_t stable, that is, if two mem­
  35.      bers compare as equal, their order in the sorted array is undefined.
  36.  
  37.      The qqssoorrtt() function is an implementation of C.A.R. Hoare's ``quicksort''
  38.      algorithm, a variant of partition­exchange sorting; in particular, see
  39.      D.E. Knuth's Algorithm Q.  QQssoorrtt() takes O N lg N average time.  This im­
  40.      plementation uses median selection to avoid the traditional O N**2 worst­
  41.      case behavior.
  42.  
  43.      The hheeaappssoorrtt() function is an implementation of J.W.J. William's ``heap­
  44.      sort'' algorithm, a variant of selection sorting; in particular, see D.E.
  45.      Knuth's Algorithm H.  HHeeaappssoorrtt() takes O N lg N worst­case time.  Its
  46.      _o_n_l_y advantage over qqssoorrtt() is that it uses no additional memory.
  47.  
  48. RREETTUURRNN VVAALLUUEESS
  49.      The qqssoorrtt() function returns no value.
  50.  
  51.      Upon successful completion, hheeaappssoorrtt() returns 0.  Otherwise, it returns
  52.      -1 and the global variable _e_r_r_n_o is set to indicate the error.
  53.  
  54. EERRRROORRSS
  55.      The hheeaappssoorrtt() function succeeds unless:
  56.  
  57.      [EINVAL]      The _s_i_z_e argument is zero.
  58.  
  59. CCOOMMPPAATTIIBBIILLIITTYY
  60.      Previous versions of qqssoorrtt() did not permit the comparison routine to it­
  61.      self call qqssoorrtt(_3).  This is no longer true.
  62.  
  63. SSEEEE AALLSSOO
  64.      sort(1),  radixsort(3)
  65.  
  66.  
  67.      Hoare, C.A.R., "Quicksort", _T_h_e _C_o_m_p_u_t_e_r _J_o_u_r_n_a_l, 5:1, pp. 10­15, 1962.
  68.  
  69.      Williams, J.W.J, "Heapsort", _C_o_m_m_u_n_i_c_a_t_i_o_n_s _o_f _t_h_e _A_C_M, 7:1, pp. 347­348,
  70.      1964.
  71.  
  72.      Knuth, D.E., "Sorting and Searching", _T_h_e _A_r_t _o_f _C_o_m_p_u_t_e_r _P_r_o_g_r_a_m_m_i_n_g,
  73.      Vol. 3, pp. 114­123, 145­149, 1968.
  74.  
  75. SSTTAANNDDAARRDDSS
  76.      The qqssoorrtt() function conforms to ANSI C3.159­1989 (``ANSI C'').
  77.  
  78. BSD Experimental                 June 29, 1991                               2
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.