宿題のためにJavaで反復クイックソートを実装する必要があります。私はそれについてたくさん検索しましたが、反復クイックソートを実装する方法について明確に説明しているWebサイトを見つけることができませんでした.
私はJavaでこのコードを見つけました。ソートは非常にうまくいきますが、どのように機能するのかわかりません。再帰的なクイックソートがどのように機能するかは知っています。
私は自分の質問でコードにコメントしました
public static void iterativeQsort(int[] arr) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(0);
stack.push(arr.length);
while (!stack.isEmpty()) {
int end = stack.pop();
int start = stack.pop();
if (end - start < 2) continue;
int p = start + ((end-start)/2);
p = partition(arr,p,start,end);
stack.push(p+1);
stack.push(end);
stack.push(start);
stack.push(p);
}
}
private static int partition(int[] arr, int p, int start, int end) {
int l = start;
int h = end - 2; //what is h and l variables for and why h has to be end -2?
int piv = arr[p];
swap(arr,p,end-1);
while (l < h) {
if (arr[l] < piv) {
l++;
} else if (arr[h] >= piv) {
h--;
} else {
swap(arr,l,h);
}
}
int idx = h; // what is idx exactly?
if (arr[h] < piv) idx++;
swap(arr,end-1,idx);
return idx; //why return idx.
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
私はほとんどが分割方法に混乱しています。それが何をするのかわかりません。
誰かが反復クイックソートを作成するための主な手順を説明できれば、私はとても幸せです.
ご協力いただきありがとうございます。