글
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 | #include <iostream> #include <ctime> using namespace std; void swap(int& a, int& b){ int temp; temp = a; a = b; b = temp; } class Sort{ int NumOfElements; int* elements; void makeNum(int Num){ cout<<"생성된 데이터 :"; for(int i = 0; i<Num; i++){ *(elements+i)=rand()%100; cout<<*(elements+i)<< ' '; } cout<<endl; } public: Sort(int NumOfElements){ this->NumOfElements = NumOfElements; elements = new int[NumOfElements]; makeNum(NumOfElements); } Sort(){ cout<<"자료의 개수를 입력해주세요:"; cin>>NumOfElements; elements = new int[NumOfElements]; makeNum(NumOfElements); } void display(){ for(int i = 0; i<NumOfElements; i++){ cout<<*(elements+i)<< ' '; } cout<<endl; } ~Sort(){ if(elements != NULL) delete[] elements; elements = NULL; } void smallest_select(){ int smallest = elements[0]; int i; for(i = 1; i<NumOfElements; i++){ if( elements[i] < smallest ) smallest = elements[i]; } cout<<"가장 작은 값은"<<smallest<<"입니다"<<endl; } void large_select(){ if(elements == NULL){ cout<<"자료가 없습니다"; return; } int largest=0; int temp = 0; int i,j; for(i = NumOfElements-1; i>=0; i--){ //자료형이 0번 방부터 시작함을 유의 largest=i; for(j = i-1 ; j>=0; j--){ if(elements[j] > elements[largest]) largest=j; } if(i != largest ){ swap(elements[i], elements[largest]); cout<<i<<"번째 자료 "<<elements[i]<<"와 "<<largest<<"번째 데이터"<<elements[largest]<<" Exchange"<<endl; display(); } } } void quick_sort(){ _quick_sort(0, NumOfElements-1); } void _quick_sort(int _left, int _right){ if( _left >= _right ) return; int pivot = elements[_left]; //cout<<"Pivot"<<pivot<<endl; display(); int left_index = _left, right_index=_right+1; do{ do{ left_index++; cout<<"left_index:"<<left_index<<" left_index 값:"<<elements[left_index]<<endl; }while( (elements[left_index] < pivot)&&(left_index <= _right)); do{ right_index--; cout<<"right_index:"<<right_index<<" right_index 값:"<<elements[right_index]<<endl; }while( (elements[right_index] > pivot)&&(right_index >= _left+1) ); if(left_index<right_index){ cout<<"피벗보다 큰"<<elements[left_index]<<"값과 피벗보다 작은"<<elements[right_index]<<"값을 교환"<<endl; swap(elements[left_index],elements[right_index]); } //교차점근처서 바꾸고 나서, 다시 값이 바뀔수 있다 //위의 left_index++와 right_index--를 거쳐야 교차를 한다. //그런데 이 검사를 밑 while에서 하므로 if문으로 확인해줘야한다. }while(left_index<right_index); cout<<"[Pivot]:"<<elements[_left]<<"와"<<elements[right_index]<<"를 교환"<<endl; swap(elements[_left],elements[right_index]); //피벗과 교환 display(); if(_left<right_index-1){ cout<<"재귀함수 호출... 인덱스"<<_left<<"에서 인덱스"<<right_index-1<<"까지 재귀함수 호출"<<endl; _quick_sort(_left, right_index-1); } if(right_index+1<_right){ cout<<"재귀함수 호출... 인덱스"<<right_index+1<<"에서 인덱스"<<_right<<"까지 재귀함수 호출"<<endl; _quick_sort(right_index+1, _right); } }//void _quick_sort }; void main(){ srand(time(0)); Sort* s = new Sort; //s->large_select(); s->quick_sort(); cout<<"====================최종 결과:======================="<<endl; s->display(); delete s;1 } |
