Задачи сортировки
план-конспект по информатике и икт по теме

Тема урока: Задачи сортировки.

 Цель урока:

                Сформировать у учащихся понятие сортировки пузырьком и быстрая сортировка. 

 Задачи урока:

                     1. Сортировка пузырьком.

                     2. Быстрая сортировка.

  Оборудование урока: компьютер, проектор.

План  урока.

1. Организационный момент.

           -Здравствуйте, садитесь. Кто сегодня отсутствует?

2. Изучение нового материала.

Задачи сортировки

    Сортировка, это большая и важная группа задач. Задач этого типа так много, что иногда можно услышать мнение, о том, что только на этих задачах можно научиться программированию. Рассмотрим только одну задачу, и на ней  изучим два алгоритма. В общем, задачу сортировки можно сформулировать так: дано множество однородных объектов, требуется расположить их в определенном порядке. Например, дано множество людей, требуется расположить их в порядке родства. Например, дано множество предложений русского языка, разбить их на группы по смыслу.

    Задача 1. Упорядочение по возрастанию числового множества.

            Из условия задачи видно, что есть некоторое множество чисел, которое вводится извне а, что в нём за числа и в каком они порядке расположены ничего не известно, кроме, быть может, их типа. Надо над этим множеством выполнить алгоритм, по завершению которого, в этом множестве останутся те же числа, что были в нём и до обработки, но теперь они будут располагаться в порядке возрастания значений.

    Сортировка пузырьком. Представьте себе столбик чисел, в котором меньшее число, как бы обладает меньшей массой и, следовательно, может всплывать вверх. Тогда самые маленькие будут самыми легкими, как пузырьки воздуха в более тяжелой воде и как пузырьки они будут стремиться всплывать вверх. Процесс такого перераспределения, чисел называется «сортировка пузырьком».

    Конечно, сами по себе числа не могут всплывать, это только общий принцип, а сейчас нам нужен алгоритм. Начнём с нескольких общих соображений. Множество чисел, придётся представить в виде массива. Назовем пару последовательных чисел правильной, если первое число пары меньше второго, назовём пару чисел неправильной, если первое число больше второго.

    Исходя из понятий правильной и неправильной пар, можно упорядоченный массив определить, как массив, в котором любая пара чисел является правильной или наоборот нет ни одной неправильной пары.

    Отсюда появляется и алгоритмическая идея: пройдем весь массив и просмотрим все пары чисел (первое и второе), (второе и третье) и т.д. И на каждом шаге если найдена неправильная пара, то её элементы меняются местами.

    Видимо за один проход упорядочить массив не получится. Возникает вопрос – сколько раз нужно пройти массив до полного упорядочения.      Представим себе наихудшую ситуацию – пусть в массиве самое маленькое число находится в конце массива, а всего в массиве N – чисел. За один проход это самое маленькое число сместится в направлении начала на одну позицию, и за каждый проход оно будет смещаться только на одну позицию. В начале процесса наше маленькое число находилось в позиции N, а в конце оно должно переместиться на позицию с номером 1. Простая арифметическая операция говорит, что для этого достаточно N проходов массива. Теперь запишем  алгоритм.

1. Ввести массив из N элементов
2. N – раз делать
3. Для всех элементов от 1 до N - го делать
4. Сравнить текущий элемент и следующий
5. Если текущий элемент больше следующего То
6. Текущий элемент и следующий меняются местами.
7. Распечатать значения массива

    Этот алгоритм, реализует метод пузырька, но наш алгоритм не самый эффективный. Его можно существенно улучшить. Вспомним еще раз наш плохой случай, когда самое маленькое число в самом конце. После первого прохода массива самое маленькое число из позиции N сместится в позицию N-1. Это означает, что на втором проходе просматривать до N – ой позиции уже не надо, там наименьшего элемента уже нет.

    Ниже приведен текст программы.  Это хорошая работающая программа, но в ней есть две неточности, которые позволяют повысить скорость её работы. Обе неточности находятся в записи заголовков циклов. Попробуйте их найти.

program example;

 uses crt;

 var

  a:array[1..100] of integer;

  i,n,j,c:integer;

begin

 read(n);

 for i:=1 to n do

  read(a[i]);

 for i:=1 to n do

  for j:=1 to n-1 do

   if a[j]>a[j+1] then

    begin

     c:=a[j];a[j]:=a[j+1];a[j+1]:=c;

    end;

 clrscr;

 for i:=1 to n do

  writeln(a[i]);

end.

    Быстрая сортировка. Самая главная проблема любого алгоритма сортировки это большое количество операций, которые требуются алгоритму для выполнения своей работы. Например, алгоритму пузырька (в том виде, как он приведен) требуется N*(N-1) операций для той части программы, которая собственно занимается упорядочиванием. При N = 1000 чисел, что совсем немного, потребуется почти миллион операций, что уже заметно. При сортировке больших массивов, таких которые могут получаться в результате какой-либо реальной человеческой деятельности, например, при сборе статистики в масштабах большой страны, потребуется обработка многомиллионных массивов, что может потребовать больших машинных ресурсов. Машинные ресурсы стоят дорого, поэтому стоит подумать о более быстрых алгоритмах. Одним из таких алгоритмов является алгоритм быстрой сортировки. Его идея следующая.

program example;

 uses crt;

  type

    shablon=array[0..100] of integer;

  var

   a:shablon;

   n,i,left,right:integer;

function sort(var mas:shablon;left,right:integer):integer;

 var

  c,i,j,barrier,m:integer;

begin

 m:=(left+right) div 2;

 barrier:=mas[m];

 i:=left;j:=right;

 repeat

  while mas[i]

  while mas[j]>barrier do j:=j-1;

  if (i<=j) then

    begin

     c:=mas[i];mas[i]:=mas[j];mas[j]:=c;

     i:=i+1;j:=j-1;

    end;

 until i>j;

 sort:=j;

end;

procedure quick(var mas:shablon;left,right:integer);

 var

  i,ind:integer;

begin

 ind:=sort(mas,left,right);

 if right-left>2 then

 begin

 if ind>left then quick(mas,left,ind);

 if ind+1 < right then quick(mas,ind+1,right);

 end;

end;

begin

 clrscr;

 read(n);

 for i:=0 to n-1 do

   read(a[i]);

 left:=0;

 right:=n-1;

 quick(a,left,right);

 for i:=0 to n-1 do

   write(a[i],' ');

end.

3.Домашнее задание.

            Повторить изученный материал. Выучить понятия: сортировка пузырьком, быстрая сортировка. Решить задачу: Удобно считать, что числа a[1]…a[n]  и b[1]…b[n]  представляют собой начальное и конечное значение массива х. Требование «а и b содержат одни и те же числа» будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов х.  

4. Подведение итогов:

            Выставление оценок ученикам, которые хорошо работали на уроке