Рефераты | Рефераты по информатике, программированию | Сортировка данных в массиве | страница реферата 3 | Большая Энциклопедия Рефератов от А до Я
Большая Энциклопедия Рефератов от А до Я
  • Рефераты, курсовые, шпаргалки, сочинения, изложения
  • Дипломы, диссертации, решебники, рассказы, тезисы
  • Конспекты, отчеты, доклады, контрольные работы


    • Рефераты | Рефераты по информатике, программированию | Сортировка данных в массиве


    Рефераты | Рефераты по информатике, программированию | Сортировка данных в массиве

    Сортировка данных в массиве




    Категория реферата: Рефераты по информатике, программированию
    Теги реферата: сочинение рассуждение, реферат молодежь
    Добавил(а) на сайт: Funtusov.



    Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 |



    Рис.4

    Затем происходит обмен значениями центрального элемента A[0] с A[scanDown]:

    Swap(A[0], A[scanDown]);

    В результате у нас появляются два подсписка A[0] – A[5] и A[6] – A[9], причем все элементы первого подсписка меньше элементов второго, и последний элемент первого подсписка является его наибольшим элементом. Таким образом, можно считать, что после проделанных операций подсписки разделены элементом А[5] = 550 (рисунок 5). Если теперь отсортировать каждый подсписок по отдельности, то у нас получится полностью отсортированный массив. Заметьте, что по сути оба этих подсписка являются такими же массивами, как и исходный, поэтому к ним можно применить тот же самый алгоритм. Применение того же алгоритма к частям массива называется рекурсивной фазой.

    Рекурсивная фаза

    Одним и тем же методом обрабатываются два подсписка: Sl(A[0] – A[4]) и Sh(A[6] – A[9]). Элемент А[5] обрабатывать не надо, так как он уже находится на своем месте.

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

    Рефераты | Рефераты по информатике, программированию | Сортировка данных в массиве 

    Рис.5

    Алгоритм QuickSort

    Этот рекурсивный алгоритм разделяет список A[low]--A[high] по центральному элементу, который выбирается из середины списка

    mid = (high + low) / 2;

    pivot = A[mid];

    После обмена местами центрального элемента с A[low], задаются начальные значения индексам scanUp = low + 1 и scanDown = high, указывающим на начало и конец списка, соответственно. Алгоритм управляет этими двумя индексами. Сначала scanUp продвигается вверх по списку, пока не превысит значение scanDown или пока не встретится элемент больший, чем центральный.

    while (scanUp <= scanDown && A[scanUp] <= pivot)

      scanUp++;

    После позиционирования scanUp индекс scanDown продвигается вниз по списку, пока не встретится элемент, меньший или равный центральному.

    while (pivot < A[scanDown])

      scanDown--;

    По окончании этого цикла (и при условии что scanUp < scanDown) оба индекса адресуют два элемента, находящихся не в тех подсписках. Эти элементы меняются местами.

    Swap(A[scanUp], A[scanDown]);

    Обмен элементов прекращается, когда scanDown становится меньше, чем scanUp. В этот момент scanDown указывает начало левого подсписка, который содержит меньшие или равные центральному элементы. Индекс scanDown становится центральным. Взять центральный элемент из A[low]:

    Swap(A[low], A[scanDown]);

    Для обработки подсписков используется рекурсия. После обнаружения точки разбиения мы рекурсивно вызываем QuickSort с параметрами low, mid-1 и mid+1, high. Условие останова возникает, когда в подсписке остается менее двух элементов, так как одноэлементный или пустой массив упорядочивать не нужно.

    // Swap меняет местами элементы массива. Соответствующий тип данных

    // должен поддерживать операцию «=».


    Рекомендуем скачать другие рефераты по теме: инвестиции реферат, реферат память.



    Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 |




    Поделитесь этой записью или добавьте в закладки

       

    Категории:



    Разделы сайта




    •