Сортировка массива - Форум


Корейская косметика

Сортировка массива
  • dianondianon
    May 2011 +1 -1
    Сообщений: 114
    Я так и не могу отличить сортировки друг от друга, соответственно, не могу узнать их эффективность. Скажите, это сортировка пузырьком? Если нет, то какая?

    for i:=1 to N-1 do
    for j:= 1 to N-i do
    begin
    if A[j] < A[j+1] then
    begin
    k:=A[j];
    A[j]:=A[j+1];
    A[j+1]:=k;
    end;
    end;
  • kvakva13kvakva13
    May 2011 +1 -1
    Сообщений: 266
    пузырьком это, мог бы и спросить в треде по информатике.
  • dianondianon
    May 2011 +1 -1
    Сообщений: 114
    А вот это какая?

    1:b:=false;
    for i:=1 to N-1 do
    begin
    if A[i] begin
    j:=A[i+1];
    A[i+1]:=A[i];
    A[i]:=j;
    b:=true;
    end;
    end;
    if b=true then goto 1;

    Просто я сначала думал, что это пузырьком, а потом написал ту и засомневался.
  • kvakva13kvakva13
    May 2011 +1 -1
    Сообщений: 266
    тоже она, но модернизированная
  • kvakva13kvakva13
    May 2011 +1 -1
    Сообщений: 266
    Оно же, но без goto
    repeat
    b := false;
    for j:=N-1 downto 1 do
    if A[j] > A[j+1] then begin
    с := A[j];
    A[j] := A[j+1];
    A[j+1] := с;
    b := true;
    end;
    until not b;
  • dianondianon
    May 2011 +1 -1
    Сообщений: 114
    А по эффективности они оба одинаковыми будут считаться?
  • aklag
    May 2011 +1 -1
    Сообщений: 152
    dianon, эффективность сортировки никогда не оценивалась. просто есть задачи, где она не нужна совсем. и если ее применить, то баллы снизят. а есть задачи, гда она нужна, но на меньшем массиве, чем кто-то написал и тогда тоже снизят. а сами алгоритмы сортировки не играют роль (в егэ, на олимпиадах - играют)
  • dianondianon
    May 2011 +1 -1
    Сообщений: 114
    У Полякова сказано, что за совсем неэффективный алгоритм, ON^3, например, баллы снизят. Конечно, какую-нибудь быструю сортировку не требуют, пузырька хватит. В критериях тоже что-то сказано про эффективность.
  • aklag
    May 2011 +1 -1
    Сообщений: 152
    dianon, про эффективность в критериях обязательно говорится, НО эффективность алгоритма в целом и эффективность методов сортировки - это не одно и то же. говорю же - снимут баллы, если сделана сортировка (неважно как), а можно было совсем без нее
  • Osnik
    May 2011 +1 -1
    Сообщений: 54
    Оба кода одинаковые, просто использованы разные циклы. И почитайте алгоритм(Текстовый) на википедии и один раз сделайте самостоятельно, а не копируйте чужой код.

    aklag
    Я кстати очень слабо представляю случай, когда нужно, что-то сортировать, а сортировка не нужна. Ну если элемента в массиве не три штуки.
  • kvakva13kvakva13
    May 2011 +1 -1
    Сообщений: 266
    На вход программе подается последовательность цифр, заканчивающаяся точкой (другие символы, кроме цифр и точки, отсутствуют). Требуется написать программу, которая выводит цифры, встречающиеся во входной последовательности, в порядке увеличения частоты их встречаемости. Если какие-то цифры встречаются одинаковое число раз, они выводятся в порядке возрастания. Например, если исходная последовательность была такая:
    123124456.
    то результат должен быть следующий:
    356124

    Вот тут сортировка будет считать неэффективным методом?
  • aklag
    May 2011 +1 -1
    Сообщений: 152
    Osnik, 1й пример. нужно найти 3 лучших (худших) по баллам. если взять всех и сортировать - баллы снимут, сразу запоминать и переприсваивать трех - не снимут. 2й пример. вводятся цифры и потом из них сформировать наибольшее (наименьшее) число. если все цифры запоминать в большом массиве и потом сортировать - снимут, если сделать маленький массив с индексом из этих цифр - не снимут.
    тому, кто это сразу понимает, и в голову не придет сортировку делать. поэтому и удивление у тебя. а есть такие, кто упорно сортирует
  • aklag
    May 2011 +1 -1
    Сообщений: 152
    kvakva13, спасибо за наглядный пример. здесь сортировка уместна, но только для массива из 10 элементов с индексами-цифрами - не надо запоминать всю длинную входную цепочку, а считать только кол-во для каждой цифры.
  • dianondianon
    May 2011 +1 -1
    Сообщений: 114
    Ага, то есть, если уместна сортировка, то можно делать любым способом?
    Osnik, ты такой сумбурный, петушок. Знаки препинания только в программах используешь, нэ?
    Алсо, ты мне напомнил:
    "И почитаеш алгоритм
    И делаеш ее самостоятельно
    Ну ты понел"
  • aklag
    May 2011 +1 -1
    Сообщений: 152
    dianon, ну конечно. если в самом задании сказано вывести по возрастанию(убыванию) значит д.б. сортировка. если этого в явном виде нет, сильно сомнительно, что ее можно исп-ть без потери баллов. а какая именно сортировка - не важно (если правильно отсортирован)
  • Osnik
    May 2011 +1 -1
    Сообщений: 54
    dianon :facepalm:

    aklag said:

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


    Хм, если пересортировать этот массив, ассоциации цифр с их количеством, потеряются. Если я правильно понял алгоритм. Индекс измениться.
  • dianondianon
    May 2011 +1 -1
    Сообщений: 114
    Индекс измениться моя твоя понимать.
    Ничего там не изменится, если задать массив из целых чисел с идентификаторами ячеек из букв, а не два массива разных. Да и тогда можно просто одновременно их переставлять при сортировке.
  • dianondianon
    May 2011 +1 -1
    Сообщений: 114
    Алсо, сначала прочитал твой ник, как "ОМСК". Неспроста, видимо, лол.
  • aklag
    May 2011 +1 -1
    Сообщений: 152
    Osnik, да, спасибо. в первоначальном посте у меня все верно было, а потом зачем-то... sorry, sorry, нужно два 10элементных массива. ну, или один двумерный
  • kvakva13kvakva13
    May 2011 +1 -1
    Сообщений: 266
    aklag said:

    Osnik, да, спасибо. в первоначальном посте у меня все верно было, а потом зачем-то... sorry, sorry, нужно два 10элементных массива. ну, или один двумерный


    Двумерный будет менее эффективным. 10*10=100, 10+10=20
    Скорее всего, ты имел в виду записи.
  • aklag
    May 2011 +1 -1
    Сообщений: 152
    kvakva13, двумерный размером 2*10, а не 10*10. ну, ясно же
  • Osnik
    May 2011 +1 -1
    Сообщений: 54
    aklag said:

    Osnik, да, спасибо. в первоначальном посте у меня все верно было, а потом зачем-то... sorry, sorry, нужно два 10элементных массива. ну, или один двумерный



    Можно обойтись одним массивом.
    Делаем переменную, изначально равную 1. Проходим циклом по массиву С КОНЦА, если встречается единица, выписываем эту цифру(Индекс), и начинаем цикл заново. Если единица не встретилась, инкрементируем переменную. И так, пока переменная не стала равной максимальному элементу.
    Всяко лучше, чем сортировать двумерный массив.
    И вообще лучше использовать не двумерный массив, а структуру. С ней легче работать. По крайней мере не запутаешься в элементах.