1
먼저, 숙제라고 말하고 싶습니다.중복이있는 int의 이진 파일을 사용하는 퀵 소트. 재귀에 문제가 있음
종종 우리는 과제를 끝내고 질문을 게시 할 것이며 과제를 계속하기 위해 계속 노력하고 싶지만이 경우에는 난처하게됩니다!
우리는 file.seek, file.read 및 file.write 명령 만 사용하여 이진 파일을 사용하여 퀵 포트를 구현해야합니다. 이것은 정수의 2 진 파일입니다.
피벗의 "하위 트리"에서 함수를 호출하는 재귀 부분입니다. 저는이 웹 사이트에 올린 알고리즘을 따르고 있습니다 : http://xoax.net/comp_sci/crs/algorithms/lessons/Lesson4/ 그리고 이진 파일 구현을위한 의사 코드로 코드 예제를 사용해 왔습니다.
여기 내 코드입니다 :
//Algorithm and code example used:
void manage(fstream & file , int lindex , int fSize){
//Chunks of 1 or 0 do not need sorting
if(fSize <= 1)
return;
//Choose point in file as "pivot." Pivot is a value.
//pp is the index of "pivot"
int pp = (rand() % fSize) + lindex;
file.seekp(pp * sizeof(int) , file.beg);
int pivot;
file.read((char*)&pivot , sizeof(int));
//Choose "indices" to be swapped. These will be used in seekp
int leftIndex = lindex;
int rightIndex = fSize - 1;
//Swap val , swap val, temp storage, swap index 1 , swap index 2
int leftSwap , rightSwap , temp , tempI1 , tempI2 = 0;
//Dummy indecies to help with tracking partitions.
int dumL = leftIndex;
int dumR = rightIndex;
while(dumL < dumR){
//Move to left index from the file beginning.
file.seekp(dumL * sizeof(int) , file.beg);
do{
tempI1 = file.tellp()/sizeof(int);
dumL = tempI1;
file.read((char*)&temp , sizeof(int));
}
while(temp < pivot);
leftSwap = temp;
//Move to right index.
file.seekp(dumR * sizeof(int) , file.beg);
int n = 1;
do{
tempI2 = file.tellp()/sizeof(int);
dumR = tempI2;
file.read((char*)&temp , sizeof(int));
file.seekp((rightIndex - n) * sizeof(int) , file.beg);
n++;
}
while(temp > pivot);
rightSwap = temp;
//Swap values
int hold = 0;
if(leftSwap == rightSwap && rightSwap == pivot)
break;
file.seekp(tempI1 * sizeof(int) , file.beg);
file.read((char*)&hold , sizeof(int));
file.seekp(tempI1 * sizeof(int) , file.beg);
file.write((char*)&rightSwap , sizeof(int));
file.seekp(tempI2 * sizeof(int) , file.beg);
file.write((char*)&leftSwap , sizeof(int));
}
cout << "pp: " << pp << endl;
cout << "dumL: " << dumL << endl;
cout << "dumR: " << dumR << endl << endl;
//cout << "Lmanage: \n\t Lindex: 0\n\tSize: " << dumL << endl;
manage(file , 0 , dumL);
//cout << "Rmanage: \n\t Lindex: " << dumL + 1 << "\n\tSize: " << fSize - dumL - 1 << endl;
manage(file , dumL + 1 , fSize - (dumL - leftIndex) - 1);
}
void quicksort(fstream & file , int iSize){
srand((unsigned int) time(0));
manage(file , 0 , iSize);
}
int main(int argc, char* argv[]){
if(argc != 2){
cout << "Invalid number of arguments.\n";
return -1;
}
fstream file;
int x = 0;
file.open(argv[1] , ios::binary | ios::out | ios::in);
//Calculate number of ints in file.
file.seekg(0 , file.end);
int size = file.tellg()/sizeof(int);
cout << "size: " << size << endl;
quicksort(file , size);
return 0;
}
"인수"가능한 중복 100 개 정수를 포함하는 바이너리 파일입니다. 문제는 첫 번째 1/4를 정렬하는 것으로 보이지만 색인 생성이 섞여서 "크기"인수가 부정적이된다는 것입니다.
편집 : 내 메인이 추가되었으며 설명이 변경되어 업데이트되었습니다.
는 우선, 각 재귀 층으로 RNG 시드 중지합니다. 'srand()'는 프로그램 시작에 있어야합니다; 아무데도. 둘째, 빠른 정렬 구현에서 자주 발생하는 실수는 하위 시퀀스로 재귀 할 때 배치 된 피벗 슬롯을 건너 뛰지 않는 것입니다. 똑같은 실수를 저 지르지 않도록 코드를주의 깊게 살펴보십시오. 피벗은 되풀이되는 서브 시퀀스 중 하나 *에 포함되어서는 안됩니다. – WhozCraig
또한, 파일 이름을'manage()'에 넘겨서는 안됩니다. 열린 fstream 참조를 전달한다. 해당 파일 핸들을 모두 열 필요는 없으며 공유에 문제가있을 것입니다. – WhozCraig
나는 그것을 생각하고 처음에는했지만, 나는 내가 이해하지 못했던 커다란 오류를 얻었습니다. 나는 열린 파일을 인수로 전달할 수 없다고 생각했다. – Joshua