Персональная страничка
Диканева Тараса
Викторовича
Главная \ Преподавательское \ Программирование для начинающих
Введение
Выбор среды программирования
1. Линейные программы: арифметические операторы, стандартные функции и ввод/вывод в текстовом режиме
2. Логические выражения и условный оператор
3. Цикл с параметром (for)
4. Вычисления с помощью рекуррентных соотношений
5. Вложенные циклы
6. Задачи на перебор вариантов
7. Переменные-флаги
8. Переменная - счетчик событий
9. Циклы while и repeat
10. Массивы
11. Процедуры и функции
12. Двумерные массивы
13. Графика в Паскале
14. Символы, строки, текстовые файлы
15. Записи
16. Указатели

10. Массивы

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

10.4. Примеры программ, работающих с массивами

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

10.6. Хороший стиль при решении задач на массивы

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-е место. Программную реализацию этого метода оставим для самостоятельной реализации.

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

10.6. Хороший стиль при решении задач на массивы

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

10.4. Примеры программ, работающих с массивами

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

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

  1. asd 19.11.2012 в 06:51 
    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 19.11.2012 в 20:12

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

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

  3. Alex_Kot 23.08.2015 в 01:48

    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 23.08.2015 в 10:44

    Ошибку исправил:
    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 23.08.2015 в 12:50

    Так тоже работает:
    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 23.08.2015 в 22:47

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

  7. Ruslan 24.01.2016 в 04:37

    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.

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