sort array of integers lexicographically C++

Aseem Goyal picture Aseem Goyal · Oct 25, 2013 · Viewed 8.7k times · Source

I want to sort a large array of integers (say 1 millon elements) lexicographically.

Example:

input [] = { 100, 21 , 22 , 99 , 1  , 927 }
sorted[] = { 1  , 100, 21 , 22 , 927, 99  }

I have done it using the simplest possible method:

  • convert all numbers to strings (very costly because it will take huge memory)
  • use std:sort with strcmp as comparison function
  • convert back the strings to integers

Is there a better method than this?

Answer

Oswald picture Oswald · Oct 25, 2013

Use std::sort() with a suitable comparison function. This cuts down on the memory requirements.

The comparison function can use n % 10, n / 10 % 10, n / 100 % 10 etc. to access the individual digits (for positive integers; negative integers work a bit differently).