Содержание


Работа со структурами данных в языках Си и Python

Часть 4. Связные списки и сортировка

Comments

Серия контента:

Этот контент является частью # из серии # статей: Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

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

Типы сортировок

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

Методы сортировки обычно разделяются на две категории: сортировка массивов и сортировка файлов, также называемые внутренней и внешней сортировкой, так как массивы располагаются во внутренней памяти, а файлы во внешней. Важнейшее требование к алгоритмам для сортировки массивов и связных списков - экономное расходование памяти, поэтому использование дополнительных массивов для сортировки считается дурным тоном.

Основным критерием для классификации алгоритмов сортировки является их быстродействие. При сортировке выполняются два типа операций - сравнение ключей и перестановка элементов (в случае со связными списками - переназначение указателей). Если в массиве n элементов, то алгоритм считается хорошим, если число перестановок равно произведению числа элементов массива n на логарифм этого числа log(n). Например, стандартная пузырьковая сортировка требует числа перестановок, равного квадрату от n.

Методы сортировки можно разбить на три основных класса:

  • сортировка включениями;
  • сортировка выбором;
  • сортировка обменом.

Принцип, лежащий в основе первого класса, заключается в том, что массив разбивается на две половины - итоговую и входную. Берется элемент из входной половины и вставляется в итоговую в порядке сортировки. Число перестановок элементов в общем случае равно квадрату от n.

В случае сортировки выбором алгоритм таков: берется минимальный элемент массива и ставится в начало массива, и т.д. Число перестановок элементов в общем случае меньше, чем в первом случае, и будет равно произведению числа элементов массива на логарифм от этого числа. Быстрая сортировка относится ко второму классу.

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

Первым будет рассматриваться алгоритм пузырьковой сортировки, который требует порядка n*n перестановок, поэтому является не самым удачным выбором. В функции llist_bubble_sort, приведенной в листинге 1, выполняется вложенная итерация по списку, с помощью которой реализуется алгоритм пузырьковой сортировки для языка Си.

Листинг 1. Реализация пузырьковой сортировки на языке Си
#include <stdio.h>
#include <stdlib.h>

#define MAX 10

struct lnode 
{
 int data;
 struct lnode *next;
} *head, *visit;

void llist_add(struct lnode **q, int num);
void llist_bubble_sort(void);
void llist_print(void);

int main(void) 
{
 struct lnode *newnode = NULL;
 int i = 0;

 for(i = 0; i < MAX; i++) 
 {
   llist_add(&newnode, (rand() % 100));
 }

 head = newnode;
 printf("до пузырьковой сортировки:\n");
 llist_print();
 printf("после пузырьковой сортировки:\n");
 llist_bubble_sort();
 llist_print();

 return 0;
}

void llist_add(struct lnode **q, int num) 
{
 struct lnode *tmp; 
 
 tmp = *q;

 if(*q == NULL) {
  *q = malloc(sizeof(struct lnode));
   tmp = *q;
 } else {
  while(tmp->next != NULL)
   tmp = tmp->next;

   tmp->next = malloc(sizeof(struct lnode));
   tmp = tmp->next;
 }

 tmp->data = num;
 tmp->next = NULL;
}

void llist_print(void) 
{
 visit = head;

 while(visit != NULL) {
  printf("%d ", visit->data);
  visit = visit->next;
 }
 printf("\n");
}

void llist_bubble_sort(void) 
{
 struct lnode *a = NULL;
 struct lnode *b = NULL; 
 struct lnode *c = NULL;
 struct lnode *e = NULL; 
 struct lnode *tmp = NULL; 

 while(e != head->next) 
 {
	c = a = head;
	b = a->next;
		while(a != e) 
		{
			if(a->data > b->data) 
			{
				if(a == head) 
				{
					tmp = b -> next;
					b->next = a;
					a->next = tmp;
					head = b;
					c = b;
				} 
				else 
				{
					tmp = b->next;
					b->next = a;
					a->next = tmp;
					c->next = b;
					c = b;
				}
			} 
			else 
			{
				c = a;
				a = a->next;
			}
			b = a->next;
			if(b == e)
				e = a;
		}
	}
}

В листинге 2 приведена реализация пузырьковой сортировки на языке Python с использованием стандартных списков, встроенных в Python.

Листинг 2. Реализация пузырьковой сортировки на языке Python
import random 

lista = [] 

for i in range ( 0, 10 ) : 
  lista.append ( int ( random.uniform ( 0, 10 ) ) )

