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

Зачем нужны сортировки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
wwmwwm
 Аватар для wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
08.05.2013, 20:15     Зачем нужны сортировки #1
Скажите пожалуйста, зачем при подготовке к олимпиаде по программированию, нужно учить алгоритмы: Быстрая сортировка, сортировка пузырьком и так дальше, если в языке c++ есть функция sort. И не нужно морочиться!. Смысл изучения этих алгоритмов?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
08.05.2013, 20:17     Зачем нужны сортировки #2
На олимпиадах вроде нельзя юзать std.
kventin_zhuk
БНТУ ФИТР
 Аватар для kventin_zhuk
214 / 154 / 15
Регистрация: 26.12.2012
Сообщений: 382
08.05.2013, 20:20     Зачем нужны сортировки #3
wwmwwm, А смысл учиться писать, если можно печатать на клавиатуре? Cмысл учить таблицу умножения, если есть калькулятор? Смысл задавать глупые вопросы, если ответ очевиден?
wwmwwm
 Аватар для wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
08.05.2013, 20:27  [ТС]     Зачем нужны сортировки #4
Цитата Сообщение от kventin_zhuk Посмотреть сообщение
wwmwwm, А смысл учиться писать, если можно печатать на клавиатуре? Cмысл учить таблицу умножения, если есть калькулятор? Смысл задавать глупые вопросы, если ответ очевиден?
Нет, умничать здесь не нужно. Нужен конкретный ответ. Чем они мне помогут на олимпиаде, если я могу вызвать функцию сортировки?
kventin_zhuk
БНТУ ФИТР
 Аватар для kventin_zhuk
214 / 154 / 15
Регистрация: 26.12.2012
Сообщений: 382
08.05.2013, 20:40     Зачем нужны сортировки #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
wwmwwm, А зачем вам решать самому олимпиадные задачи? для какой цели вам это нужно? для начала на этот вопрос ответьте.
wwmwwm
 Аватар для wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
08.05.2013, 20:46  [ТС]     Зачем нужны сортировки #6
Цитата Сообщение от kventin_zhuk Посмотреть сообщение
wwmwwm, А зачем вам решать самому олимпиадные задачи? для какой цели вам это нужно? для начала на этот вопрос ответьте.
Так же можно сказать, зачем мне например библиотеки #include<iostream> и #include<iomanip>
Ее же можно на олимпиаде самому написать. Зачем же учить их объявление.
kventin_zhuk
БНТУ ФИТР
 Аватар для kventin_zhuk
214 / 154 / 15
Регистрация: 26.12.2012
Сообщений: 382
08.05.2013, 20:53     Зачем нужны сортировки #7
wwmwwm, Не преувеличивайте. Они расширят ваш кругозор и представление об алгоритмизации в целом. Устраивает? Успехов.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
08.05.2013, 20:55     Зачем нужны сортировки #8
Цитата Сообщение от Nekto Посмотреть сообщение
На олимпиадах вроде нельзя юзать std.
вы ошибаетесь, на многих можно

Добавлено через 2 минуты
Цитата Сообщение от wwmwwm Посмотреть сообщение
Быстрая сортировка, сортировка пузырьком и так дальше, если в языке c++ есть функция sort.
а на олимпиадах все на с++ пишут? помоему нет, есть еще люди которые на паскале пишут
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
08.05.2013, 22:34     Зачем нужны сортировки #9
wwmwwm, вот пример простенькой, но прикольной задачи с олимпиады, тут вас шаблоны не спасут.
Кликните здесь для просмотра всего текста
ограничение времени на тест: 1 сек.
ограничение памяти на тест: 65536 KB.
Дана последовательность A, состоящая из N целых чисел. Необходимо отсортировать ее таким образом, чтобы никакие два стоящих рядом элемента не имели последовательных значений. Другими словами, B[i] + 1 != B[i + 1] для всех i, таких что 0 <= i < N-1, где B - последовательность, полученная после сортировки.

Входные данные
В первой строке находится натуральное число N (1 <= N <= 50). Во второй строке даны N чисел A[i] - элементы последовательности A (0 <= A[i] <= 1000).

