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] }
2011-09-29
Código de ordenação em awk.
Subscrever:
Enviar feedback (Atom)
Falta-me fazer o shell sort para completar a colecção.
ResponderEliminar