Quicksort algorithm or something similar

[MPC1984]

Hi everybody!

I want to improve the following algorithm:

Code: Select all

#include <stdio.h>

int i, j, numHabitantes, contador;
long diasVividos [100000];

int main(void) {
	scanf("%d", &numHabitantes);
	while(numHabitantes > 0) {
		contador = 0;
		for(i = 0; i < numHabitantes; i++) {
			scanf("%d", &diasVividos[i]);
		}
		for(i = 0; i < numHabitantes - 1; i++) {
			for(j = i + 1; j < numHabitantes; j++) {
				if(diasVividos[i] > diasVividos[j]) {
					contador++;
				}
			}
		}
		printf("%d\n", contador);
		scanf("%d", &numHabitantes);
	} 
	return 0;
}

I have tried to use quicksort algorithm, but I don't know how.

Thanks in advance.

[brianfry713]

I can't read your variable names, what are you trying to accomplish? What is the I/O? Is there a problem statement?
In C you can use qsort().

[MPC1984]

Sorry for the vagueness brianfry713

The problem in English is the following (sorry for the translation):

Temporary disorders: Once a technological advance comes the "general public" effects usually arise from their use anyone would have predicted at first. The nomofobia or irrational to leave home without mobile phone fear, De Quervain syndrome by intensive use of the thumbs or extended Internet addiction are three examples of digital consequences suffered by the population in the XXI century.
When he got to travel in time, only a few psychologists sounded the alarm about the danger which could be an overuse of these trips on people. At first they called temporary disorders although the term evolved into what we now call Fry syndrome in reference to a character in a popular series of the XXI century.
These disorders are caused by excessive consumption of time travel due to aging body still suffering even when in a moment that does not belong. For example, if a student passes 20-year history 30 years in ancient Egypt studying in situ the lives and customs of the people of that time, when he returns has the body of a man of 50 years if age for administration follow 20. mental disorders being produced to look older than his own father can lead to destruction.
At the last meeting of the LIE (Ministry of temporary wrongs) decided to take action in this situation. The first step is to know how many people are affected and the level of each disorder. Defined the level of temporary disorder of a person as the number of people who, despite being older than oneself from an administrative point of view, have experienced fewer days.
For this, the LIE handles the actual number of days that each person has lived and now wants to know the temporal disorder of the whole population, or what is the same, the amount of temporary disorders of all inhabitants.

Input:
The entry will be composed of different test cases, each in two lines. The first line will have the number of inhabitants of the population being studied (100,000). In the second line the actual age (number of days spent) of each of those ordered by administrative age appears.
The last test case is followed by a line with a 0 should not be processed.

Output:
For each test case a number indicating the total disarray of the population as defined number will be displayed.

Sample Input:
4
1000 2000 3000 4000
4
10000 2000 8000 1000
0

Sample Output:
0
5

Notes:
The answer to the second test case example is the result of adding temporary disorders of all individuals. The first temporary disorder is 3, because despite being the youngest (from the administrative point of view) is older than the other three. The second temporal disorder is 1, because it is older than the last, and the third temporal disorder is also 1 for the same reason.

Here it's the code in C:

Code: Select all

#include <stdio.h>

int i, j, numHabitants, count;
long livedDays[100000];

int main(void) {
	scanf("%d", &numHabitants);
	while(numHabitants> 0) {
		count= 0;
		for(i = 0; i < numHabitants; i++) {
			scanf("%d", &livedDays[i]);
		}
		for(i = 0; i < numHabitants- 1; i++) {
			for(j = i + 1; j < numHabitants; j++) {
				if(livedDays[i] > livedDays[j]) {
					count++;
				}
			}
		}
		printf("%d\n", count);
		scanf("%d", &numHabitants);
	} 
	return 0;
}

I have had the veredict "TLE", and that's why I have thought in use quicksort algorithmn (which is a divide and conquer algorithm as indicating the category of the problem), but I don't know how. Could you help me please?

The complete problem is in: https://www.aceptaelreto.com/problem/st ... php?id=230

Thanks in advanced.

[MPC1984]

Hi everybody!

I don't know how to implement a divide and conquer algorithm in the previous problem. Someone could help me?

I only have two problems tried and not solved from http://www.aceptaelreto.com, and I want to have all solved .

Thanks in advance.