Реферат: Сортировка данных в массиве
В этом разделе будет рассмотрен знаменитый алгоритм ''быстрой'' сортировки, по праву считающийся самым быстрым среди неспециализированных алгоритмов сортировки. Для сравнения мы также рассмотрим один из алгоритмов сортировки, имеющих более низкую эффективность, но и более простых алгоритмов – сортировку вставками.
Сортировка вставками
Сортировка вставками похожа на процесс тасования карточек с именами. Регистратор заносит каждое имя на карточку, а затем упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее место. Опишем этот процесс на примере нашего пятиэлементного списка 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]; j--; } // точка вставки найдена; вставить temp A[j] = temp; --> ЧИТАТЬ ПОЛНОСТЬЮ <-- К-во Просмотров: 586
Бесплатно скачать Реферат: Сортировка данных в массиве
|