Алгоритмы: сортировка и поиск

Сортировка – это упорярядочивание набора однотипных данных по возрастанию или убыванию.

В языке Си есть стандартная функция qsort().

Недостатки – не может сортировать данные, находящиеся в связанных списках и универсальность ведет к "медленной работе" в некоторых конкретных случаях.

Существует две категории алгоритмов сортировок:

  1. Алгоритмы, сортирующие объекты с произвольным доступом.
  2. Алгоритмы, сортирующие последовательные объекты.

Рассмотрим алгоритмы первой категории, как наиболее полезные для применения.

При сортировки данных часть их используется в качестве ключа сортировки.

Ключ – это часть информации, определяющая порядок элементов.

Существует три общих метода сортировки массивов:

  • обмен;
  • выбор;
  • вставка.

 

Оценка алгоритмов сортировки

Рассмотрим общие критерии оценки алгоритов:

  • среднее время работы алгоритма сортировки;
  • минимальное и максимальное время работы;
  • естественно или неестественно он себя ведет (поведение алгоритма сортировки называется естественным, если время сортировки минимально для уже упорядоченного списка элементов, увеличивается по мере возрастания степени неупорядоченности списка и максимально, когда элементы списка расположены в обратном порядке);
  • преставляет ли он элементы с одинаковыми ключами (если в отсортированном массиве элементы с одинаковыми ключами идут в том же порядке, в которомони располагались в исходном массиве, то алгоритм сортировки называется устойчивым, а в противном случае – неустойчивым.)

Объем работы алгоритма оценивается количеством проиводимых производимых сравнений и обменов.

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

 

Пузырьковая сортировка

Этот алгоритм является самым известным и оним из самых худших алгоритмов сортировки (зато является простым алгоритмом). Этот алгоритм относится к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения и, при необходимости, обмен соседних данных. Элементы ведут себя подобно пузырькам воздуха в воде – каждый из них поднимается на свой уровень.

 

Пример: /* пузырьковая сортировка */

#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.