Форум программистов CodeGuru
23 Август 2017, 04:37:34 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.

Войти
Новости:
 
   Начало   Помощь Войти Регистрация  
Страниц: [1]   Вниз
  Печать  
Автор Тема: Количество перестановок при сортировке  (Прочитано 13122 раз)
0 Пользователей и 1 Гость смотрят эту тему.
MahovIV
Новичок
*
Офлайн Офлайн

Сообщений: 3


Просмотр профиля
« : 01 Январь 2014, 17:11:10 »

Помогите решить задачу.
 В этой задаче вам необходимо проанализировать некоторый алгоритм сортировки. Этот алгоритм сортирует последовательность из N различных целых чисел, переставляя по два соседних элемента последовательности до тех пор, пока она не будет упорядочена по возрастанию. Ваша задача состоит в том, чтобы посчитать, сколько таких перестановок двух соседних элементов необходимо сделать, чтобы отсортировать заданную последовательность.
 Входные данные

 Первая строка входных данных содержит единственное натуральное число 1 ≤ N < 500000 - длину сортируемой последовательности. Каждая из последующих N строк содержит целое число 0 ≤ a ≤ 999999999, i-ый элемент последовательности. Все элементы последовательности различны.
 Выходные данные

 Выведите единственное целое число - минимальное количество перестановок соседних элементов последовательности, необходимое для того, чтобы отсортировать ее по возрастанию.
 Преподаватель сказал использовать не пузырьковую сортировку, а сортировку слиянием. Я нашёл код сортировки слиянием, но при массивах в 200000 элементов и более происходило переполнение стека. Как реализовать таую сортировку для больших массивов? Как подсчитать количество перестановок?
Программа выглядит так.
Код:
#include <stdio.h>

int main() {

int a[100], N, pr = 0, i, j, c;
scanf("%d", &N);
for(i = 0; i < N; i++) {
scanf("%d", &a[i]);
printf("\n");
}
for(i = 0; i < N; i++)
for(j = N - 2; j >= i; j--) {
if(a[j] > a[j + 1]) {
c = a[j];
a[j] = a[j + 1];
a[j + 1] = c;
pr++;
}
}
printf("%d\n", pr);
return 0;
}
Но преподаватель сказал, что нельзя использовать пузырькоую сортировку, а нужно использовать сортировку слиянием. Я находил много таких алгоритмов, но с их помощью нельзя отсортировать массив размером более 200000 элементов. Иными словами, нужен алгоритм с глобальными переменными. Покажите такой код, который бы сортировал большие массивы и чтобы можно было пересчитывать количество перестановок.
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #1 : 02 Январь 2014, 10:37:39 »

Помогите решить задачу.
 В этой задаче вам необходимо проанализировать некоторый алгоритм сортировки.

Т.е. задача в анализе, а не написании кода, так ?

Выведите единственное целое число - минимальное количество перестановок соседних элементов последовательности, необходимое для того, чтобы отсортировать ее по возрастанию.

И результатом анализа должна стать оценка количества перестановок (минимального).

Преподаватель сказал использовать не пузырьковую сортировку, а сортировку слиянием.

В сортировке слиянием перестановок нет.

Я нашёл код сортировки слиянием, но при массивах в 200000 элементов и более происходило переполнение стека. Как реализовать таую сортировку для больших массивов? Как подсчитать количество перестановок?

Наверно достаточно увеличить максимальный размер стека путем использования соответствующей опции компилятора. Возможно также, код компилируется под платформу, где объем адресного пространства резко ограничен (под дос, например).
Записан

MahovIV
Новичок
*
Офлайн Офлайн

Сообщений: 3


Просмотр профиля
« Ответ #2 : 03 Январь 2014, 01:13:06 »

Помогите решить задачу.
 В этой задаче вам необходимо проанализировать некоторый алгоритм сортировки.
Нужно решить эту проблему именно при помощи алгоритма.
Мне сказали использовать именно сортировку слиянием.
Помогите решить задачу.
 В этой задаче вам необходимо проанализировать некоторый алгоритм сортировки.

Т.е. задача в анализе, а не написании кода, так ?

Выведите единственное целое число - минимальное количество перестановок соседних элементов последовательности, необходимое для того, чтобы отсортировать ее по возрастанию.

И результатом анализа должна стать оценка количества перестановок (минимального).

Преподаватель сказал использовать не пузырьковую сортировку, а сортировку слиянием.

В сортировке слиянием перестановок нет.

Я нашёл код сортировки слиянием, но при массивах в 200000 элементов и более происходило переполнение стека. Как реализовать таую сортировку для больших массивов? Как подсчитать количество перестановок?

Наверно достаточно увеличить максимальный размер стека путем использования соответствующей опции компилятора. Возможно также, код компилируется под платформу, где объем адресного пространства резко ограничен (под дос, например).

Т.е. задача в анализе, а не написании кода, так ?

Выведите единственное целое число - минимальное количество перестановок соседних элементов последовательности, необходимое для того, чтобы отсортировать ее по возрастанию.

И результатом анализа должна стать оценка количества перестановок (минимального).

Преподаватель сказал использовать не пузырьковую сортировку, а сортировку слиянием.

В сортировке слиянием перестановок нет.

Я нашёл код сортировки слиянием, но при массивах в 200000 элементов и более происходило переполнение стека. Как реализовать таую сортировку для больших массивов? Как подсчитать количество перестановок?

Наверно достаточно увеличить максимальный размер стека путем использования соответствующей опции компилятора. Возможно также, код компилируется под платформу, где объем адресного пространства резко ограничен (под дос, например).
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #3 : 03 Январь 2014, 10:26:23 »

?
Записан

Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!