su 1.12.11devel
Loading...
Searching...
No Matches
Data Structures | Functions
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(*)(void *m, size_t a, size_t b)  less,
void(*)(void *m, size_t a, size_t b)  swap 
)

Sort array using smoothsort.

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

Parameters
basepointer to array
rlowest index to sort
Nnumber of elements to sort
lesscomparison function returning nonzero if m[a] < m[b]
swapswapper 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.