csort.c File Reference

subroutines for sequential or parallel sort and/or merge sets of integer. More...

Go to the source code of this file.

Functions
void	insertion_sort (int *indices, int count)
void	quick_sort (int *indices, int left, int right)
void	bubble_sort (int *indices, int count)
int	counting_sort (int *indices, int count)
void	shell_sort (int *a, int n)
int	ssort (int *indices, int count, int flag)
int	omp_psort_opt (int *A, int nA, int flag)
int	omp_psort (int *A, int nA, int flag)
int	sorted (int *indices, int count)
int	monotony (int *indices, int count)

Detailed Description

subroutines for sequential or parallel sort and/or merge sets of integer.

Note

Copyright (c) 2010-2012 APC CNRS Université Paris Diderot. This program is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, see http://www.gnu.org/licenses/lgpl.html

For more information about ANR MIDAS'09 project see http://www.apc.univ-paris7.fr/APC_CS/Recherche/Adamis/MIDAS09/index.html

ACKNOWLEDGMENT: This work has been supported in part by the French National Research Agency (ANR) through COSINUS program (project MIDAS no. ANR-09-COSI-009).

Author

Pierre Cargemel

Date

April 2012

Definition in file csort.c.

Function Documentation

insertion_sort()

void insertion_sort	(	int *	indices,
		int	count
	)

Insertion sort : complexity is n square; ascending order

Parameters

indices	array of integer
count	number of elements in indices array

Returns

void

Definition at line 32 of file csort.c.

quick_sort()

void quick_sort	(	int *	indices,
		int	left,
		int	right
	)

Quick sort : complexity n square (Average is n log(n)). Sort in ascending order indices between left index and right index. Notice that this algorithm uses recursive calls, and can lead to stack overflow.

Parameters

indices	array of integer
first	element number
last	element number

Returns

void

Definition at line 55 of file csort.c.

bubble_sort()

void bubble_sort	(	int *	indices,
		int	count
	)

Bubble sort : complexity n square

Parameters

indices	array of integer
count	number of elements in indices array

Returns

void

Definition at line 88 of file csort.c.

counting_sort()

int counting_sort	(	int *	indices,
		int	count
	)

Counting sort : sort indices in strictly ascending order (monotony). If the array initially ows reundants elements, they will be merged. Thus the returned number of sorted elements is less than the initial number of elements. Assuming elements belong to [min, max], complexity is n+(max-min+1). Due to allocation, memory overhead is (max-min+1)sizeof(element)

Parameters

indices	array of integer
count	number of elements in indices array

Returns

number of sorted elements

Definition at line 111 of file csort.c.

shell_sort()

void shell_sort	(	int *	a,
		int	n
	)

Shell sort

Parameters

indices	array of integer
count	number of elements in indices array

Returns

void

Definition at line 141 of file csort.c.

ssort()

int ssort	(	int *	indices,
		int	count,
		int	flag
	)

Sort and merge redundant elements of a set of indices using a specified method. The indices tab, initially an arbitrary set of integers, becomes a monotony set. Available methods :

• quick sort
• bubble sort
• insertion sort
• counting sort
• shell sort

Parameters

indices	tab (modified)
count	number of indices
flag	method

Returns

number of sorted elements

Definition at line 172 of file csort.c.

omp_psort_opt()

int omp_psort_opt	(	int *	A,
		int	nA,
		int	flag
	)

Definition at line 210 of file csort.c.

omp_psort()

int omp_psort	(	int *	A,
		int	nA,
		int	flag
	)

Sort and merge redundant elements of a set of indices, using openMP. The indices tab, initially an arbitrary set of integers, becomes a monotony set. Algorithm is diivided in two steps :

• each thread sorts, in parallel, a subpart of the set using a specified method.
• subsets obtained are merged successively in a binary tree manner.

Available methods for the fully parallel step :

• quick sort
• bubble sort
• insertion sort
• counting sort
• shell sort

Parameters

indices	tab (modified)
count	number of elements to sort

Returns

flag method

Definition at line 302 of file csort.c.

sorted()

int sorted	(	int *	indices,
		int	count
	)

=========================Checker Routines=============================================

Definition at line 376 of file csort.c.

monotony()

int monotony	(	int *	indices,
		int	count
	)

Definition at line 388 of file csort.c.