ДС17о10-Сортировки (1238905)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Carnegie MellonСортировкиАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция10, 14ноября,2017Лектор:ДмитрийСеверов,кафедраинформатики608КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Сортировки§ Введение§ Простые:O(n2)§ Сложные:O(n·log n)2ЗадачасортировкиДлянекоторойпоследовательностиa1,a2,…,anнайтиперестановкуеёэлементоввтакомпорядкеa'1,a'2,… ,a'n,чтопризаданнойфункцииfсправедливоотношение:f(a'1)£ f(a'2)£ …£ f(a'n)¢¢Функцияупорядочиванияf(x)вычисляетсянеприкаждомсравнении,аоднаждыисодержится вкаждомэлементеввидеявнойкомпоненты– ключа3ТипысортировкиВнутренняя§ всеэлементынаходятсявпамятимашины¢ Внешняя§ массивданныхнастольковелик,чтовОЗУ¢машиныможетхранитьсятольколишьчастьданных¢Устойчивая§ сохраняетпорядокразмещенияэлементоввмассиве,содержащемодинаковыеключи4ОсновныехарактеристикиВремя– характеристикавызывающаянаибольшийинтерес¢ Дополнительныйобъемоперативнойпамяти,используемыйалгоритмом1.

Нетребуется(Inplace);2. Дляразмещенияуказателейилииндексов¢массивов;3. Дляразмещенияещеоднойкопиимассива.5Вспомогательныесредства#include <iostream>#include <cmath>#include <iomanip>using namespace std;const int N = 10;unsigned long long start, end;unsigned long long access_counter(){ asm("rdtsc"); }void init(int a[],int l,int r) {for(int i=l;i<=r;i++) a[i]=rand(); }void init(double a[],int l,int r){double h=2.*M_PI/(r-l);for(int i=l;i<=r;i++) a[i]=sin(h*i); }6template <typename T>void print(T a[], int l, int r) {for(int i=l;i<=r;i++)cout << a[i]<< (i==r?'\n':' ');}template <typename T>void exch(T& A, T& B) {T t=A; A=B; B=t;}template <typename T>bool compexch(T& A, T& B) {if(B<A) { exch(A,B); return true;} else return false;}7Простыесортировки:О(n2)1.2.3.4.5.СортировкавставкамиСортировкавыборомСортировкапузырькомГномья сортировкаШейкерная сортировка8Сортировкавставкамиtemplate <typename T>void insert(T a[], int l, int r) {for(int i=l+1;i<=r;i++)for(int j=i;j>l;j--)if(!compexch(a[j-1],a[j]))break;}9Сортировкавыборомtemplate <typename T>void slct(T a[], int l, int r) {for(int i=l;i<r;i++) {int min=i;for(int j=i+1;j<=r;j++)if(a[j]<a[min]) min=j;exch(a[i],a[min]); }}10Гномья сортировка[цветочныхгоршков]Еслинетгоршкасзади,тошагаетвперёд.Еслигоршкивпередиисзадистоятверно,тошагаетвперёд,иначеменяетгоршкиместамиишагаетназад.Еслинет горшкавпереди,тоостанавливается.11Гномья сортировкаtemplate <typename T>void dwarf(T a[],int l,int r) {int i=l;while(i<r)if(!compexch(a[i],a[i+1]) || i==l) i++;else i--;}12Сортировкапузырькомtemplate <typename T>void bubble(T a[], int l, int r) {int b=1;for(int i=l;(i<r) && b; i++){ b=0;for(int j=r; j>i; j--)b = compexch(a[j-1],a[j])||b;}}13Шейкерная сортировкаtemplate < typename T >void shaker(T a[], int l, int r) {do {for(j=k=r;j>l;j--)if(compexch(a[j-1],a[j])) k=j;l=k;for(j=k=l+1;j<=r;j++)if(compexch(a[j-1],a[j])) k=j;r=k-1;}while(l<r);}14СложныесортировкиСвойства§ ВсреднемO(nlogn)§ ВозможнадеградациядоО(n3/2)идажеО(n2)§ Невсегда«inline»¢Шелла¢Быстрая(Хоара)¢Слиянием¢Пирамидальная¢15СортировкаШелла(вставканесоседних)template <typename T>void shell(T a[], int l, int r) {int h;for(h=1; h<=(r-l)/3; h=3*h+1);for(;h>0; h/=3)for(int i=l+h;i<=r;i++) {int j=i; T v=a[i];while( j>=l+h && a[j-h]>v ) {a[j]=a[j-h]; j-=h; }a[j]=v; }}1 4 13 40 121 364 1093 3280 9841 … ~O(N3/2)16СортировкаШелла123456789101112131415EUHIKGKB M YAKBBG4BGHIKGKB M YAKBEUh=13BEABBGHIKGKK M YUh=4ABBBEGGHIKKK M UY<i+1: 1 8 23 77{ 281for(inti=l+h;i<=r;i++)int j=i;T v=a[i];4i+1 + 3*210734193 … O(N4/3)while(j>=l+h&&a[j-h]>v){a[j]=a[j-h];j-=h;}2i: a[j]=v;1 2 }4 16 32 64 128 …O(N2)17СортировкаШелла123456789101112131415EUHIKGKB M YAKBBG4BGHIKGKB M YAKBEUh=13BEABBGHIKGKK M YUh=4ABBBEGGHIKKK M UY<4i+1 + 3*2i+1: 1 8 23 77 281 1073 4193 … O(N4/3)2i:1 2 4 16 32 64 128 …O(N2)18Быстраясортировка(Хоара)template <typename T>void quicksort(T a[],int l,int r) {int i=l-1,j=r; T x=a[r];for(;;) {while(a[++i]<x);while(x<a[--j]) if(j==l) break;if(i>=j)break;exch(a[i],a[j]);}exch(a[i],a[r]);if(l<i-1) quicksort(a,l,i-1);if(r>i+1) quicksort(a,i+1,r); }19Сортировкаслияниемtemplate <typename T>void merge(T a[],int l,int m,int r){int i,j; static T aux[N];for(i=m+1;i>l;i--) aux[i-1]=a[i-1];for(j=m;j<r;j++) aux[r+m-j]=a[j+1];for(int k=l;k<=r;k++)a[k]=aux[j]<aux[i]?aux[j--]:aux[i++];}template <typename T>void mergesort(T a[],int l int r) {if(r<=l) return; int m=(r+l)/2;mergesort(a,l,m); mergesort(a,m+1,r);merge(a,l,m,r); }20Бинарноесортирующеедерево(куча)1.

Ключузланеменьшеключейсправаислева.2. Разницаглубинлистьевнеболее13. Последнийслойзаполняетсяслеванаправобезпустот89972544826121Структураданныхкучи¢Индексыузловвмассиве12n2n42n+158123345961078611971210111222Действияскучей¢Точечноеисправлениекучи:O(log n)§ ПонеобходимостипоменятьузелспотомкомиисправитьнижеПостроениекучи:O(n)§ Исправлениемассивадокучисправаналево¢ Удалениемаксимального:O(log n)§ Поменятьпервыйспоследним,укоротить,исправить¢ Пирамидальнаясортировка:O(n log n)§ Удалитьвсемаксимальныепоочереди¢23Пирамидальнаясортировкаtemplate <typename T>void fixDown(T a[],int k,int N) { int j;while((j=2*k)<=N) {if(j<N && a[j]<a[j+1]) j++;if(!compexch(a[j],a[k])) break;k=j; } }template <typename T>void heapsort(T a[],int l,int r) {int N=r-l+1; T* pq=a+l-1;for(int k=N/2;k>=1;k--) fixDown(pq,k,N);while(N>1) { exch(a[0], pq[N]);fixDown(pq,1,--N); } }24Построениекучи774212594149212628959421224482199561279819762544826125Исходныймассив7412596129428975862442197586244212Исходнаякуча1292массив1919997254487629452148622куча979458621421226272829303132Пример:Сортировкастрок3334353637Библиотечнаяфункцияqsortvoid qsort(void* a, size_t n, size_t s,int (*comp)(const void*, const void*))здесьa – имясортируемогомассиваn – количествоэлементовas – размерностьодногоэлемента(*comp) – указательнафункциюсравнения>0, если >=0,если ==<0, если <38int comp(const void* i,const void* j){double r = *(double*)i-*(double*)j;return r>0?1:(r<0?-1:0);}int main() {init(a);qsort(a,N,sizeof(double),comp);return 0;}39.

Характеристики

Тип файла PDF

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

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

Список файлов лекций