Сортировка подсчетом

Ноябрь 14th, 2011 § 0 comments

Зарегистрировался на CodeChief и сразу попался, простецкая задача на сортировку, но не тут -то было пробовал Quicksort и MergeSort оба выдавали Time Limit Exceeded. Ответ оказался прост, нужно было воспользоваться сортировкой подсчетом. Основная идея создать нулевой массив размерностью в диапазон в водимых чисел и при вводе чисел производить инкрементацию в итоге после получения данных мы уже получаем “отсортированный” массив. Алгоритм отлично работает с положительными числами, для работы с отрицательными или со структурами данных требуется его переделать. Сортировка подсчетом на вики wiki Ниже приведен код

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

int main() {
int i,t;
int N[1000001]={0};
scanf(“%d”,&t);
for (i=0;i<t;i++) {
int n;
scanf(“%d”,&n);
N[n]++;
}
for (i=0;i<1000001;i++) {
for (int j=0;j<N[i];j++) {
printf(“%d\n”,i);
}
}
return 0;
}

Tagged

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Смотреть фильмы онлайн