Лабораторная работа 16-17 (1). Московский политехнический университет

• Название: Московский политехнический университет
• Дата: 28.03.2023
• Размер: 48.23 Kb.
• Имя файла: Лабораторная работа 16-17 (1).docx
• Тип: Лабораторная работа; #1020438

федеральное государственное автономное образовательное учреждение высшего образования




МОСКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

(ВЫСШАЯ ШКОЛА ПЕЧАТИ И МЕДИАИНДУСТРИИ)

(Факультет информационных технологий)
(Институт Принтмедиа и информационных технологий)

Кафедра Информатики и информационных технологий


направление подготовки

09.03.02 «Информационные системы и технологии»

ЛАБОРАТОРНАЯ РАБОТА № 16-17
Дисциплина: Основы алгоритмизации и программирования (первый курс, первый семестр).

Тема: Работа со списками

Выполнил: студент группы 221-721
Худаёров Акромбек Ахмад угли

(Фамилия И.О.)


Дата, подпись ________________ ___________

(Дата) (Подпись)

Проверил: _________________________ ___________

(Фамилия И.О., степень, звание) (Оценка)

Дата, подпись ________________ ___________

(Дата) (Подпись)
Замечания: _________________________________________________________

__________________________________________________________________
Москва2023

Лабораторная работа №16-17
"Алгоритм сортировки «быстрая»"

(продолжительность 4 часа)

Цель: Получить практические навыки разработке алгоритмов и их программной реализации.

1. Краткие теоретические сведения

Быстрая сортировка (англ. quick sort, сортировка Хоара) — один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы O(n log n), что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из n элементов в худшем случае может составить Θ(n^2), на практике этот алгоритм является одним из самых быстрых. Для этого алгоритма применяется рекурсивный метод.

Рекурсией называется ситуация, когда программа вызывает сама себя непосредственно или косвенно (через другие функции).

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

Далее начинаем двигаться от начала массива по возрастающей, а потом от конца массива по убывающей. Цель: переместить в правую часть элементы больше опорного, а в левую – элементы меньше опорного. Если во время движения по возрастающей находится элемент со значением больше опорного, то мы выходим из цикла, прибавляем единицу к индексу элемента, на котором остановились, и переходим к циклу с движением по убывающей. В этом цикле мы остаемся до тех пор, пока не находится элемент со значением меньше опорного.

Как только такой элемент найден, мы отнимаем единицу от его индекса, и меняем значение элемента со значением элемента, на котором мы остановились в предыдущем цикле. Делаем так до тех пор, пока индекс левого элемента (найденного в первом цикле) меньше либо равен индексу правого элемента (найденного во втором цикле). В итоге получаем два подмассива (от начала до индекса правого элемента и от индекса левого элемента до конца). С этими подмассивами мы рекурсивно проделываем все то же самое, что и с большим массивом до тех пор, пока все элементы окончательно не отсортируются.

2. Постановка задачи

Необходимо выполнить и оформить описание следующих пунктов:

1. 
   Сформулировать идею алгоритма
   
2. 
   Выполнить словесное представление алгоритма
   
3. 
   Выполнить полнить представление алгоритма с помощью блок схем с использованием элемента модификации и без него.
   
4. 
   Выполнить программную реализацию алгоритмов на языке С с использованием параметрического цикла и цикла с предусловием.
   

3. Содержание отчета

1. Титульный лист.

2. Название и цель работы.

3. Постановка задачи.

4. Описание выполненных пунктов задания.

5. Листинг программы с комментариями.

Быстрая сортировка (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

 

• 
  разбиение массива относительно опорного элемента;
  
• 
  рекурсивная сортировка каждой части массива.
  

Работает для произвольного массива из n целых чисел.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

int n, a[n]; //n - количество элементов void qs(int* s_arr, int first, int last) {     int i = first, j = last, x = s_arr[(first + last) / 2];        do {         while (s_arr[i] < x) i++;         while (s_arr[j] > x) j--;            if(i <= j) {             if (s_arr[i] > s_arr[j]) swap(&s_arr[i], &s_arr[j]);             i++;             j--;         }     } while (i <= j);        if (i < last)         qs(s_arr, i, last);     if (first < j)         qs(s_arr, first, j); }

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.

1	qs(a, 0, n-1);

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

int partition (int[] array, int start, int end)    {        int marker = start;        for ( int i = start; i <= end; i++ )        {            if ( array[i] <= array[end] )            {                int temp = array[marker]; // swap                array[marker] = array[i];                array[i] = temp;                marker += 1;            }        }        return marker - 1;    }       void quicksort (int[] array, int start, int end)    {        if ( start >= end )        {            return;        }        int pivot = partition (array, start, end);        quicksort (array, start, pivot-1);        quicksort (array, pivot+1, end);    }

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

int partition( T[] m, int a, int b) where T :IComparable {     int i = a;     for (int j = a; j <= b; j++)         // просматриваем с a по b     {         if (m[j].CompareTo( m[b]) <= 0)  // если элемент m[j] не превосходит m[b],         {             T t = m[i];                  // меняем местами m[j] и m[a], m[a+1], m[a+2] и так далее...             m[i] = m[j];                 // то есть переносим элементы меньшие m[b] в начало,             m[j] = t;                    // а затем и сам m[b] «сверху»             i++;                         // таким образом последний обмен: m[b] и m[i], после чего i++         }     }     return i - 1;                        // в индексе i хранится <новая позиция элемента m[b]> + 1 }    void quicksort( T[] m, int a, int b) where T : IComparable// a - начало подмножества, b - конец {                                        // для первого вызова: a = 0, b = <элементов в массиве> - 1     if (a >= b) return;     int c = partition( m, a, b);     quicksort( m, a, c - 1);     quicksort( m, c + 1, b); }    //Пример вызова //double[] arr = {9,1.5,34.4,234,1,56.5}; //quicksort(arr,0,arr.Length-1); //

«С» с использованием лямбда-выражений

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

using System; using System.Collections.Generic; using System.Linq;    static public class Qsort     {         public static IEnumerable QuickSort(this IEnumerable list) where T : IComparable         {             if (!list.Any())             {                 return Enumerable.Empty();             }             var pivot = list.First();             var smaller = list.Skip(1).Where(item => item.CompareTo(pivot) <= 0).QuickSort();             var larger = list.Skip(1).Where(item => item.CompareTo(pivot) > 0).QuickSort();                return smaller.Concat(new[] { pivot }).Concat(larger);         }    //(тоже самое, но записанное в одну строку, без объявления переменных)            public static IEnumerable shortQuickSort(this IEnumerable list) where T : IComparable         {             return !list.Any() ? Enumerable.Empty() : list.Skip(1).Where(                 item => item.CompareTo(list.First()) <= 0).shortQuickSort().Concat(new[] { list.First() })                     .Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).shortQuickSort());         }     }