About me

About

2011-09-29

Código de ordenação em awk.

  • bubble sort

    function bubble_sort(arr, a, b,     i,done,t) {
    i = a
    done = 1
    for (;;) {
    if (i == b) {
    if (done)
    break
    i = a
    done = 1
    }
    if (arr[i] > arr[i+1]) {
    t = arr[i]
    arr[i] = arr[i+1]
    arr[i+1] = t
    done = 0
    }
    i = i+1
    }
    }


    # main
    { x[++n] = substr($0,1) } ## lexical sort
    #{ x[++n] = $0+0 } ## numerical sort
    END { bubble_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }
  • heap sort

    ## works only on arrays indexed [1..n]

    function heap_sort(arr, n, i,t) {
    make_heap(arr, n)
    for (i=n; i>1; i--) {
    t = arr[1]
    arr[1] = arr[i]
    arr[i] = t
    sift_down(arr, i-1, 1)
    }
    }

    function make_heap(arr, n, i) {
    for (i=int(n/2); i>=1; i--)
    sift_down(arr, n, i)
    }

    function sift_down(arr, n, i, k,j,t) {
    k = i
    do {
    j = k
    if (2*j <= n && arr[2*j] > arr[k])
    k = 2*j
    if (2*j < n && arr[2*j+1] > arr[k])
    k = 2*j+1
    t = arr[j]
    arr[j] = arr[k]
    arr[k] = t
    } while (j != k);
    }

    # main
    { x[++n] = substr($0,1) } ## lexical sort
    #{ x[++n] = $0+0 } ## numerical sort
    END { heap_sort(x, n); for (i=1; i<=n; i++) print x[i] }
  • insert sort

    # sorts array ARR[A..B]
    function insert_sort(arr, a, b, i,j,t) {
    for (i=a+1; i<=b; i++) {
    if (arr[i] > arr[i-1])
    continue
    t = arr[i]
    j=i-1
    do
    arr[j+1] = arr[j];
    while (--j>0 && t < arr[j]);
    arr[j+1] = t
    }
    }

    # main
    { x[++n] = substr($0,1) } ## lexical sort
    #{ x[++n] = $0+0 } ## numerical sort
    END { insert_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }
  • merge sort

    function merge_sort(arr, a, b,      k) {
    if (a<b) {
    k = int((a+b)/2)
    merge_sort(arr, a, k)
    merge_sort(arr, k+1, b)
    merge(arr,a,k,b)
    }
    }

    function merge(arr, a, k, b, i,j,p,c) {
    j = i = a
    p = k+1
    while (a <= k && p <= b) {
    if (arr[a] <= arr[p]) {
    c[i++] = arr[a++]
    } else {
    c[i++] = arr[p++]
    }
    }
    while (a <= k) c[i++] = arr[a++]
    while (p <= b) c[i++] = arr[p++]

    while (j<=b) {
    arr[j] = c[j]
    j++
    }
    }

    ## main
    function pr(arr,i,j) { while (i<=j) print arr[i++] }
    { x[++n] = substr($0,1) } ## lexical sort
    #{ x[++n] = $0+0 } ## numerical sort
    END { merge_sort(x, 1, i); pr(x, 1, i); }
  • quick sort

    function quick_sort(arr, a, b,      pivot,i,j,t) {

    if (a >= b)
    return

    if (a+1 == b) {
    if (arr[a] > arr[b]) {
    t = arr[a]
    arr[a] = arr[b]
    arr[b] = t
    }
    return
    }

    pivot = median(arr[a], arr[b], arr[int((a+b)/2)])
    i = a-1;
    j = b+1;
    for (;;) {
    while (arr[++i] < pivot)
    ;
    while (arr[--j] > pivot)
    ;

    if (i>=j)
    break

    t = arr[i]
    arr[i] = arr[j]
    arr[j] = t
    }
    quick_sort(arr, a, i-1)
    quick_sort(arr, i, b)
    }

    function median(a, b, c) {
    if (a<b) {
    if (b<c)
    return c
    if (a<c)
    return c
    return a
    }
    if (a<c)
    return c
    if (b<c)
    return c
    return b
    }

    # main
    { x[++n] = substr($0,1) } ## lexical sort
    #{ x[++n] = $0+0 } ## numerical sort
    END { quick_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }
  • selection sort

    # sorts array ARR[A..B]
    function selection_sort(arr, a, b, i,j,k,t) {
    for (i=a; i<=b; i++) {
    k=i
    for (j=i+1; j<=b; j++) {
    if (arr[k] > arr[j])
    k = j
    }
    if (k != i) {
    t = arr[i]
    arr[i] = arr[k]
    arr[k] = t
    }
    }
    }

    # main
    { x[++n] = substr($0,1) } ## lexical sort
    #{ x[++n] = $0+0 } ## numerical sort
    END { selection_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }

1 comentário: