Ivelin Pavlov

За нуждите на ЦЕРН даден масив от данни, които те обработват, трябва да бъде сортиран. За
съжаление в ЦЕРН всички са твърде заети, за да напишат алгоритъм за сортиране, защото
последният им опит е излязал извън контрол и ако не бъдат взети спешни мерки, Земята ще бъде
погълната от черна дупка. Можете ли да помогнете на ЦЕРН?
За да може ЦЕРН да се възползва от алгоритъма ви, те ще ви зададат цяло число N < 10000, брой
на числа, които трябва да се сортират, последвано от редица от цели числа всяко от които е по-
малко от 10000000. Вие трябва за техните нужди да сортирате масива лексикогравски. Това става
като сравняваме първите цифри и ако при едното цифрата е по-малка, то е по-малко. Ако са
равни продължаваме със следващите цифри. Ако на някое от числата цифрите му се изчерпат
преди тези на другото по описания алгоритъм, тогава то е по-малкото (например 190 е по-голямо
от 1000).
Изхода от програмата ви трябва да е сортираните числа като всяко се принтира на отделен ред.

Вход:
5
190
1000
5
11
22

Изход:
1000
11
190
22
5

#include <iostream>
using namespace std;
int a[10000];

int intlength(int a) {
	if(a==0) return 1;
    int i=0;
    while(a>0) {
   	 a = a/10;
   	 i++;
    }
    return i;
}
int e(int a) {
	if(a<=0) return 1;
	int b = 1;
	for(int i=0;i<a;i++) {
		b = b*10;
	}
	return b;
}
bool leksikogravskaProverkaPoGolqmo(int a, int b) {
    int alen = intlength(a);
    int blen = intlength(b);
	int i = 1;
	bool ss= false;
	int tmpa,tmpb;
    while(alen>0 && !ss) { 
		tmpa = (a % e(alen))/e(alen-1);
		tmpb = (b % e(blen))/e(blen-1);
		if(blen<1) tmpb=-1;
		if(tmpa>tmpb) {
			ss = !ss;
			return 1;
		} else if(tmpa<tmpb) {
			return 0;
		}
		alen--;
		blen--;
		i++;
    }
    return 0;
}

void quicksort(int arr[],int left,int right) {
	int length = sizeof(arr);
	int i=left,j=right;
	int pivot = arr[(left+right)/2];

	while(i<=j) {
		while(!leksikogravskaProverkaPoGolqmo(arr[i],pivot) && arr[i]!=pivot)
			i++;
		while(leksikogravskaProverkaPoGolqmo(arr[j],pivot))
			j--;
		if(i<=j) {
			swap(arr[i],arr[j]);
			j--;
			i++;
		}
	}
	if(left<j)
		quicksort(arr,left,j);
	if(i<right)
		quicksort(arr,i,right);
}

int main() {
	int count;
	cin>>count;
	for(int i=0; i< count; i++) {
		cin>>a[i];
	}
	quicksort(a,0,count-1);
	for(int i=0;i<count;i++) {
		
		cout<<a[i];cout<<endl;
	}
}