Двоичный поиск в упорядоченном массиве 123456789101112131415161718190 134810141621242731333638424450515359 l hm 33 private static int binSearch(int[] data, - презентация

1 Двоичный поиск в упорядоченном массиве l hm 33 private static int binSearch(int[] data, int key) { int l = 0, h = data.length-1; while (l < h) { int m = (l + h) / 2; // (l <= m < h) if (data[m] < key) l = m + 1; else h = m; } return (data[l] == key ? l : -1); } Инвариант цикла: l <= h && «если key == data[k], то l <= k <= h »

2 Сортировки массива 1. Сортировка «пузырьком» public static void bubbleSort(int[] data) { int n = data.length; for (int i = 1; i < n; i++) { for (int j = 0; j < n-i; j++) { if (data[j] > data [j+1]) { int tmp = data[j]; data[j] = data[j+1]; data[j+1] = tmp; }

3 2. Сортировка простыми вставками public static void simpleSort(int[] data) { int i, j; for (i = 1; i < data.length; i++) { int c = data[i]; for (j = i-1; j >= 0 && data[j] > c; j--) { data[j+1] = data[j]; } data[j+1] = c; }

4 3. Сортировка двоичными вставками public static void binInsertSort(int[] data) { int n = data.length; // Длина массива for (int i = 1; i < n; i++) { int c = data[i]; // Вставляемое значение // Организация поиска места для вставки значения c int low = 0, high = i; // Inv : (low <= high) && место для c - внутри data[low:high] while (low < high) { int m = (low+high) >> 1; // low <= m < high if (data[m] < c) low = m+1; else high = m; } // Найдено место вставки - low // Сдвигаем элементы в сторону больших индексов. for (int j = i-1; j >= low; j--) { data[j+1] = data[j]; } // Заносим значение на найденное место data[low] = c; }

5 4. Сортировка Шелла step= step= step= step=1

6 4. Сортировка Шелла public static void ShellSort(int[] data) { int n = data.length; // Длина массива int step = n; // Шаг поисков и вставки int i, j; do { // Вычисляем новый шаг step = step / 3 + 1; // Производим сортировку простыми вставками с заданным шагом for (i = step; i < n; i++) { int c = data[i]; for (j = i-step; j >= 0 && data[j] > c; j -= step) { data[j+step] = data[j]; } data[j+step] = c; } } while (step != 1); } Количество перестановок элементов (по результатам экспериментов со случайным массивом) n = 25n = 1000n = Сортировка Шелла Сортировка простыми вставками млрд.

7 5. Алгоритм слияния упорядоченных массивов public static int[] merge(int[] a, int[] b) { int na = a.length, nb = b.length, nc; int[] c = new int[nc = na + nb]; int ia = 0, ib = 0, ic = 0; while (ia < na && ib < nb) { if (a[ia] < b[ib]) c[ic++] = a[ia++]; else c[ic++] = b[ib++]; } while (ia < na) c[ic++] = a[ia++]; while (ib < nb) c[ic++] = b[ib++]; return c; }

8 Сортировка фон Неймана (слиянием) И так далее…

9 Алгоритм сортировки фон Неймана public static void mergeSort(int[] data) { int n = data.length; // Длина массива int[] altData = new int[n]; // Дополнительный массив int[] from = data, // Указатели "откуда" и "куда" происходит слияние to = altData; int len = 1; // Длина сливаемого фрагмента do { int start = 0; while (start < n) { // Сливаем участки from[start:(start+len-1)] и from[(start+len):(start+2*len-1)] // в to[start:(start+2*len-1)] mergeSection( from, start, Math.min(start+len, n), from, Math.min(start+len, n), Math.min(start+(len<<1), n), to, start); start += (len << 1); } // Меняем направление слияния int[] interm = from; from = to; to = interm; } while ((len <<= 1) < n); // Если после последнего слияния результат оказался "не там", // то переносим результат "куда надо" if (from != data) { mergeSection(from, 0, n, from, n, n, data, 0); }

10 7. Пирамидальная сортировка (сортировка «кучей») И так далее…

11 7. Пирамидальная сортировка (продолжение) И так далее…

12 Алгоритм пирамидальной сортировки public static void heapSort(int[] data) { int n = data.length; // Длина массива buildPyramid: // Построение пирамиды for (int i = 1; i < n; i++) { // Inv: Элементы data[0:i-1] уже образуют пирамиду; int c = data[i]; // "Протаскиваемое" значение int p = i, q; // Индексы для "протаскивания" вверх к вершине do { q = p; if ((p = (q-1) >> 1) >= 0 && data[p] < c) data[q] = data[p]; else { data[q] = c; continue buildPyramid; } } while (true); } meltPyramid: // Постепенное разрушение пирамиды for (int i = n-1; i > 0; i--) { int c = data[i]; data[i] = data[0]; int q, p = 0; // Индексы для протаскивания do { q = p; p = (q << 1) | 1; if (p >= i) { // Вышли за границу пирамиды data[q] = c; continue meltPyramid; } if (p data[p]) p++; if (data[p] > c) data[q] = data[p]; else { data[q] = c; continue meltPyramid; } } while (true); } > 1) >= 0 && data[p] < c) data[q] = data[p]; else { data[q] = c; continue buildPyramid; } } while (true); } meltPyramid: // Постепенное разрушение пирамиды for (int i = n-1; i > 0; i--) { int c = data[i]; data[i] = data[0]; int q, p = 0; // Индексы для протаскивания do { q = p; p = (q << 1) | 1; if (p >= i) { // Вышли за границу пирамиды data[q] = c; continue meltPyramid; } if (p data[p]) p++; if (data[p] > c) data[q] = data[p]; else { data[q] = c; continue meltPyramid; } } while (true); }">

13 8. Быстрая сортировка l h

14 Дополнения и улучшения алгоритма Первый элемент в сортируемом куске выбирается случайно и запоминается; Участки, меньшие определенного размера, сортируются простыми способами; Иногда исключение рекурсивных вызовов приводит к повышению эффективности.

15 public static void quickSort(int[] data) { quickSort(data, 0, data.length-1); } private static void quickSort(int[] data, int from, int to) { if (to-from < 50) // Небольшие фрагменты быстрее сортировать методом простых вставок simpleSort(data, from, to); else { int c = data[from]; // Выбираем некоторый элемент // Распределяем элементы массива на значения меньшие и большие c. int low = from, high = to+1; // Inv: (low = c while (low < high) { while (low = c) ; data[low] = data[high]; while (low < high && data[++low] <= c) ; data[high] = data[low]; } // Вставляем элемент на свое место data[low] = c; // Независимо сортируем верхнюю и нижнюю половины массива quickSort(data, from, low-1); quickSort(data, low+1, to); } Программа быстрой сортировки

16 9. Поиск α-медианы public static int mediana(int[] data, double alpha) { int n = data.length; // Длина массива int m = (int)(alpha*(n-1)); // Номер alpha-медианы в упорядоченном массиве // Ищем элемент номер m в участке массива с индексами от low до high. // Для этого выбираем произвольный элемент и делим массив на две части так, // как это делалось в алгоритме быстрой сортировки. int low = 0, high = n-1; // Границы обрабатываемого участка массива do { int c = data[low]; // Выбранный элемент int ndxLow = low, ndxHigh = high; // "Сдвигающиеся" индексы // Цикл фильтрации элементов на меньшие c и большие c. while (ndxLow < ndxHigh) { while (ndxLow = c) ndxHigh--; data[ndxLow] = data[ndxHigh]; while (ndxLow < ndxHigh && data[ndxLow] <= c) ndxLow++; data[ndxHigh] = data[ndxLow]; } // Нашли порядковый номер элемента c. data[ndxLow] = c; if (ndxLow == m) return data[m]; // Продолжаем поиск в одной из двух половин массива if (m < ndxLow) high = ndxLow-1; else low = ndxLow+1; } while (true); }

17 10. Сортировка подсчетом

18 Программа для сортировки подсчетом public static void countSort (int[] src, int[] dest) { // Предполагается, что все элементы src[i] из диапазона int n = src.length; // Длина массива int[] count = new int[16]; // Массив для подсчета элементов // 1. Подсчет for (int i = 0; i < n; i++) { count[src[i]]++; } // 2. Суммирование for (int i = 1; i < 16; i++) { count[i] += count[i-1]; } // 3. Расстановка for (int i = n-1; i >= 0; i--) { dest[--count[src[i]]] = src[i]; }

19 11. Цифровая сортировка После сортировки по последней цифре: После устойчивой сортировки по первой цифре:

20 Программа для цифровой сортировки public static void digitSort(int[] data) { int n = data.length; // Длина массива int[] data2 = new int[n]; // Вспомогательный массив for (int step = 0; step < 8; step++) { // step - номер "цифры" // Сортировка "подсчетом" по цифре с заданным номером countSort(data, step, data2); // Меняем указатели на массивы int[] temp = data; data = data2; data2 = temp; } private static void countSort (int[] src, int nDig, int[] dest) { int n = src.length; // Длина массива int[] count = new int[16]; // Массив для подсчета элементов // 1. Подсчет nDig <<= 2; for (int i = 0; i < n; i++) { count[(src[i] & (0xF > nDig]++; } // 2. Суммирование for (int i = 1; i < 16; i++) { count[i] += count[i-1]; } // 3. Расстановка for (int i = n-1; i >= 0; i--) { dest[--count[(src[i] & (0xF > nDig]] = src[i]; } nDig]++; } // 2. Суммирование for (int i = 1; i < 16; i++) { count[i] += count[i-1]; } // 3. Расстановка for (int i = n-1; i >= 0; i--) { dest[--count[(src[i] & (0xF > nDig]] = src[i]; }">