print lista
def bubble_sort ( lista ) :
  swap_test = False
  for i in range ( 0, len ( lista ) - 1 ):
    for j in range ( 0, len ( lista ) - i - 1 ):
      if lista[j] > lista[j + 1] :
        lista[j], lista[j + 1] = lista[j + 1], lista[j] 
        swap_test = True
    if swap_test == False:
      break

bubble_sort ( lista ) 
print lista

В листинге 3 приведен исходный код пузырьковой сортировки для Python, но уже на основе связных списков.

Листинг 3. Пузырьковая сортировка с использованием связных списков
import random 

class Node:
    def __init__(self, value = None, next = None):
        self.value = value
        self.next = next

    def __str__(self):
        return 'Node ['+str(self.value)+']'

class LinkedList:
    def __init__(self):
        self.first = None
        self.last  = None
        self.length = 0

    def add(self, x):
        if self.first == None:
            self.first = Node(x, None)
            self.last = self.first
        elif self.last == self.first:
            self.last = Node(x, None)
            self.first.next = self.last
        else:
            current = Node(x, None)
            self.last.next = current
            self.last = current

    def __str__(self):
        if self.first != None:
            current = self.first
            out = 'LinkedList [ ' +str(current.value) +' '
            while current.next != None:
                current = current.next
                out += str(current.value) + ' '
            return out + ']\n'
        return 'LinkedList []'

    def BubbleSort(self):
       a = Node(0,None)
       b = Node(0,None)
       c = Node(0,None)
       e = Node(0,None)
       tmp = Node(0,None)
       
       while(e != self.first.next) :
        c = a = self.first
        b = a.next

        while a != e:
          if a and b:
            if a.value > b.value:
              if a == self.first:
                tmp = b.next
                b.next = a
                a.next = tmp
                self.first = b
                c = b
              else:
                tmp = b.next
                b.next = a
                a.next = tmp
                c.next = b
                c = b
            else:
              c = a
              a = a.next
            b = a.next
            if b == e:
              e = a
          else:
              e = a
              
    
L  = LinkedList()

for i in range ( 0, 10 ) : 
  L.add ( int ( random.uniform ( 0, 10 ) ) )

print L
L.BubbleSort()
print L

Как можно увидеть, код в листинге 3 очень похож на код на языке Си, приведенный в листинге 1, поскольку в Python работа со ссылками на объекты реализована практически так же, как и в языке Си.

Быстрая сортировка

В данном разделе будет рассмотрен алгоритм быстрой (quicksort) сортировки двусвязного списка, на основе рекурсивной функции QuickSortList, представленной в листинге 4. Данная функция работает следующим образом:

  1. выполняется итерация по списку;
  2. в ходе итерации определяется максимальное значение, которое записывается в конец массива;
  3. выполняется следующая итерация, но без только что найденного максимума и т.д.
Листинг 4. Реализация быстрой сортировки на языке Си
#include <stdio.h>

// элемент двусвязного списка
typedef struct _tagIntegerList
{
	int nInteger;
	struct _tagIntegerList *pPrev;
	struct _tagIntegerList *pNext;
} IntegerList;


// указатели на первый и последний элементы списка
IntegerList *g_pFirstItem = NULL;
IntegerList *g_pLastItem = NULL;

// добавление в список
void AddListItem(int nInteger)
{
	IntegerList *pItem = new IntegerList;
	pItem->nInteger = nInteger;
	if (g_pFirstItem == NULL)
	{
		g_pFirstItem = g_pLastItem = pItem;
		pItem->pNext = pItem->pPrev = NULL;
	}
	else
	{
		g_pLastItem->pNext = pItem;
		pItem->pPrev = g_pLastItem;
		g_pLastItem = pItem;
		pItem->pNext = NULL;
	}
}

// удаление
void RemoveAllItems()
{
	IntegerList *pDelItem, *pItem = g_pFirstItem;

	while (pItem != NULL)
	{
		pDelItem = pItem;
		pItem = pItem->pNext;
		delete pDelItem;
	}
	g_pFirstItem = g_pLastItem = NULL;
}

// вывод содержимого списка в консоль
void PrintList()
{
	IntegerList *pItem = g_pFirstItem;

	while (pItem != NULL)
	{
		printf("%d  ", pItem->nInteger);
		pItem = pItem->pNext;
	}
		printf("\n");
}

