CareerCup

This is just sorting algo (descending order ).. the only modification we need to do is .. while comparing 2 integers , we have concat one with other and compare ....
ex: {9,10} --> then while comparing 9 and 10 .. we have concat these two...910 > 109 ... so 9 comes before 10
Ex: {9,900}--> 9900>9009 --> 9 comes before 900..
Ex {10,107} --> 10710 > 10107 --> 107 comes before 10....

Here is the C++ code for this

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int compareNumString( string num1, string num2 )
{
    	string joined_num1 = num1+num2;
	string joined_num2 = num2+num1;
	return joined_num1.compare(joined_num2) > 0 ? 1: 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
	vector<string> array;
	//output should be 6054854654
	array.push_back("54");
	array.push_back("546");
	array.push_back("548");
	array.push_back("60");

	// output should be 777776
	/*array.push_back("7");
	array.push_back("776");
	array.push_back("7");
	array.push_back("7");*/

	//output should be 998764543431
	/*array.push_back("1");
	array.push_back("34");
	array.push_back("3");
	array.push_back("98");
	array.push_back("9");
	array.push_back("76");
	array.push_back("45");
	array.push_back("4");
	*/

	std::sort( array.begin(), array.end(), compareNumString );

	for(int i=0; i < array.size() ; i++ )
		cout<<array[i];
   
	return 0;
}

do radix sort and append the digit..

Here we have to sort the numbers according to the digit positions...If conflict occurs between any 2 numbers sort according to the next digit.
Let me explain with an example:

Array: [9, 18, 3, 28, 173]
Step 1: Sort according to 1st digit : [9,3,28,(18,173)]
step 2: here 18, 173 have same 1st digit. So sort according to next digit. : [9, 3, 28, 18, 173]

So output: 932818173...

P.S: We can use 'Divide by 10' technique to get first digit each time.

This approach is a bit bad, but How about, generate all the n digit (n is size of array) permutation of given array and then picking up the largest number among them arr[1,2]

2 digit permutations are [1,2] [2,1] ....21 is the largest..you need to use some extra space to store the permutation output ...and then sort that.....This can be optimized however

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int compare(const void *xptr, const void *yptr)
{
char *sbuffer=(char *)malloc(sizeof(char)*20),*tmp;
char *lbuffer=(char *)malloc(sizeof(char)*20);
int x=*(int *)xptr;
int y=*(int *)yptr;
int cnt=0,swapped=0;
itoa(x,sbuffer,10);
itoa(y,lbuffer,10);
if(strlen(sbuffer)>strlen(lbuffer))
{
tmp=sbuffer;
sbuffer=lbuffer;
lbuffer=tmp;
swapped=1;
}
while(*sbuffer==*lbuffer&&*sbuffer!='\0')
{
sbuffer++;
lbuffer++;
cnt++;
}
if(*sbuffer=='\0')
if((*lbuffer-'0')>(*(sbuffer-cnt)-'0'))
return(swapped?-1:1);
else
return(swapped?1:-1);
else
return(swapped?(*sbuffer-*lbuffer):-(*sbuffer-*lbuffer));
}


int main()
{
int values[]= {9, 18, 3, 28, 173};
int i;
//int values[]={9,900};
//int values[]={10,107};
//int values[]={3,71,2};
//int values[]={7,76,7,7};
int size=sizeof(values)/sizeof(values[0]);
qsort (values, size, sizeof(int), compare);
for(i=0; i<size; i++)
printf ("%d ",values[i]);
getchar();
}

How about simply sorting even and odd positions separately.
Here is the code. 
#define ASC 	1
#define DEC 	2

void sort(int *a, int len, int skip, int order)
{
	int i,j;

	for(i=0; i<len; i+=skip) {
		for(j=i+skip; j<len;j+=skip) {
			if((order == ASC && a[i] > a[j]) ||
					(order == DEC && a[i] < a[j]))
				swap(a, i, j);
		}
	}
}

