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


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


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

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




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



    1  2  3  4  5  6  7  8  9  10  11 |



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

    В этом разделе будет рассмотрен знаменитый алгоритм ''быстрой'' сортировки, по праву считающийся самым быстрым среди неспециализированных алгоритмов сортировки. Для сравнения мы также рассмотрим один из алгоритмов сортировки, имеющих более низкую эффективность, но и более простых алгоритмов – сортировку вставками.

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

    Сортировка вставками похожа на процесс тасования карточек с именами. Регистратор заносит каждое имя на карточку, а затем упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее место. Опишем этот процесс на примере нашего пятиэлементного списка A = 50, 20, 40, 75, 35 (рисунок 1).

    В функцию InsertionSort передается массив A и длина списка n. Рассмотрим i-ый проход (1<i<n-1). Подсписок от A[0] до A[i-1] уже отсортирован по возрастанию. В качестве вставляемого (TARGET) выберем элемент A[i] и будем продвигать его к началу списка, сравнивая с элементами A[i-1], A[i-2] и т.д. Просмотр заканчивается на элементе A[j], который меньше или равен TARGET, или находится в начале списка (j = 0). По мере продвижения к началу списка каждый элемент сдвигается вправо (A[j] = A[j-1]). Когда подходящее место для A[i] будет найдено, этот элемент вставляется в точку j.

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

    Рис. 1

    // Сортировка вставками упорядочивает подсписки A[0]...A[i], 1 <= i <= n-1. Для

    // каждого i A[i] вставляется в подходящую позицию A[j]

    template <class T>

    void InsertionSort(T A[], int n)

    {

      int i, j;

      T temp;

      // i определяет подсписок A[0]...A[i]

      for (i=1; i<n; i++)

      {

        // индекс j пробегает вниз по списку от A[i] в процессе

        // поиска правильной позиции вставляемого значения

        j = i;

        temp = A[i];

        // обнаружить подходящую позицию для вставки, сканируя подсписок,

        // пока temp < A[j-1] или пока не встретится начало списка

        while (j > 0 && temp < A[j-1])

        {

          // сдвинуть элементы вправо, чтобы освободить место для вставки

          A[j] = A[j-1];


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



    1  2  3  4  5  6  7  8  9  10  11 |




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

       

    Категории:



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




    •