Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Сортировки - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Происходит ли установка студии? http://www.cyberforum.ru/cpp-beginners/thread968738.html
Я скачал вроде визуал студию и стал ее как будто бы устанавливать. Прошло так наверно минут семнадцать, может даже чуть больше. Таки непонятно, происходит ли установка, или что это? Я сначала...
C++ Определение размера данных, находящихся по адресу x Приветствую! Сабж: #include <cstdlib> #include <iostream> using namespace std; int main(int argc, char *argv) http://www.cyberforum.ru/cpp-beginners/thread968731.html
C++ Параллельные вычисления
Здравствуйте, не знаю в какой ветке постить, решил в этой. Хочу использовать эти технологии OpenMP и\или GPGPU(OpenCL) но практической задачи я не придумал, хотелось бы спросить у вас, к чему...
Сортировка матрицы по последнему элементу строки C++
Всем привет. Задача: Нужно упорядочить строки матрицы в порядке возрастания их последних элементов. Вся программа почти готова, но функция сортировки у меня никак не работает. Вроде как эта функция,...
C++ Перевод системного времени http://www.cyberforum.ru/cpp-beginners/thread968705.html
Задача отловить изменение системного времени time1=time(NULL); Sleep(delay); time2=time(NULL); if(time1!=time2-delay) std::cout<<"Време перевели"<<; Когда пользователь переводит сам время...
C++ Нужна подмога по классам (Создать класс матрица) Вопщем так. мне завтра нужно сдать эту лабу. помогите пожалуйста доделать. ниже прикрепляю тект задания и часть программы, что уже сделала. P.S. просьба,писать в том же стиле чтоли,как я) чтобы мне... подробнее

Показать сообщение отдельно
fakesc
0 / 0 / 0
Регистрация: 05.01.2013
Сообщений: 2

Сортировки - C++

04.10.2013, 12:53. Просмотров 347. Ответов 9
Метки (Все метки)

Вообщем у меня было задание отсортировать по убыванию массивы (заданный рандомно, по убыванию, по возрастанию)
Критерий: количество перестановок, что собственно и вызвало у преподавателя вопросы

Простые вставки:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void prostObratn(int *a,int n)
{
  int  x, i, j,temp;
  for ( i=1; i < n; i++)
   { 
    x = a[i];
    for ( j=i-1; j>=0 && a[j] < x; j--)
    {
    a[j+1] = a[j];gchng++;
 
    }
    a[j+1] = x;gchng++;
    }
}
Пирамидальная сортировка:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void sift(int *A,int L,int R) 
{
int i,j,x,k; 
i=L; j=2*L+1; 
x=A[L]; 
if ((j<R) && (A[j]>A[j+1]))
    j++;
while ((j<=R) && (x>A[j])) 
    { 
    k=A[i];
    A[i]=A[j];
    A[j]=k;
    gchng+=3;
    i=j;
    j=2*j+1;
    if ((j<R) && (A[j]>A[j+1]))
        j++;
    }
}
void HeapSort(int *A,int n) 
{
int L,R,x,i;
L=n/2; R=n-1;
while (L>0)
{
L=L-1;
sift(A,L,R);
}
while (R>0)
{ x=A[0]; A[0]=A[R]; A[R]=x;R--;
sift(A,L,R);}
}
Результаты:

http://img5.imageshack.us/img5/2259/4a3t.jpg

Вопрос преподавателя:


Почему количество перестановок для "простых вставок" и для "пирамидальной сортировки" при сортировке УЖЕ отсоротированного массива по УБЫВАНИЮ не является нолем. При пирамидальной я вроде как разобрался, так как это неустойчивая сортировка и массив будет считываться хаотично, вроде как. Поправьте, если неправ, а вот со вставками мне немного непонятно, в связи с этим и прошу помощи в ответе на вопрос
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru