next up previous contents index
: ヒープソート : 整列:ソート : 計算量の解析   目次   索引


プログラムリスト

バブルソートのプログラム sort.rr は次の二つの関数 bubleSorttestBuble からなる.

def bubleSort(AnArray) {
  Size = size(AnArray)[0];
  for (J=Size-1; J>0; J--) {
    for (I=0; I<J; I++) {
      if (AnArray[I] > AnArray[I+1]) {
        Tmp = AnArray[I+1];
        AnArray[I+1] = AnArray[I];
        AnArray[I] = Tmp;
      }
    }
  }
}

def testBuble(N) {
  A = newvect(N);
  for (I=0; I<N; I++) {
    A[I] = random() % 100;
  }
  /* print(A); */
  tstart();
  bubleSort(A);
  tstop();
  /* print(A); */
}
end$

クイックソートのプログラム sort2.rr は次の二つの関数 quickSorttestQuick からなる.

def quickSort(A,P,Q) {
   if (Q-P < 1) return;
   Mp = idiv(P+Q,2);
   M = A[Mp];
   B = P; E = Q;
   while (1) {
     while (A[B] < M) B++;
     while (A[E] > M && B <= E) E--;
     if (B >= E) break;
     else {
       Tmp = A[B];
       A[B] = A[E];
       A[E] = Tmp;
       E--;
     }
  }
  if (E < P) E = P;
  quickSort(A,P,E);
  quickSort(A,E+1,Q);
}

def testQuick(N) {
  A = newvect(N);
  for (I=0; I<N; I++) {
    A[I] = random() % 100;
  }
  /* print(A);*/
  tstart();
  quickSort(A,0,N-1);
  tstop();
  /* print(A); */
}
end$



Nobuki Takayama 平成15年9月12日