Алгоритмы на линейных структурах: алгоритмы сортировки

Дисциплина «Алгоритмы и структуры данных» Лекция № 8 Алгоритмы на линейных структурах: алгоритмы сортировки. Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Задача сортировки Некоторые из наиболее важных применений сортировки: 1) Решение задачи "группировки", когда нужно собрать вместе все элементы с одинаковым значением некоторого признака. Допустим, имеется 10000 элементов, расположенных в случайном порядке, причем значения многих из них равны; и нам нужно переупорядочить эту последовательность так, чтобы элементы с равными значениями занимали соседние позиции в ней. 2) Пересечение множеств. Если две или более последовательности отсортированы в одном и том же порядке, то можно отыскать в них все общие элементы за один последовательный просмотр без возвратов. Сортировка позволяет использовать последовательный доступ к большим последовательностям в качестве приемлемой замены прямой адресации. 3) Поиск элемента в упорядоченной последовательности возможен за O(logN) 3) Наглядное представление результатов, например в алфавитном порядке. Задача сортировки Для заданной последовательности a1, a2, …, an найти перестановку её элементов в таком порядке a'1, a'2, … ,a'n, что при заданной функции f справедливо отношение: f(a'1)  f(a'2)  …  f(a'n) Функция упорядочивания f(x) не вычисляется, а содержится в каждом элементе в виде явной компоненты. Её значение называют ключом элемента, а саму компоненту элемента – ключом сортировки. Задача сортировки Отношение порядка "<" на множестве ключей вводится таким образом, чтобы для любых трех значений ключей a, b, c выполнялись следующие условия: 1) справедливо одно и только одно из соотношений a < b, a = b, a > b (закон трихотомии); 2) если a < b, b < c, то a < c (закон транзитивности). Эти два свойства определяют математическое понятие линейного "упорядочивания", называемого еще "совершенным упорядочиванием". Любое множество с отношением "<" удовлетворяющим свойствам 1 и 2, поддается сортировке большинством методов, которые будут рассмотрены, хотя некоторые из них годятся только для числовых и буквенных ключей с обычным отношением порядка. Типы сортировки • Внутренняя – все элементы находятся в оперативной памяти машины • Внешняя – массив данных настолько велик, что в ОЗУ машины может храниться только лишь часть данных, остальные хранятся во внешней памяти • Устойчивая сортировка – сохраняет относительный порядок размещения элементов в массиве, содержащем дублированные ключи (Сортировка называется устойчивой, если она удовлетворяет дополнительному условию, что записи с одинаковыми ключами остаются в прежнем порядке) Основные характеристики • Время – характеристика вызывающая наибольший интерес • Отдельные операции (сравнение, обмен) • Дополнительный объем оперативной памяти, используемый алгоритмом – In place (без привлечения дополнительной памяти) – Требующие память для размещения еще одной копии массива – С использованием места для размещения указателей или индексов массивов (служебные поля) Классификация сортировок 1) Обменная сортировка. Если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. 2) Сортировка вставками. Элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. 3) Сортировка посредством выбора. Сначала выделяется наименьший (наибольший) элемент и каким-либо способом отделяется от остальных, затем выбирается наименьший (наибольший из оставшихся) и т.д. 4) Сортировка слиянием. Две (или более) упорядоченные последовательности объединяются в одну упорядоченную последовательностью путем последовательного сравнения «крайних» элементов. Таким образом объединение последовательностей в одну происходит за линейное время от общего числа элементов (за одним просмотр) 5) Сортировка подсчетом. Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших ключей. Классификация сортировок 1) Обменная сортировка. Если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. • «Пузырьковая» сортировка от O(N) до O(N2); • «Быстрая» сортировка Хоара (“quicksort”) от O(Nlog(N)) до O(N2) 2) Сортировка вставками. 3) Сортировка посредством выбора. 4) Сортировка слиянием. 5) Сортировка подсчетом. Классификация сортировок 1) Обменная сортировка. 2) Сортировка вставками. Элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. • Простая вставка (сортировка карт «на руке») – O(N2) • Сортировка на основе бинарного поиска Поиск места для вставки на основе алгоритма бинарного поиска делением отрезка пополам O(Nlog(N)) + Сдвиг: освобождение места под вставку элемента в массиве – O(N2) • сортировка Шелла O(N1,6667) 3) Сортировка посредством выбора. 4) Сортировка слиянием. 5) Сортировка подсчетом. Классификация сортировок 1) Обменная сортировка. 2) Сортировка вставками. 3) Сортировка посредством выбора. Сначала выделяется наименьший (наибольший) элемент и каким-либо способом отделяется от остальных, затем выбирается наименьший (наибольший из оставшихся) и т.д. • Простой выбор («МинМакс») O(N2) • пирамидальная сортировка O(Nlog(N)) 4) Сортировка слиянием. 5) Сортировка подсчетом. Классификация сортировок 1) Обменная сортировка. 2) Сортировка вставками. 3) Сортировка посредством выбора. 4) Сортировка слиянием. Две (или более) упорядоченные последовательности объединяются в одну упорядоченную последовательностью путем последовательного сравнения «крайних» элементов. Таким образом объединение последовательностей в одну происходит за линейное время от общего числа элементов (за одним просмотр) • Фиксированное двухпутевое слияние O(Nlog(N) • Естественное двухпутевое слияние от O(N) до O(Nlog(N) ) 5) Сортировка подсчетом. Классификация сортировок 1) Обменная сортировка. 2) Сортировка вставками. 3) Сортировка посредством выбора. 4) Сортировка слиянием. 5) Сортировка подсчетом. Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших ключей. • «Сравнение и подсчет» O(N2) • «Распределяющий подсчет» O(M+N) Программная реализация алгоритмов сортировки Вспомогательные функции и главная программа #include #include template void swap(Item& A, Item& B) { Item t=A; A=B; B=t; } template int ifSwap(Item& A, Item& B) { if(B void sort(Item a[], int L, int R) { for(int i=L+1; i <= R; i++) for(int j = i; j > L; j--) ifswap(a[j-1], a[j]); } • L, R – индексы начального и конечного элементов сортируемого массива (левая и правая граница диапазона индексов массива) • i – номер первого не отсортированного элемента • j – номер текущей позиции в отсортированной части массива Сортировка вставками template void sort(Item a[], int L, int R) { for(int i=L+1; i <= R; i++) for(int j = i; j > L; j--) ifswap(a[j-1], a[j]); } 10 3 335 33 355 217 536 3 10 335 33 355 217 536 3 10 335 33 355 217 536 3 10 33 335 355 217 536 3 10 33 335 355 217 536 3 10 33 217 335 355 536 3 10 33 217 335 355 536 • Среднее число операций на i шаге: (0+i-1)*i/2/i = (i-1)/2 • Всего: (i-1)/2=(n-2)(n-1)/2= O(n2) Сортировка вставками (улучшение 1) template void sort(Item a[], int L, int R) { for(int i=L+1; i <= R; i++) for(int j = i; j > L; j--) ifswap(a[j-1], a[j]); } 1. Поскольку левый подмассив отсортирован, внутренний цикл можно завершить раньше Сортировка вставками (улучшение 2) template void sort(Item a[], int L, int R) { for(int i=L+1; i <= R; i++) for(int j = i; j > L; j--) if(! ifswap(a[j-1], a[j]) break; } } 2. Операцию обмена во внутреннем цикле следует заменить на операции сдвига. Сортировка Шелла template void sort(Item a[], int L, int R) { for(int N=L-R+1, h = N/2; h>0; h/=2) for(int i=L+1; i <= R; i++) for(int j = i; j > L; j--) ifswap(a[j-1], a[j]); } Сортировка Шелла 6 7 8 3 2 9 0 5 1 6 7 8 3 2 9 0 5 1 N / 2 | + h=N/2 2 7 0 3 6 9 8 5 1 2 7 0 3 1 9 8 5 6 1 7 0 3 2 9 8 5 6 h=h/2 Сортировка Шелла template void sort(Item a[], int L, int R) { for(int h=1; h<=(r-l)/3; h=3*h+1); for(int N=L-R+1, h = N/2; h>0; h/=2) for(int i=L+h; i <= R; i++) for(int j = i; j > L; j--) ifswap(a[j-1], a[j]); } Сортировка Шелла template void sort(Item a[], int L, int R) { for(int h=1; h<=(r-l)/3; h=3*h+1); for(int N=L-R+1, h = N/2; h>0; h/=2) for(int i=L+h; i <= R; i++) for(int j = i; j > L; j-=h) ifswap(a[j-h], a[j]); } Сортировка Шелла template void sort(Item a[], int L, int R) { for(int h=1; h<=(r-l)/3; h=3*h+1); for(h=h ; h>0; h/=3) for(int i=L+h; i <= R; i++) for(int j = i; j > L; j-=h) ifswap(a[j-h], a[j]); } Сортировка методом Шелла template void shell(Item a[], int l, int r) { for(int h=1; h<=(r-l)/3; h=3*h+1 h=3*h+1); for(;h>0; h/=3) for(int i=l+h;i<=r;i++) { int j=i; Item v=a[i]; while( j>=l+h && v void bubble(Item a[], int l, int r) { for(int i=l; ii; j--) ifswap(a[j-1],a[j]); } 564 41 165 815 685 764 827 Сортировка методом «пузырька» template void bubble(Item a[], int l, int r) { for(int i=l; ii; j--) ifswap(a[j-1],a[j]); } 564 41 165 815 685 764 827 41 564 165 685 815 764 827 41 165 564 685 764 815 827 41 165 564 685 764 815 827 41 165 564 685 764 815 827 41 165 564 685 764 815 827 41 165 564 685 764 815 827 Число операций: n*(n-1)/2 Сортировка методом «пузырька» template void bubble(Item a[], int l, int r) { for(int i=l; ii; j--) ifswap(a[j-1],a[j]); } 1. Выход из внешнего цикла можно производить при отсутствии обменов во внутреннем цикле 2. Не эффективна в работе с уже частично упорядоченными массивами 51234 Сортировка методом «пузырька» template void bubble(Item a[], int l, int r) { for(int i=l; i i; j--) flag = ifswap(a[j-1],a[j]); if (!flag) break; // обменов не было } Быстрая сортировка Хоара aix l … i aj≥x j • l,r – левая и правая границы • I,j – левый и правый указатели • x = a[r] – разделяющий элемент x r Быстрая сортировка Хоара template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } Быстрая сортировка Хоара 623 3 787 268 461 386 376 template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 581 603 279 Быстрая сортировка Хоара 268 3 787 623 461 386 376 template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 581 603 279 Быстрая сортировка Хора 268 3 279 623 461 386 376 template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 581 603 787 Быстрая сортировка Хоара 3 268 279 623 461 386 376 template void quicksort(Item a[], int l, int r) { int I = l-1, j=r; Item x = a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 581 603 787 Быстрая сортировка Хоара 3 268 279 623 461 386 376 template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 581 603 787 Быстрая сортировка Хоара 3 268 279 581 461 386 376 template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 623 603 787 Быстрая сортировка Хоара 3 268 279 581 461 386 376 template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 603 623 787 Быстрая сортировка Хоара 3 268 279 376 461 386 581 603 template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j)break; exch(a[i],a[j]); } exch(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 623 787 Быстрая сортировка Хоара 3 268 279 376 386 461 581 template void quicksort(Item a[], int l, int r) { int i=l-1,j=r; Item x=a[r]; for(;;) { while(a[++i]=j) break; swap(a[i],a[j]); } swap(a[i],a[r]); if(lr) quicksort(a,i+1,r); } 603 623 787 Оценки производительности • Наихудший случай (например, файл уже отсортирован): выполняет примерно О(N2/2) сравнений – Первый шаг: N сравнений и вызов для N-1 элемента – Второй шаг: N-1 сравнение и т.д. – Всего N + (N-1) + … + 1 = N(N+1)/2 Оценки производительности • Наилучший случай: на каждой стадии разбиения файл делится пополам: CN = 2CN/2 + N = N + 2(2CN/4 + N/2) = N + N + 4(2CN/8 + N/4) = = O(NlgN) Сортировка выбором template void slct(Item a[],int l,int r) { for(int i=l;i void slct(Item a[], int l, int r) { for(int i=l;i void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void mergesort(Item a[], int l, int r) { if(r<=l) return; int m=(r+l)/2; mergesort(a,l,m); mergesort(a,m+1,r); O(N log N) merge(a,l,m,r); } Нисходящая сортировка слиянием a 10 3 335 33 355 217 536 195 700 949 l=0 template void mergesort(Item 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); } r=9 Mergesort(0,9) Mergesort(0,2) Mergesort(0,4) Mergesort(5,9) Mergesort(3,4) Merge(0,2,4) Mergesort(0,1) Mergesort(0,0) Mergesort(1,1) Merge(0,0,1) Mergesort(2,2) Merge(0,1,2) Merge(0,4,9) Нисходящая сортировка слиянием a 10 3 l=0 335 33 355 217 536 195 700 949 m=0 r=1 aux 10 3 template void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void merge(Item a[], int l, int m, int r) { int i,j; static Item aux[maxN]; for(i=m+1;i>l;i--) aux[i-1]=a[i-1]; for(j=m;j void fixDown(Item a[],int k,int N) { while(2*k<=N) { int j=2*k; if(j void heapsort(Item a[],int l,int r) { int N=r-l+1; Item* pq=a+l-1; for(int k=N/2; k>=1; k--) fixDown(pq,k,N); while(N>1) { swap(pq[1],pq[N]); fixDown(pq,1,--N); } } Спасибо за внимание!