sort in c


  • 0
    F

    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.