Monthly Archives: Ноябрь 2014

Реализация на GCC 4.9.1 сортировки кучей (пирамидальная сортировка). У сортировки кучей два больших достоинства:

1. В худшем случае работает за O(n * log n)
2. Не требует дополнительной памяти

Реализация:

#include
//получить индекс левого потомка
int left(int i){
	return i * 2 + 1;
}

//получить индекс правого потомка
int right(int i){
	return i * 2 + 2;
}

//поменять местами два элемента массива
int swap(int *a,int i,int j){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

//вывести на экран массив
void print(int *a,int size){
	int i;
	for(i=0;i=0;i--){
		heapify(a,size,i);
	}
}

//сортировка кучей
void heapSort(int *a,int size){
	buildHeap(a,size);
//	printf("build\n");
//	print(a,size);
	while(--size > 0){
		swap(a,0,size);
		heapify(a,size,0);		
	}
}

int main(){	
	const int N = 9;
	int arr[9] = {1,6,3,5,9,4,2,8,7};
	print(arr,N);//вывести на экран исходный массив
	heapSort(arr,N);//сортировка кучей
	printf("=============\n");
	print(arr,N);//вывод отсортированного массива	
	return 0;
}

В результате исходный массив (1 6 3 5 9 4 2 8 7) будет отсортирован (1 2 3 4 5 6 7 8 9).