Персональная страничка
Диканева Тараса
Викторовича

Главная \ Преподавательское \ Программирование для начинающих

10. Массивы

Предыдущий раздел:

Следующий раздел:

10.5. Сортировка массивов

Одна из важнейших задач, связанных с массивами – сортировка, то есть расположение элементов массива по возрастанию или убыванию. Пусть есть массив, содержащий 4 элемента:

    x[1] = 0.5, x[2] = 0.75, x[3] = 0.12, x[4] = 0.62.

Сортировка будет заключаться в преобразовании этого массива к виду:

    x[1] = 0.12, x[2] = 0.5, x[3] = 0.62, x[4] = 0.75.

Чаще всего сортировка применяется для последующего поиска. Представьте себе, что вы ищете слово в англо-русском словаре, где слова располагаются в случайном порядке. При наличии сотни тысяч слов задача кажется затруднительной. Однако сортировка по алфавиту радикально облегчает поиск.

Есть и масса других применений.

Существует несколько алгоритмов сортировки. В зависимости от особенностей решаемой задачи эффективней окажется тот или иной алгоритм. Однако если время работы алгоритма не критично, то стоит выбрать тот, который наиболее прост в реализации. Мне таким представляется метод выбора.

Идея следующая. На первом шаге в массиве ищется самый маленький элемент и меняется местами с первым. На втором шаге ищется самый маленький, начиная со второго, и ставится на 2-е место (второй элемент, естественно не забываем – ставим его на место, где раньше был самый маленький). И так далее, на i-м шаге ищется самый маленький, начиная с i-го, и ставится на i-е место. Программную реализацию этого метода оставим для самостоятельной реализации.

Следующий раздел:

Предыдущий раздел:

7 комментариев

  1. asd
    program Project2;
    
    {$APPTYPE CONSOLE}
    
    uses
      SysUtils;
    
    const
      n=10;
    type
      TMass=array [1..n] of integer;
    var
      k,i: integer;
      dt: TMass;
      elm,min, index:integer;
    begin
    // zapolnenie massiva
      for i:=1 to n do
        readln(dt[i]);
    // sortirovka puzirkov
      for i:=1 to n do
      begin
        index:=1;
        for k:=i to n do
        begin
          if dt[k]< dt[index] then
            index:=k
        end;
        elm:=dt[i];
        dt[i]:= dt[index];
        dt[index]:=elm;
      end;
    
      for i:=1 to n do
        write ( dt[i],' ');
    
      readln;
    end.
  2. Taras

    К сожалению, в программу вкралась небольшая ошибка. Уже на втором шаге внешнего цикла результат будет почти наверняка неправильным. Советую пройти второй шаг в режиме отладки, посмотреть, в какой момент что-то пошло не так и, соответственно, разобраться, почему.

    И еще этот алгоритм — сортировка выбором, а не метод пузырька.

  3. Alex_Kot

    Program Sort_10_5; {Сортировка методом выбора}
    const
    n=10;
    type
    TMassiv=array[0..n-1] of integer ;
    var
    x: TMassiv;
    i, k, Kmin, z: integer;
    begin
    for i:=0 to n-1 do
    begin
    x[i]:=trunc(10*random);
    write(x[i]);
    end;
    writeln;
    for i:=0 to n-2 do
    begin
    Kmin:=i;
    for k:=i+1 to n-1 do
    begin
    if x[k]<x[Kmin] then
    Kmin:=k;
    z:=x[Kmin];
    x[Kmin]:=x[i];
    x[i]:=z;
    end;
    write(x[i]);
    end;
    write(x[n-1]);
    end.

  4. Alex_Kot

    Ошибку исправил:
    Program Sort_10_5; {Сортировка методом выбора}
    const
    n=10;
    type
    TMassiv=array[0..n-1] of integer ;
    var
    x: TMassiv;
    i, k, Kmin, z: integer;
    begin
    for i:=0 to n-1 do
    begin
    x[i]:=trunc(10*random);
    write(x[i]);
    end;
    writeln;
    for i:=0 to n-2 do
    begin
    Kmin:=i;
    for k:=i+1 to n-1 do
    begin
    if x[k]<x[Kmin] then
    Kmin:=k;
    end;
    z:=x[Kmin];
    x[Kmin]:=x[i];
    x[i]:=z;
    write(x[i]);
    end;
    write(x[n-1]);
    end.

  5. Alex_Kot

    Так тоже работает:
    Program Sort_10_5; {Сортировка методом выбора}
    const
    n=10;
    type
    TMassiv=array[0..n-1] of integer ;
    var
    x: TMassiv;
    i, k, Kmin, z: integer;
    begin
    for i:=0 to n-1 do
    begin
    x[i]:=trunc(10*random);
    write(x[i]);
    end;
    writeln;
    for i:=0 to n-1 do
    begin
    Kmin:=i;
    for k:=i to n-1 do
    begin
    if x[k]<x[Kmin] then
    Kmin:=k;
    end;
    z:=x[Kmin];
    x[Kmin]:=x[i];
    x[i]:=z;
    write(x[i]);
    end;
    end

  6. Alex_Kot

    В соответствии с правилами «хорошего стиля» результаты 2-х последних программ лучше выводить так:
    x[i]:=z;
    end;
    for i:=0 to n-1 do {ДОРАБОТКА программы 154}
    write(x[i]);
    end.

  7. Ruslan

    program Sort_10_5;
    const
    n=5000;
    type
    TMassive=array [0..n] of real;
    var
    x: TMassive;
    i, ii: integer;
    a: real;
    begin
    for i:=0 to n do
    begin
    x[i]:=random(10000);
    end;

    for i:=0 to n do
    begin
    // if i<n then

    for ii:=0 to n-1 do
    // if iix[ii+1] then
    begin
    a:=x[ii]; x[ii]:=x[ii+1]; x[ii+1]:=a;
    end;
    end;

    end;

    for i:=0 to n do
    writeln (x[i]);
    end.

Добавить комментарий