// быстрая сортировка
void QuickSortList(IntegerList *pLeft, IntegerList *pRight)
{
	IntegerList *pStart;
	IntegerList *pCurrent; 
	int nCopyInteger;

	// сортировка окончена - выход
	if (pLeft == pRight) return;

	// установка двух рабочих указателей - Start и Current
	pStart = pLeft;
	pCurrent = pStart->pNext;

	// итерация по списку слева направо
	while (1)
	{
		// элемент с максимальным значением помещается в начало списка
		if (pStart->nInteger < pCurrent->nInteger)
		{
			nCopyInteger = pCurrent->nInteger;
			pCurrent->nInteger = pStart->nInteger;
			pStart->nInteger = nCopyInteger;
		}	
		
		if (pCurrent == pRight) break;
		pCurrent = pCurrent->pNext;
	}



	// переключение First и Current - максимум попадает в правый конец списка
	nCopyInteger = pLeft->nInteger;
	pLeft->nInteger = pCurrent->nInteger;
	pCurrent->nInteger = nCopyInteger;


	// сохранение Current
	IntegerList *pOldCurrent = pCurrent;

	// рекурсия
	pCurrent = pCurrent->pPrev;
	if (pCurrent != NULL)
	{
		if ((pLeft->pPrev != pCurrent) && (pCurrent->pNext != pLeft))
			QuickSortList(pLeft, pCurrent);
	}

	pCurrent = pOldCurrent;
	pCurrent = pCurrent->pNext;
	if (pCurrent != NULL)
	{
		if ((pCurrent->pPrev != pRight) && (pRight->pNext != pCurrent))
			QuickSortList(pCurrent, pRight);
	}
}

int main ()
{

	AddListItem(100);
	AddListItem(12);
	AddListItem(56);
	AddListItem(67);

	PrintList();
	QuickSortList(g_pFirstItem, g_pLastItem);
	PrintList();
	RemoveAllItems();
	return 0;
}

Сортировка слиянием

При сортировке слиянием (mergesort) массив разбивается на две части, каждая часть сортируется отдельно, а потом обе части сливаются. Практически это можно объяснить на следующем примере.

  1. колода карт делится на две части, и каждая часть сортируется по отдельности, чтобы наверху оказалась самая маленькая карта;
  2. из двух верхних карт выбирают меньшую и перекладывают ее в результирующую колоду;
  3. процесс повторяется, пока не кончатся карты в обеих половинах;
  4. если в одной половине карты закончатся раньше, тогда все карты, оставшиеся в другой половине, просто перекладываются в результирующую колоду.

Считается, что этот алгоритм был придуман Джоном фон Нейманом в 1945 году. Недостатком сортировки слиянием считается то, что она требует O(n) памяти.

Листинг 5. Реализация сортировки слиянием на языке Си
struct node 
{
 int number;
 struct node *next;
};

struct node *addnode(int number, struct node *next) 
{
 struct node *tnode;
 tnode = (struct node*)malloc(sizeof(*tnode));
 if(tnode != NULL) 
 {
  tnode->number = number;
  tnode->next = next;
 }
 return tnode;
}

int Length(struct node* head) 
{
  int count = 0;
  struct node* current = head;
  while (current != NULL) 
  {
    count++;
    current = current->next;
  }
  return(count);
}

void FrontBackSplit(struct node* source, 
                    struct node** frontRef, 
                    struct node** backRef) 
{

  int len = Length(source);
  int i;
  struct node* current = source;
  if (len < 2) 
  {
    *frontRef = source;
    *backRef = NULL;
  }
  else 
  {
    int hopCount = (len-1)/2;
    for (i = 0; i<hopCount; i++) 
    {
      current = current->next;
    }
    // исходный список разбивается на два подсписка
    *frontRef = source;
    *backRef = current->next;
    current->next = NULL;
  }
}

struct node* SortedMerge(struct node* a, struct node* b) 
{
  struct node* result = NULL;
  if (a==NULL) return(b);
  else if (b==NULL) return(a);
  if (a->number <= b->number) 
  {
    result = a;
    result->next = SortedMerge(a->next, b);
  }
  else 
  {
    result = b;
    result->next = SortedMerge(a, b->next);
  }
  return(result);
}
  

void MergeSort(struct node** headRef) 
{
  struct node* head = *headRef;
  struct node* a;
  struct node* b;
  // вырожденный случай – длина списка равно 0 или 1
  if ((head == NULL) || (head->next == NULL)) 
  {
    return;
  }
  FrontBackSplit(head, &a, &b);
  MergeSort(&a); // рекурсивная сортировка подсписков
  MergeSort(&b);
  *headRef  = SortedMerge(a, b);
}

Сравнение различных алгоритмов

