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)
	=========================Checker Routines=============================================
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

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 18 of file csort.c.

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 40 of file csort.c.

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 73 of file csort.c.

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 95 of file csort.c.

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 129 of file csort.c.

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

Definition at line 197 of file csort.c.

int sorted	(	int *	indices,
		int	count
	)

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

Definition at line 364 of file csort.c.

int monotony	(	int *	indices,
		int	count
	)

Definition at line 377 of file csort.c.