int main()
{
        int a[] = {7,1,4,2,18,34,16,12,19,56,3,20, 5};
	int len = sizeof(a)/sizeof(int);
        sort(a, len, 2, ASC);
        sort(a+1, len-1, 2, DEC);

        return 0;
}

lexographic sorting will do.
Example: 10, 7, 9, 20, 30

compare 10 and 7 : 7 is greater than 1. NUMBER: 710
compare 710 and 9 : 9 is greater than 7. NUMBER: 9710
compare 9710 and 20 : 2 < 9 go forward check 2 < 7 go forward 2 > 1 Number: 972010.
compare 972010 and 30 : 3 < 9 go forward 3 < 7 go forward 3 > 2 Number: 97302010.

suppose u have some numbers in an array ,then u have to find greatest no.then there must me some no start with either 0-9 .u have to separate those no in different bucket on the basis of starting no.then within each bucket sort the number.sorting is done on the basis of digit,if 2 no is dere then sort it in this manner.example:- suppose i have 2 no in a bucket,(4,48).these 2 goes in 1 bucket.then on the basis of digit sort this(48,4).then ur work is done.

Step 1:- filter base no digits like (single,double...)
Step 2:- sort all single, then all double......
step 3:- merge
step 4:- output

E.g. {1, 34, 3, 98, 9, 76, 45, 4} 
   1. Sort on most significant digit of each number first. After this step all numbers starting with 9 will be followed by all numbers starting with 8 and so on. For above example: {9, 98, 76, 45, 4, 3, 34, 1}. There will be 9 groups and a group of zeros if present.
    2. Sort the numbers within each group with the following special comparison function compare(a,b):
         2a. Normal integer comparison with a,b have same number of digits. 
         2b. If a and b do not have equal number of digits, add the digit corresponding to the group as many times as needed to make the two have equal number of digits. 
      3. The final answer is the concatenation of the sorted numbers in steps 1 and 2.

What about this guys
1. Sort array in descending order
2. build the string by appending each digit
3. cast to int

Assumption: number is an integral 64 bits.

Insertion sort in descending order. With long int of 64 bits, the max positive value possible is 9223372036854775807, which is 19 digits. Insertion sort may do element copies. For example, if all the elements are sorted in descending order except the first element, then insertion sort needs to shift N-1 elements. In contrast, using quicksort, the number of copy operations is logn.

public static void sort(final List<Integer> digits) {
        for (int i = 1; i < digits.size(); i++) {
            int storeIndex = i;
            int valueToInsert = digits.get(i);

            while ((storeIndex > 0) &&
                    (valueToInsert > digits.get(storeIndex - 1))) {
                digits.set(storeIndex, digits.get(storeIndex - 1));
                storeIndex--;
            }

            digits.set(storeIndex, valueToInsert);
        }
    }

scala> val a = Array(9,6,8,1).sortWith((x,y) => x.toString > y.toString).mkString.toInt
a: Int = 9861

How about a bucket sort and ordering from reverse???

This is the correct solution : www {dot} geeksforgeeks {dot} org {slash} given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest-number

Sort the array in descending order -
T(N) = O(NlgN) and S(N) = O(1)

public static void findMaxNumber(Integer[] input){
        Arrays.sort(input, new Comparator<Integer>(){

            @Override
            public int compare(Integer o1, Integer o2) {
                StringBuffer buf = new StringBuffer();
                buf.append(o1);
                buf.append(o2);
                String s1 = buf.toString();
                String s2 = buf.reverse().toString();
                return s2.compareTo(s1);
            }
        });

        StringBuffer buf2 = new StringBuffer();
        for(int n : input){
            buf2.append(n);
        }

        System.out.println(buf2.toString());
    }

do permutation of number and keep track of maximum number.

Convert the array into String so that we have all the array as the String of digits and then we can do a sort on the String in descending order to get the largest number.