quicksort in linux or Unix

发表于 | 更新于: | |


qsort is quicksort function in linux or Unix. The function prototype is

1
void qsort(const void* array, const int number, const size_t sizeof_element,int (*cmp_fun)(const void*,const void*));

maybe I write too many const here:) I will write some examples to sort numbers below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdlib.h>
// in c++ use cstdlib
int cmp(const void * a, const void * b){
	const int *tmp_a = (const int*)a;
	const int *tmp_b = (const int *)b;
	return *tmp_a-*tmp_b; // this is ASCE
} // this is function for comparing two Int type
int main(){
	int array[100],i,flag = 0;
	for(i =0; i <100; i++){
		scanf("%d",&array[i]);	
	}
	qsort(array,100, sizeof(array[0]), cmp);
	// here you can use sizeof(int) instead
	for(i = 0; i < 100; i++){
		if(!flag){
			printf("%d", array[i]);
			flag = 1;
		}
		else{
			printf(" %d", array[i]);
		}
	}
	printf("\n");
	return 0;
}

qsort function will change the content of array. If you want use complex object in qsort. You should just convert const void to object. If you will use point in array, you should compare with objects use tmp_a-tmp_b. If you want to compare double or float type, you should have a look at my another article: compare double numbers in c/c++ language.

If you want a stable compare function, you can use qsort also. First you should construct a class or struct, then and index or other information into struct. And compare when two values are equal.

1
2
3
4
5
6
7
8
9
10
11
12
13
int cmp(const void * a, const void * b){
	const Object *tmp_a = (const Object*)a;
	const Object *tmp_b = (const Object *)b;
	if(tmp_a->value == tmp_b->value){
		if(tmp_a->index < tmp_b->index){
			return -1;
		}
		else{
			return 1;
		}
	}
	return tmp_a->value-tmp_b->value; // this is ASCE
} // this is function for comparing two Int type