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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Лунь
0 / 0 / 0
Регистрация: 11.08.2015
Сообщений: 11
#1

Сортировка расчёской и быстрая сортировка - C++

17.08.2015, 17:32. Просмотров 1205. Ответов 5
Метки нет (Все метки)

В файле in.txt записана последовательность целых чисел. Заданными методами отсортировать числа и записать в файлы out1.txt и out2.txt. Используя библиотеку <time.h>, подсчитать время, потраченное на каждую сортировку отдельно и вывести это время на консоль. Подскажите, с чего начать или покажите готовое решение
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.08.2015, 17:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка расчёской и быстрая сортировка (C++):

Сортировка расчёской - C++
Всем привет! Помогите, пожалуйста разобрать код. template &lt;typename T, typename Comp&gt; void combsort(T array, std::size_t size, Comp...

Пояснить каждую строчку кода. Сортировка расчёской - C++
Нужно пояснить каждую строчку кода #include &lt;algorithm&gt; #include &lt;iostream&gt; using namespace std; //newGap Function ...

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка (сортировка методом Хоара) - C++
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке убывания. Вывести массивы до и после...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий...

5
Evgenii Kushner
12 / 12 / 7
Регистрация: 12.08.2015
Сообщений: 55
17.08.2015, 20:13 #2
А как записаны числа в файле через пробел или в столбик?
И какие именно методы сортироки?
И в два выходных файла записывать одни и те же числа?
0
Лунь
0 / 0 / 0
Регистрация: 11.08.2015
Сообщений: 11
19.08.2015, 20:27  [ТС] #3
Через пробел.
Сортировка расчёской(comb sort) и быстрая сортировка(Quicksort).
После сортировки одну часть в один файл, другую часть - в другой.
0
Evgenii Kushner
12 / 12 / 7
Регистрация: 12.08.2015
Сообщений: 55
19.08.2015, 21:34 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Надеюсь меня не забанят тут)))
Но вот что у меня пока есть ... Читает с файла правда в столбик, есть одна сортировка расчёской без вывода в файл и <time.h>
Сейчас через пару часов думаю смогу сделать всё как надо))
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
void show(int *array, int size)
{
    for (int i = 0; i < size; ++i)
    {
        cout << array[i] << '\n';
    }
}
 
 
void sort(int *array, int size )
{
  if (!array || !size)
    return;
 
  int jump = size;
  bool swapped = true;
 
  while (jump > 1 || swapped)
  {
    if (jump > 1)
      jump = (int)(jump / 1.25);
    swapped = false;
    for (int i = 0; i + jump < size; i++)
      if (array[i] > array[i + jump])
        std::swap(array[i],array[i + jump]), swapped = true;
  }
}
 
int main()
{
    vector <int> array;
    int data;
    ifstream fin("in.txt");
    while (fin >> data) {
        array.push_back(data);
    }
    int N = array.size();
    int *mas = new int[N];
    for(int i = 0; i < N; ++i)
    {
        mas[i] = array[i];
    }
    array.clear();
    show(mas,N);
    sort(mas,N);
    show(mas,N);
}
есть плюс, что можно читать любое кл-во чисел(через вектор сделал)

Добавлено через 36 минут
Так вроде готово проверяйте)
Расчёску и квиксорт украл) Делал первую вчера поэтому ссылки нету) А вот квиксорт http://algolist.manual.ru/sort/quick_sort.php
Правда считывает и записывает в столбик но тут я хз как сделать через пробел)
Библиотека тайм мутная но вроде тут только одна функция определяет затраченое время, так что думаю не ошибся.
http://www.opennet.ru/docs/RUS/libc/libc-6.html
Вот окончательный код

Берет из файла любое кол-во чисел в столбик, сортирует по двум разным, выводит время на конслось, сортированые числа по файлам.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>
#define MAXSTACK 2048   
 
using namespace std;
 