Выходные данные
Выведите N чисел - искомую отсортированную последовательность. Если ответ не однозначен, выведите последовательность, минимальную в лексикографическом смысле.

Пример

Ввод
3
1 2 3

Вывод
1 3 2

Пояснение
Существует три последовательности, удовлетворяющих заданному критерию: {1, 3, 2}, {2, 1, 3} и {3, 2, 1}. Первая является лексикографически минимальной.


Добавлено через 5 минут
Вот ещё 1 пример
Кликните здесь для просмотра всего текста

Рассмотрим алгоритм сортировки пузырьком.

Pascal
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
var
 
  a : array [1..50000] of integer;
 
  n, b, i, k, j, x, t : integer;
 
  loopCnt : integer;
 
begin
 
  read(n);
 
  for i := 1 to n do read(a[i]);
 
 
 
  loopCnt := 0;
 
 
 
  b := n;
 
  while b > 0 do begin
 
    inc(loopCnt);
 
    t := 0;
 
    for j := 1 to b - 1 do
 
      if a[j] > a[j + 1] then begin
 
        x := a[j]; 
 
        a[j] := a[j + 1]; 
 
        a[j + 1] := x;
 
        t := j;
 
      end;
 
    b := t;
 
  end;
 
 
 
  for i := 1 to n do
 
    write(a[i], ' ');
 
end.

Вам задана перестановка, которая подается на вход этого алгоритма сортировки. Найдите значение переменной loopCnt после выполнения алгоритма.

Входные данные
Число N (1 <= N <= 50000), затем перестановка.

Выходные данные
Выведите ответ.

Пример

Ввод
5
1 4 3 5 2

Вывод
4
wwmwwm
 Аватар для wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
08.05.2013, 23:10  [ТС]     Зачем нужны сортировки #10
В общем то я понял. Это расширяет кругозор, а так же не во всех языках есть функции сортировки в готовом виде. То что я сделаю в C++ вызовом одной функции, в Java я буду писать строчек 10-15
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.05.2013, 00:09     Зачем нужны сортировки #11
wwmwwm, к тому же стандартные функции всегда медленнее рукописных
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 00:19     Зачем нужны сортировки #12
aram_gyumri, вообще довольно резкое высказывание, ибо qsort если и реализовывать в ручную, то стоит помнить о том, что стандартный qsort может деградировать до O(N^2) ужс, сами понимаете, чтобы этого избежать нужно погемороиться, и кто знает, может наша асимптотика будет хуже чем заложенная.

Добавлено через 2 минуты
aram_gyumri, кстати, помню как рукописный stack творил чудеса, действительно прибавка к скорости невероятно большая, аналогично выключению вертикального синхроимпульса в 3d играх
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
09.05.2013, 06:39     Зачем нужны сортировки #13
Цитата Сообщение от kventin_zhuk Посмотреть сообщение
А смысл учиться писать, если можно печатать на клавиатуре?
вот именно... нет никакого смысла...)

Добавлено через 3 минуты
во-первых, это полезно для мозга. во-вторых, не всегда нужно сортировать втупую. в-третьих, не на всех олимпиадах можно использовать СТЛ.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2013, 10:31     Зачем нужны сортировки
Еще ссылки по теме:

C++ зачем нужны итераторы?
C++ Зачем нужны указатели?
Зачем нужны дружественные функции C++

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

Или воспользуйтесь поиском по форуму:
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.05.2013, 10:31     Зачем нужны сортировки #14
Цитата Сообщение от Ternsip Посмотреть сообщение
aram_gyumri, вообще довольно резкое высказывание, ибо qsort если и реализовывать в ручную, то стоит помнить о том, что стандартный qsort может деградировать до O(N^2) ужс, сами понимаете, чтобы этого избежать нужно погемороиться, и кто знает, может наша асимптотика будет хуже чем заложенная.
ну я не именно qsort имел ввиду, тот же set работает гараздо медленнее рукаписного красно-черного дерева
Yandex
Объявления
09.05.2013, 10:31     Зачем нужны сортировки
Ответ Создать тему
Опции темы

Текущее время: 10:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru