Loading...
Searching...
No Matches
smoothsort.c File Reference

Smoothsort implementation. More...

`#include <stdlib.h>`
`#include <sofia-sip/su_config.h>`
`#include "config.h"`
`#include <sofia-sip/heap.h>`
`#include <assert.h>`
`#include <stdio.h>`
`#include <sys/types.h>`
Include dependency graph for smoothsort.c:

## Data Structures

struct | stretch
| Description of current stretch. More...
struct | array
| Description of array. More...

## Functions

void | su_smoothsort (void *base, size_t r, size_t N, int(*less)(void *m, size_t a, size_t b), void(*swap)(void *m, size_t a, size_t b))
| Sort array using smoothsort.

## Detailed Description

Smoothsort implementation.

Smoothsort is a in-place sorting algorithm with performance of O(NlogN) in worst case and O(n) in best case.

See also
  "Smoothsort, an alternative for sorting in-situ", E.D. Dijkstra, EWD796a, <http://www.enterag.ch/hartwig/order/smoothsort.pdf&gt;.

Author
  Pekka Pessi Pekka.nosp@m..Pes.nosp@m.si@no.nosp@m.kia..nosp@m.com

## Function Documentation

## su_smoothsort()

void su_smoothsort | ( | void * | base,
|  | size_t | r,
|  | size_t | N,
|  | int(* | less )(void *m, size_t a, size_t b),
|  | void(* | swap )(void *m, size_t a, size_t b) )

Sort array using smoothsort.

Sort N elements from array base starting with index r with smoothsort.

Parameters

  base | pointer to array
  r | lowest index to sort
  N | number of elements to sort
  less | comparison function returning nonzero if m[a] < m[b]
  swap | swapper function exchanging elements m[a] and m[b]

Sofia-SIP 1.12.11devel - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.