using sort in c


  • 0
    F

    using kinds of sort in c

    static void
    merge(int *a, int *b, int start, int end) {
        int mid = (start+end)/2;
        int i=start, j=mid+1, k=start;
    
        while (i<=mid && j<=end) {
            if (a[j] >= a[i]) {
                b[k++] = a[i++];
            } else {
                b[k++] = a[j++];
            }
        }
        while (i<=mid) {
            b[k++] = a[i++];
        }
    
        while (j<=end) {
            b[k++] = a[j++];
        }
    
        for (i=start; i<=end; i++) {
            a[i] = b[i];
        }
    }
    
    static void
    split(int *a, int *b, int start, int end) {
        int mid;
    
        if (start >= end) {
            return;
        }
    
        mid = (start+end)/2;
        split(a, b, start, mid);
        split(a, b, mid+1, end);
        merge(a, b, start, end);
    }
    
    void
    merge_sort(int *a, int *b, int n) {
        int start=0, mid, end=n-1;
    
        split(a, b, start, end);
    }
    
    static void
    heap_adjust(int *a, int n, int p) {
        int child, temp;
    
        if (p > n/2-1) {
            return;
        }
        child = 2*p+1;
        if (child+1<n && a[child]<a[child+1])
            child++;
        
        if (a[p] < a[child]) {
            temp = a[p];
            a[p] = a[child];
            a[child] = temp;
        }
        heap_adjust(a, n, child);
    }
    
    void
    heap_sort(int *a, int n) {
        int i;
    
        for (i=n/2-1; i>=0; i--) {
            heap_adjust(a, n, i);
        }
    
        for (i=n-1; i>0; i--) {
            a[i] = a[i]^a[0];
            a[0] = a[i]^a[0];
            a[i] = a[i]^a[0];
    
            heap_adjust(a, i, 0);
        }
    }
    
    void
    fast_sort(int *a, int start, int end) {
        int i, j, key, temp;
    
        if (start >= end) {
            return;
        }
    
        key = a[start];
        i = start;
        j = end;
    
        while (i<j) {
            while (j>i) {
                if (a[j] < key) break;
                j--;
            }
    
            while (i<j) {
                if (a[i] > key) break;
                i++;
            }
    
            if (i != j) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        a[start] = a[i];
        a[i] = key;
    
        fast_sort(a, start, i-1);
        fast_sort(a, i+1, end);
    }
    
    void
    insert_sort(int *a, int n) {
        int i, j, temp;
    
        for (j=1; j<n; j++) {
            for (i=j; i>0; i--) {
                if (a[i-1] > a[i]) {
                    temp = a[i-1];
                    a[i-1] = a[i];
                    a[i] = temp;
                }
            }
        }
    }
    
    int kthSmallest(int** matrix, int matrixRowSize, int matrixColSize, int k) {
        int i, j, index = 0, res;
    
        int *a = (int *)malloc(sizeof(int)*matrixRowSize*matrixColSize);
        int *b = (int *)malloc(sizeof(int)*matrixRowSize*matrixColSize);
    
        for(i=0; i<matrixRowSize; i++) {
            for(j=0; j<matrixColSize; j++) {
                a[index++] = matrix[i][j];
            }
        }
    
        //insert_sort(a, matrixRowSize*matrixColSize);
        merge_sort(a, b, matrixRowSize*matrixColSize);
        //heap_sort(a, matrixRowSize*matrixColSize);
        //fast_sort(a, 0, matrixRowSize*matrixColSize-1);
    
        res = a[k-1];
        free(a);
        free(b);
    
        return res;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.