クイックソート
今クイックソートのプログラム作成をしていますが、分からない箇所が幾つかあります。下は、作成した時のプログラムリストです。
class QuickSort{
static int compare = 0;
static int copy = 0;
static int swap = 0;
static void swap(int a[], int i, int j){
int tmp;
tmp = a[i];copy++;
a[i] = a[j];copy++;
a[j] = tmp;copy++;
swap++;}
static void showArray(int a[], int l, int r){//配列の内容を表示するメソッドで、動作:部分配列a[l]～a[r]の要素を表示。これが分かりません。
int a[l] = {1,2,3,4,5,6,7,8,9,10};
int a[r] = {11,12,13,14,15,16,17,18,19,20};}
static void initArray(int a[], int N){
int i;
a[0]=0;
for(i=1;i<N;i++) a[i] = i;
for(i=1;i<N;i++){
int j,k;
j = (int)(java.lang.Math.random()*(N-1)) + 1;
k = (int)(java.lang.Math.random()*(N-1)) + 1;
swap(a,j,k);}}
public static void (int a[],int l, int r) {
if (r+1-l <= 1)
return;
int e = (l+r+1)/2;
int c = 0;
return a[c];
}
static int partition(int a[], int l, int r, int pivot){// 配列の分割を行うメソッドです。そのあと分割に要した比較回数(=iの増加分+jの減少分)を変数compareに加算し、iの値を戻り値として返さないといけませんが、そこんとこが分かりません。
while (true) {
while (a[l] < pivot)
l = l + 1;
while (a[r] >= pivot)
r = r - 1;
if (l > r)
return l;
swap(a, l, r);
}
}
static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
int i=0;
int j=0;
return i;
}
static void quicksort(int[] a, int l, int r){//(カットオフなしで)再帰的にクイックソートを行うメソッドです。paritionメソッドを用い、a[l]～a[r]を分割値a[r]で分割するのが条件ですが、ここも全然分かりません。
if(l < r){
int i = l;
int j = r;
int x = a[(i+j)/2];
do{
while(a[i]<x) i++;
while(a[j]>x) j--;
if(i<=j)
{
swap(a,i,j);
i++;
j--;
}
}while(i<=j);
quickort(a,l,j);
quicksort(a,i,r);
}
}
static void swap(int[] a, int s, int t){
int temp = a[s];
a[s] = a[t];
a[t] = temp;
return;
int i,pivot;
}
public static void main(String args[]){
//上で作ったメソッドを用いて、ソート過程を表示しながらクイックソートを実行
//手順は次のようになる。
1.要素を(20個もつ)整数型配列aを宣言
2.整数型変数Nに配列aの要素数を保存
3.initArrayメソッドを用いて配列aを初期化
4.showArrayメソッドを用いてソート前の配列aの内容を表示
5.変数compare,copyの値を0に初期化
6.quickSortメソッドを用いて配列aを選択ソート
7.showArrayメソッドを用いてソート後の配列aの内容を表示
8.ソートにかかった比較・コピーの回数を表示
//これも分かりません。
}
分かる人がいましたら教えて下さい。お願いします。
お礼
ありがとうございました． ためしてみます．