Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdio.h"
- #include "math.h"
- #include "stdbool.h"
- // IntroSort(data, size, set, swap, bigger, bigoreq)
- // bool(*bigoreq)(void*, void*)
- // bool(*bigger)(void*, void*)
- // void(*swap)(void*, void*)
- // void(*set)(void*, void*)
- void InsertionSort(int* data, int count, void(*swap)(void*, void*), bool(*bigger)(void*, void*)) {
- for (int i = 1; i < count; ++i){
- int j = i;
- while (j > 0){
- if (bigger( &data[j - 1], &data[j])){
- swap(&data[j], &data[j - 1]);
- --j;
- }
- else{
- break;
- }
- }
- }
- }
- void MaxHeapify(int* data, int heapSize, int index, void(*swap)(void*, void*), bool(*bigger)(void*, void*)) {
- int left = (index + 1) * 2 - 1;
- int right = (index + 1) * 2;
- int largest = 0;
- if (left < heapSize && bigger(&data[left], &data[index]) ){
- largest = left;
- }
- else{
- largest = index;
- }
- if (right < heapSize && bigger(&data[right], &data[largest])){
- largest = right;
- }
- if (largest != index){
- swap(&data[index], &data[largest]);
- MaxHeapify(data, heapSize, largest, swap, bigger);
- }
- }
- void HeapSort(int* data, int count, void(*swap)(void*, void*), bool(*bigger)(void*, void*)) {
- int heapSize = count;
- for (int p = (heapSize - 1) / 2; p >= 0; --p){
- MaxHeapify(data, heapSize, p, swap, bigger);
- }
- for (int i = count - 1; i > 0; --i) {
- swap(&data[i], &data[0]);
- --heapSize;
- MaxHeapify(data, heapSize, 0, swap, bigger);
- }
- }
- int Partition(int* data, int left, int right, void(*set)(void*, void*), void(*swap)(void*, void*), bool(*bigoreq)(void*, void*)) {
- void *pivot = &data[right];
- int i = left;
- for (int j = left; j < right; ++j){
- if ( bigoreq(pivot, &data[j])){
- swap(&data[j], &data[i]);
- i++;
- }
- }
- set(&data[right], &data[i]);
- set(&data[i], pivot);
- return i;
- }
- void QuickSortRecursive(int* data, int left, int right, void(*set)(void*, void*), void(*swap)(void*, void*), bool(*bigoreq)(void*, void*)){
- if (left < right){
- int q = Partition(data, left, right, set, swap, bigoreq);
- QuickSortRecursive(data, left, q - 1, set, swap, bigoreq);
- QuickSortRecursive(data, q + 1, right, set, swap, bigoreq);
- }
- }
- void IntroSort(void* data, int count, void(*set)(void*, void*), void(*swap)(void*, void*), bool(*bigger)(void*, void*), bool(*bigoreq)(void*, void*)) {
- int partitionSize = Partition(data, 0, count - 1, set, swap, bigoreq);
- if (partitionSize < 16) {
- InsertionSort(data, count, swap, bigoreq);
- }
- else if (partitionSize >(2 * log(count))){
- HeapSort(data, count, swap, bigger);
- }
- else{
- QuickSortRecursive(data, 0, count - 1, set, swap, bigoreq);
- }
- }
- void set(void* a, void* b){
- *(int*)a = *(int*)b;
- }
- void swap(void* a, void* b){
- int temp = *(int*)a;
- *(int*)a = *(int*)b;
- *(int*)b = temp;
- }
- bool bigger(void* a, void* b){
- return *(int*)a > *(int*)b;
- }
- bool bigoreq(void* a, void* b){
- return *(int*)a >= *(int*)b;
- }
- void print_array(int *data, int size){
- for (int i = 0; i < size; i++){
- printf("%d, ", data[i]);
- }
- printf("\n");
- }
- int main(){
- int data[] = { -1, 25, -58964, 8547, -119, 0, 78596 };
- IntroSort(data, 7, set, swap, bigger, bigoreq);
- print_array((void*)data, sizeof(data) / sizeof(data[0]));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement