If input is 8999 the next biggest number is 9899.
If input is 14562 the next biggest number is 14625.
using namespace std;
//SWAP 2 CHARACTERS
void swap(char* ch1, char* ch2)
{
char t;
t = *ch1;
*ch1 = *ch2;
*ch2 = t;
}
//USED IN QUICK SORT FOR SORTING AROUND THE PIVOT
int partition(char* ptr, int low, int high)
{
char key = ptr[low];
int i = low+1;
int j = high;
while(high > i && ptr[i] <= key)i++;
while(ptr[j] > key) j--;
if(i < j)
{
swap(ptr[i],ptr[j]);
}
else
{
swap(ptr[j],ptr[low]);
}
return j;
}
//RECURSSIVE QUICK SORT
void quicksort(char * ptr, int low, int high)
{
if( high > low)
{
int idx = partition(ptr,low,high);
quicksort(ptr,low,idx-1);
quicksort(ptr,idx+1,high);
}
}
//NEXT BIGGEST
void NextBiggest(char * val){
size_t len = strlen(val);
bool swapped = false;
// case : 9788 o/p:9887
//IF THERE IS ANY NUMBER IN OTHER PLACE, SMALLER THAN THE UNITth PLACE THE SWAP THEM
// AND YOU HAVE FOUND THE NEXT BIGGEST NUMBER
for(int i = len-2; i >= 1; i--)
{
if(val[len-1] > val[i]){
swap(val[len-1],val[i]);
swapped = true;
break;
}
}
//case : 145621 o/p:151246
//case 8997 o/p:9789
//IN CASES AS SHOWN ABOVE CHECK EVERY ALTERNATE DECIMAL PLACE VALUE, IF YOU FIND A SMALLER VALUE IN THE HIGHER DECIMAL PLACE SIMPLY SWAP THEM AND SORT THE INPUT FROM THAT POSITION.
if(swapped == false)
{
int i = 0;
for(i = len-2; i >=1; i--)
{
if(val[i] > val[i-1])
{
swap(val[i],val[i-1]);
swapped = true;
break;
}
}
if(swapped == true)
{
char* ptr = &val[i];
quicksort(ptr,0,(len - (ptr-val)-1));
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char numeric [256];
memset(numeric,0,256);
cin >> numeric;
NextBiggest(numeric);
cout < < "The next biggest val is :" < < numeric;
return 0;
}
Subscribe to:
Post Comments (Atom)
.jpg)
No comments:
Post a Comment