QuickSort

19801 ワード

idea


見逃さなければ、大きいのと小さいのを取り替える->大きいのと小さいのを分ける.だから左右を繰り返す.
左から大男、右から小男を探す.indexが一致しない場合は、ソートされていることを示しますので、こいつの値とpivot値を変えることができます.

紛らわしい場所


1. quickfunctionの戻り値がarrayかvoidかが混同されている.mainがvoid quickにdataarrayを渡すと,データの値が変化するか否かが混同される.
   public static void main(String args[]){
        int[] data = {3,2};

        test(data,232,433);
        System.out.println(data[0] + " " + data[1]);
    }

    static void test(int[] data,int a,int b){
        data[0] = a;
        data[1] = b;
    }
-->変更.arrayとmethodを混同しなければ当然です
2. ていし
3 5 2 1 6
->大きいやつ、->5、小さいやつ2を見つけたら、止まらなければなりません.どうやって止めますか.スタックを使って止めるべきだと思いますが、複雑になり、仕事ができません.その理由はfor loopだけを使って実現したいからです.for loopは1つの変数に対してのみ条件を表示し、while loopの他の変数の増減も条件に影響します.
ex) While data[left]<= data[pivot]
          left++
3. なぜstartとend値が必要なのか、なぜ書かれていないのか、コードを書くときにstartとend値が再帰を使用する必要があることに気づきました.設計->首都コード->コード実装では,設計段階の記述が不正確な原因と考えられる.

while / if


4. while/if
while(i<N)
i++
上記のようなwhile loopがある場合は、iをN未満と解釈するだけでよい.
iがNより大きいとは言えないi>N
iがNより大きい場合は、iがNより小さい場合にのみ移動できます.while loopはいつ回るかを明記した条件の位置です.
ex)
while(i<10)
i++
--> i가 10보다 클때까지 i을 키우고 싶다. 
그러므로 i가 10보다 작을 때까지만 돌려라
つまりwhileは言語の解釈とは逆で、逆に考えます.逆にifは直訳です.
if(i>10)
i++
--> i가 10보다 크다면. ( 직역 )
While->10より大きく回転させたい:反対に
while(i<10)
5. 数学のようにpseudo codeを記述し,経過した解に自信を確保すべきである.
if N condition  <-- 일정 수준 이상의 값만 받는다
 while M condition <-- sort 해준다
  while J condition <-- 최대값을 추출해준다
   function X() <-- 값을 섞어준다
      --> [this turn]
上記のようにコードを記述する際に矢印方向に記述する場合、現在のコードを記述する順序では、上記の手順が完了してコードが記述されていると仮定すべきである.また、何か変な点があれば検証するので、機能に従って整理します.
6. while loop,for loopは基本的に偽物だと退出します.まだよくないうちに回り続けます.
while (data[pivot] > data[left] && left <= end) {
    left++;
}
while (data[pivot] < data[right] && right > pivot) {
    right--;
}
コードは最初はこのように記述されていたが,同じ値を入力すると虚偽の状況が発生しないためloopから飛び出すことができなかった.だから=を加えます.

pseudo code





DevC++はpseudo code場として非常に適している.PlasticCodeWrapのテーマはいいですね.
quick(array data, int start, int end) {
	
	if(start>=end)
		return ;
	
Define left,right,temp,pivot

left=start+1
right=end
pivot=start

while left<right 
	while data[left] <= data[pivot] (A1)
		left++
	while data[right] >= data[pivot] (A2)
		right++
	if(left<right)
		switch data[left] data[right]
	else
		switch data[left] data[pivot]

Recurse quick(data,start,right-1)
Recurse quick(data,right+1,end)
	
}
-->A 1,A 2の位置にはleftstartのような増減条件文の内容は書かれていない.また、リクルートは初期に終了条件を指定しないと無限ループになることを覚えておいてください.

Code

package SortSeries;

public class QuickSortTry2 {
    public static void main(String args[]) {
        int[] data = {4, 112,23, 2412, 23, 43, 5, 7};
        quick(data, 0, data.length-1);
        for(int i:data){
            System.out.print(i + " ");
        }
    }

    static void quick(int data[], int start, int end) {

        if(start>=end){
            return ;
        }
        int left, right, temp, pivot;

        left = start + 1;
        right = end;
        pivot = start;

        while (left <= right) {
            while (data[pivot] >= data[left] && left <= end) {
                left++;
            }
            while (data[pivot] <= data[right] && right > pivot) {
                right--;
            }
            if (left < right) {
                temp = data[left];
                data[left]=data[right];
                data[right]=temp;
            }else{
                temp = data[pivot];
                data[pivot] = data[right];
                data[right] = temp;
            }
        }
        quick(data,start,right-1);
        quick(data,right+1,end);
    }
}