void write(int *array, int size, ofstream &out)
{
        for (int i = 0; i < size; ++i)
    {
        out << array[i] << '\n';
    }
}
 
void qSort(int a[], int size)
{
  int i, j;     
  int lb, ub;       
  int lbstack[MAXSTACK], ubstack[MAXSTACK]; 
  int stackpos = 1;   
  int ppos;           
  int pivot;              
  int temp; 
  lbstack[1] = 0;
  ubstack[1] = size-1;
  do {
    lb = lbstack[ stackpos ];
    ub = ubstack[ stackpos ];
    stackpos--;
    do {
      ppos = ( lb + ub ) >> 1;
      i = lb; j = ub; pivot = a[ppos];
      do {
        while ( a[i] < pivot ) i++;
        while ( pivot < a[j] ) j--;
 
        if ( i <= j ) {
          temp = a[i]; a[i] = a[j]; a[j] = temp;
          i++; j--;
        }
      } while ( i <= j );
      if ( i < ppos ) {
        if ( i < ub ) {      
          stackpos++;       
          lbstack[ stackpos ] = i;
          ubstack[ stackpos ] = ub;
        }
        ub = j;        
      } else {           
        if ( j > lb ) { 
          stackpos++;
          lbstack[ stackpos ] = lb;
          ubstack[ stackpos ] = j;
        }
        lb = i;
      }
    } while ( lb < ub );
  } while ( stackpos != 0 );
}
 
 
void sort(int *array, int size )
{
  if (!array || !size)
    return;
  int jump = size;
  bool swapped = true;
 
  while (jump > 1 || swapped)
  {
    if (jump > 1)
      jump = (int)(jump / 1.25);
    swapped = false;
    for (int i = 0; i + jump < size; i++)
      if (array[i] > array[i + jump])
        std::swap(array[i],array[i + jump]), swapped = true;
  }
}
 
int main()
{
    vector <int> array;
    int data;
    ifstream fin("in.txt");
    ofstream out1("out1.txt");
    ofstream out2("out2.txt");
    while (fin >> data) {
        array.push_back(data);
    }
    int N = array.size();
    int *mas_s = new int[N];
    int *mas_qs = new int[N];
    for(int i = 0; i < N; ++i)
    {
        mas_s[i] = array[i];
        mas_qs[i] = array[i];
    }
    array.clear();
    clock_t time;
    time = clock();
    sort(mas_s,N);
    cout << "Time for sort  : " << clock() - time << '\n';
    write(mas_s,N,out1);
    clock_t time_1;
    time_1 = clock();
    sort(mas_qs,N);
    cout << "Time for sort  : " << clock() - time_1 << '\n';
    write(mas_s,N,out2);
    return 0;
}
1
Лунь
0 / 0 / 0
Регистрация: 11.08.2015
Сообщений: 11
19.08.2015, 22:33  [ТС] #5
Спасибо, теперь осталось самому разобраться в коде)
P.S. Числа через пробел тоже сортирует
0
Evgenii Kushner
12 / 12 / 7
Регистрация: 12.08.2015
Сообщений: 55
19.08.2015, 22:44 #6
Всегда рад помочь, пришлось выделить память под два одинаковых массива, что бы сортировать одни и те же числа, а не сортировать уже отсортированый массив.
0
19.08.2015, 22:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.08.2015, 22:44
Привет! Вот еще темы с ответами:

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

Сортировка методом "быстрая сортировка" - C++
Здравствуйте! Имеется структура: struct BMS_Data { int* SortNodesList; double* NodesX; double* NodesY; ...

Быстрая сортировка - C++
Помоги мне ответить на вопросы,большая просьба,заранее спасибо Быстрая сортировка #include &lt;iostream&gt; using namespace std; ...

Быстрая сортировка - C++
void qSort(int a, int N) { int i = 0, j = N; int temp, p; p = a; do { while ( a &lt; p ) i++;


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru