Паскаль
<<  Задачи с использованием одномерных массивов Алгоритмы сортировки массивов  >>
Двоичный поиск в упорядоченном массиве
Двоичный поиск в упорядоченном массиве
Сортировки массива
Сортировки массива
2. Сортировка простыми вставками
2. Сортировка простыми вставками
3. Сортировка двоичными вставками
3. Сортировка двоичными вставками
4. Сортировка Шелла
4. Сортировка Шелла
4. Сортировка Шелла
4. Сортировка Шелла
5. Алгоритм слияния упорядоченных массивов
5. Алгоритм слияния упорядоченных массивов
6. Сортировка фон Неймана (слиянием)
6. Сортировка фон Неймана (слиянием)
Алгоритм сортировки фон Неймана
Алгоритм сортировки фон Неймана
7. Пирамидальная сортировка (сортировка «кучей»)
7. Пирамидальная сортировка (сортировка «кучей»)
7. Пирамидальная сортировка (продолжение)
7. Пирамидальная сортировка (продолжение)
Алгоритм пирамидальной сортировки
Алгоритм пирамидальной сортировки
8. Быстрая сортировка
8. Быстрая сортировка
Дополнения и улучшения алгоритма
Дополнения и улучшения алгоритма
Программа быстрой сортировки
Программа быстрой сортировки
9. Поиск
9. Поиск
10
10
Программа для сортировки подсчетом
Программа для сортировки подсчетом
11
11
Программа для цифровой сортировки
Программа для цифровой сортировки

Презентация на тему: «Двоичный поиск в упорядоченном массиве». Автор: Александр Кубенский. Файл: «Двоичный поиск в упорядоченном массиве.ppt». Размер zip-архива: 155 КБ.

Двоичный поиск в упорядоченном массиве

содержание презентации «Двоичный поиск в упорядоченном массиве.ppt»
СлайдТекст
1 Двоичный поиск в упорядоченном массиве

Двоичный поиск в упорядоченном массиве

33

1

3

4

8

10

14

16

21

24

27

31

33

36

38

42

44

50

51

53

59

Инвариант цикла: l <= h && «если key == data[k], то l <= k <= h»

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); }

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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. Сортировка простыми вставками

2. Сортировка простыми вставками

4

14

31

42

1

8

24

3

59

33

44

53

16

10

38

50

21

36

4

14

27

51

31

42

1

8

24

3

59

33

44

53

16

10

38

50

21

36

4

14

27

31

51

42

1

8

24

3

59

33

44

53

16

10

38

50

21

36

1

8

24

3

59

33

44

53

16

10

38

50

21

36

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. Сортировка двоичными вставками

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. Сортировка Шелла

4. Сортировка Шелла

4

27

51

14

31

42

1

8

24

3

59

33

44

53

16

10

38

50

21

36

step=7

step=3

step=2

step=1

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

6 4. Сортировка Шелла

4. Сортировка Шелла

Количество перестановок элементов (по результатам экспериментов со случайным массивом)

n = 25

n = 1000

n = 100000

Сортировка Шелла

50

7700

2 100 000

Сортировка простыми вставками

150

240 000

2.5 млрд.

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); }

7 5. Алгоритм слияния упорядоченных массивов

5. Алгоритм слияния упорядоченных массивов

4

14

27

51

1

3

8

24

31

42

59

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 6. Сортировка фон Неймана (слиянием)

6. Сортировка фон Неймана (слиянием)

4

27

51

14

31

42

1

8

24

3

59

33

44

53

16

10

38

50

21

36

И так далее…

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. Пирамидальная сортировка (сортировка «кучей»)

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

4

27

51

14

31

42

1

8

24

3

59

33

44

53

16

10

38

50

21

36

4

27

51

14

31

42

1

8

24

3

59

33

44

53

16

10

38

50

21

36

И так далее…

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

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

59

51

53

50

36

42

44

24

38

31

14

27

33

1

16

4

10

8

3

21

И так далее…

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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 < i-1 && data[p+1] > data[p]) p++; if (data[p] > c) data[q] = data[p]; else { data[q] = c; continue meltPyramid; } } while (true); } }

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

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

4

27

51

14

31

42

1

8

24

3

59

33

44

53

16

10

38

50

21

36

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 <= high) && data[from:(low-1)] <= c && data[high:to] >= c while (low < high) { while (low < high && data[--high] >= 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. Поиск

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 < ndxHigh && data[ndxHigh] >= 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

10

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

4

7

1

4

1

2

1

8

4

3

9

3

4

3

6

0

8

0

1

6

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

18 Программа для сортировки подсчетом

Программа для сортировки подсчетом

public static void countSort (int[] src, int[] dest) { // Предполагается, что все элементы src[i] из диапазона 0..15 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

11

Цифровая сортировка

4

4

27

27

51

51

14

14

31

31

42

42

1

1

8

8

24

24

3

3

59

59

33

33

44

44

53

53

16

16

10

10

39

39

50

50

21

21

36

36

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)) >> 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)) >> nDig]] = src[i]; } }

«Двоичный поиск в упорядоченном массиве»
http://900igr.net/prezentacija/informatika/dvoichnyj-poisk-v-uporjadochennom-massive-158159.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Паскаль > Двоичный поиск в упорядоченном массиве