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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
#1

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

08.05.2013, 20:15. Просмотров 1830. Ответов 13
Метки нет (Все метки)

Скажите пожалуйста, зачем при подготовке к олимпиаде по программированию, нужно учить алгоритмы: Быстрая сортировка, сортировка пузырьком и так дальше, если в языке c++ есть функция sort. И не нужно морочиться!. Смысл изучения этих алгоритмов?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.05.2013, 20:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Зачем нужны сортировки (C++):

Зачем биты нужны это меньше байтов но int 32 бита но я не допер зачем это нужно это 4 байта то есть int не может больше 4 байт весить? - C++
Вот еще один вопрос зачем биты нужны это меньше байтов но int 32 бита но я не допер зачем это нужно это 4 байта то есть int не может...

Зачем нужны указатели - C++
Не могу понять синтаксис указателей. Понял, что это работа с адресами, что оператор & это адрес. А вот * как я понял, это объявление...

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

Зачем нужны исключения? - C++
Добрый вечер, прочитал статью об исключениях, не очень понимаю, почему бы не заменить их просто оператором if? Вот код с исключением: ...

Зачем нужны операторы << и >> - C++
В книжке Дейтлов есть код http://pic.ipicture.ru/uploads/091222/thumbs/q1TZw4n1JQ.jpg Вопрос в том, что там где написано, что числа...

Зачем нужны деревья? - C++
Изучил тему деревья (осуществлял втавки, удаление, обходы и т.д.). Теперь хочу разобраться, зачем они вообще нужны? В каких случаях надо...

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

Добавлено через 2 минуты
Цитата Сообщение от wwmwwm Посмотреть сообщение
Быстрая сортировка, сортировка пузырьком и так дальше, если в языке c++ есть функция sort.
а на олимпиадах все на с++ пишут? помоему нет, есть еще люди которые на паскале пишут
0
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
0
wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
08.05.2013, 23:10  [ТС] #10
В общем то я понял. Это расширяет кругозор, а так же не во всех языках есть функции сортировки в готовом виде. То что я сделаю в C++ вызовом одной функции, в Java я буду писать строчек 10-15
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.05.2013, 00:09 #11
wwmwwm, к тому же стандартные функции всегда медленнее рукописных
0
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 играх
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
09.05.2013, 06:39 #13
Цитата Сообщение от kventin_zhuk Посмотреть сообщение
А смысл учиться писать, если можно печатать на клавиатуре?
вот именно... нет никакого смысла...)

Добавлено через 3 минуты
во-первых, это полезно для мозга. во-вторых, не всегда нужно сортировать втупую. в-третьих, не на всех олимпиадах можно использовать СТЛ.
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.05.2013, 10:31 #14
Цитата Сообщение от Ternsip Посмотреть сообщение
aram_gyumri, вообще довольно резкое высказывание, ибо qsort если и реализовывать в ручную, то стоит помнить о том, что стандартный qsort может деградировать до O(N^2) ужс, сами понимаете, чтобы этого избежать нужно погемороиться, и кто знает, может наша асимптотика будет хуже чем заложенная.
ну я не именно qsort имел ввиду, тот же set работает гараздо медленнее рукаписного красно-черного дерева
0
09.05.2013, 10:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2013, 10:31
Привет! Вот еще темы с ответами:

Зачем нужны указатели? - C++
Интересует вопрос, зачем нужны указатели? Например почему лучше нужно объявлять переменные как указатели, почему как обычно нельзя? ...

Зачем нужны классы? - C++
Изучаю СИ++ после изучения СИ. Не пойму какой смысл в классах. То что они делают можно реализовать с помощью функций, структур и обычных...

Зачем нужны итераторы? - C++
Практическое использование мне понятно - с их помощью обходят контейнеры и т.д и т.п.Но почему не реализовать нужные методы,перегрузить...

Зачем нужны header-файлы - C++
Здравствуйте хотелось бы узнать ,в чем заключается смысл этих самых header файлов ?


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

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

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