Сортировка – это упорярядочивание набора однотипных данных по возрастанию или убыванию.
В языке Си есть стандартная функция qsort().
Недостатки – не может сортировать данные, находящиеся в связанных списках и универсальность ведет к "медленной работе" в некоторых конкретных случаях.
Существует две категории алгоритмов сортировок:
- Алгоритмы, сортирующие объекты с произвольным доступом.
- Алгоритмы, сортирующие последовательные объекты.
Рассмотрим алгоритмы первой категории, как наиболее полезные для применения.
При сортировки данных часть их используется в качестве ключа сортировки.
Ключ – это часть информации, определяющая порядок элементов.
Существует три общих метода сортировки массивов:
- обмен;
- выбор;
- вставка.
Оценка алгоритмов сортировки
Рассмотрим общие критерии оценки алгоритов:
- среднее время работы алгоритма сортировки;
- минимальное и максимальное время работы;
- естественно или неестественно он себя ведет (поведение алгоритма сортировки называется естественным, если время сортировки минимально для уже упорядоченного списка элементов, увеличивается по мере возрастания степени неупорядоченности списка и максимально, когда элементы списка расположены в обратном порядке);
- преставляет ли он элементы с одинаковыми ключами (если в отсортированном массиве элементы с одинаковыми ключами идут в том же порядке, в которомони располагались в исходном массиве, то алгоритм сортировки называется устойчивым, а в противном случае – неустойчивым.)
Объем работы алгоритма оценивается количеством проиводимых производимых сравнений и обменов.
|
|
Время работы одних алгоритмов сортировки растет экспоненциально, время паботы других логарифмически зависит от количества элементов.
Пузырьковая сортировка
Этот алгоритм является самым известным и оним из самых худших алгоритмов сортировки (зато является простым алгоритмом). Этот алгоритм относится к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения и, при необходимости, обмен соседних данных. Элементы ведут себя подобно пузырькам воздуха в воде – каждый из них поднимается на свой уровень.
Пример: /* пузырьковая сортировка */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
void bubble(char *, int);
int main(void)
{
char cStr[255];
char cStr1[]="Введите строку: ";
CharToOem(cStr1,cStr1);
char cStr2[]="Отсортированная строка: ";
CharToOem(cStr2,cStr2);
printf("%s",cStr1);
gets(cStr);
bubble(cStr, strlen(cStr));
printf("%s %s. \n",cStr2,cStr);
return 0;
}
void bubble (char *pStr, int count)
{
int i,j;
char cStr;
for(i=1; i<count; ++i)
for(j=count-1; j>=i; --j) {
if(pStr[j-1] > pStr[j]) {
cStr=pStr[j-1];
pStr[j-1] = pStr[j];
|
|
pStr[j] = cStr;
}
}
}
В пузырьковой сортировке количество сравнений всегда одно и тоже (два цикла по n). Таким образом, алгоритм выполняет сравнений (внешний цикл выполняется раз, а внутренний в среднем раз.
Пузырьковая сортировка является алгоритмом порядка , так как время его работы пропорциональноквадрату количества сортируемых элементов.
Существует много модификаций алгоритма сортировки.
Сортировка посредством выбора
Литература
1. Подбельский В.В., Фомин С.С. Программирование на языке Си: Учеб. пособие. – М: Финансы и статистика, 1998. – 600 с.
2. Керниган Б., Ритчи Д. Язык программирования Си: Пер. с англ. - 2-е изд., перераб. и доп. М., Финансы и статистика, 1992.
3. С. Прата. Язык программирования Си. Киев, ДиаСофт, 2001.
4. Уинер Р. Язык Турбо Си: Пер. с англ. – М: Мир, 1991. – 384с.
5. Уэйт У., Мартин Дж, Прата Л. Язык Си для начинающих. М., Мир, 1988.