После изучения различных алгоритмов сортировки можно выполнить их сравнительное тестирование. В качестве исходной позиции будет использоваться односвязный список длиной в 50000 элементов, при этом ключ в элементе может иметь значение от 0 до 100. Элементы вставляются в произвольном порядке, и исходный список может иметь следующий вид:

0 10 10 2 9 7 2 3 4 5 2 2 10 1 1 .....

А после сортировки список должен иметь следующий вид:

0 1 1 2 2 2 2 3 4 5 7 9 10 10 10 .....

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

Листинг 6. Оценка производительности пузырьковой сортировки на языке Си
int main(void) 
{
  time_t start,time2,end;
  volatile long unsigned t;
  start = time(NULL);
  
 struct lnode *newnode = NULL;
 int i = 0;
 for(i = 0; i < MAX; i++) 
 {
   llist_add(&newnode, (rand() % 100));
 }
 head = newnode;
 printf("до пузырьковой сортировки:\n");
 time2 = time(NULL);
 printf("на подготовку потребовалось %f секунд.\n", difftime(time2, start));
 printf("после пузырьковой сортировки:\n");

 llist_bubble_sort();

 end = time(NULL);
 printf("на сортировку потребовалось %f секунд.\n", difftime(end, time2));

 return 0;
}

В листинге 7 приведен исходный код для проверки производительности быстрой сортировки.

Листинг 7. Оценка производительности быстрой сортировки на языке Си
int main ()
{
  time_t start,time2,end;
  volatile long unsigned t;
  start = time(NULL);

 for(int i = 0; i < 50000; i++) 
 {
    AddListItem((rand() % 100));
 }
  
 time2 = time(NULL);
 printf("на подготовку потребовалось %f секунд.\n", difftime(time2, start));
  
 QuickSortList(g_pFirstItem, g_pLastItem);

 end = time(NULL);
 printf("на сортировку потребовалось %f секунд.\n", difftime(end, time2));
 
 return 0;
}

В случае с сортировкой слиянием главная проблема связана с увеличением стека при рекурсии, так как при увеличении длины списка свыше 50000 элементов могут возникнуть ошибки. Функция main для сортировки слиянием показана в листинге 8.

Листинг 8. Оценка производительности сортировки слиянием на языке Си
int main(void) 
{
 time_t start,time2,end;
 volatile long unsigned t;
 start = time(NULL);
  
 struct node *head;
 
 int i;

 head = NULL;

 for( i = 0; i < 100; i++) 
 {
   head = addnode((rand() % 100), head);
 }

 time2 = time(NULL);
 printf("на подготовку потребовалось %f секунд.\n", difftime(time2, start));
 
 MergeSort(&head) ;

 end = time(NULL);
 printf("на сортировку потребовалось %f секунд.\n", difftime(end, time2));
 
 return 0;
}

Стоит учесть, что этот тест не претендует на звание «абсолютной истины», так как речь идет о конкретной реализации, применяемой на конкретной системе. Наихудший результат, как и ожидалось, показала пузырьковая сортировка, которой на то, чтобы упорядочить связный список из 50000 элементов, потребовалось более 30 секунд. Быстрая сортировка справилась с этой же задачей за 10 секунд. А самой производительной оказалась сортировка слиянием, выполнив задачу еще быстрее, чем быстрая сортировка. Также тест выявил следующие закономерности.

  1. Наибольшее число перестановок требуется пузырьковой сортировке, затем идет быстрая сортировка, и меньше всего перестановок требуется для сортировки слиянием.
  2. При увеличении длины списка отношение числа перестановок в пузырьковой сортировке к числу перестановок в быстрой сортировке растет не в пользу первой, то есть при увеличении размера списка производительность пузырьковой сортировки начинает снижаться.
  3. Сортировка слиянием имеет самые лучшие показатели по числу перестановок. Аналогичное соотношение числа перестановок для быстрой сортировки и сортировки слиянием при увеличении длины списка изменяется в пользу быстрой сортировки: чем больше список, тем меньше это соотношение, хотя и остается больше единицы.

Заключение

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


Ресурсы для скачивания


Похожие темы

  • Работа со структурами данных в языках Си и Python. Часть 1.
  • Работа со структурами данных в языках Си и Python. Часть 2.
  • Работа со структурами данных в языках Си и Python. Часть 3.
  • Работа со структурами данных в языках Си и Python. Часть 4.

Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=658092
ArticleTitle=Работа со структурами данных в языках Си и Python: Часть 4. Связные списки и сортировка
publish-date=05122011