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/ifwhile(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);
}
}
Reference
この問題について(QuickSort), 我々は、より多くの情報をここで見つけました
https://velog.io/@camel-man-ims/QuickSort
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
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);
}
}
Reference
この問題について(QuickSort), 我々は、より多くの情報をここで見つけました
https://velog.io/@camel-man-ims/QuickSort
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
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)
}
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);
}
}
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);
}
}
Reference
この問題について(QuickSort), 我々は、より多くの情報をここで見つけました https://velog.io/@camel-man-ims/QuickSortテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol