Улучшение сортировки слиянием для связанных списков. Как? - PullRequest
Новая
       12

Улучшение сортировки слиянием для связанных списков. Как?

0 голосов
/ 27 ноября 2010

прежде чем я углублюсь в объяснения, вы должны знать, что следующий код может быть очень плохим.Я начал программировать около 2 месяцев назад (несколько часов там и там).Так что я неопытный, мой стиль кодирования очень улучшен, и я все еще скучаю по практике и большому количеству (базовых) знаний.Это также включает в себя то, что я называю вещи с неправильным именем, вероятно:).

Я заинтересовался алгоритмами (университет) и хотел попрактиковаться в некоторой обработке указателей (сначала у меня были некоторые проблемы с этим), поэтому я решил сделать сортировку слияниемс односвязными списками и посмотрите, как он работает по сравнению с алгоритмом mergeSort моего профессора (который сортирует массивы).И нет, это не домашняя работа (ни у одного из моих университетских курсов (электротехника) нет домашней работы) - это мое улучшение в понимании алгоритмов, C и просто отработки вещей.

Мой код уже работает.Для тестирования я всегда создавал списки с обратной сортировкой.В таких случаях до сих пор чего-то не хватает. Список равен NULL.

Итак, перед публикацией кода, который использует структуру, я использую: 

struct list{
  int nbr;
  struct list *next_el;
};
typedef struct list LIST;
typedef LIST *z_LIST;

У меня есть две функции: mergeSort и merge.mergeSort возвращает новый заголовок отсортированных (под) списков, а merge возвращает заголовок объединенных последовательностей.

Прямо сейчас я даю mergeSort текущий заголовок несортированного списка и количество элементов.Затем он рекурсивно разбивает список (очевидно :)).Я не уверен, сколько сказать о следующем коде.Если что-то неясно, я отвечу и объясню как можно быстрее, но 

z_LIST mergeSort ( z_LIST head, int length ) {

  int steps;
  int m = 0;
  z_LIST head1 = NULL, head2 = NULL, new_head = NULL;

if( length > 1) {

  m = (length+1)/2;


  head2 = head; 
  for(steps = 0; steps<m; steps++) {
    head2 = head2->next_el;
  }

  head1 = mergeSort(head, m);
  head2 = mergeSort(head2, length-m);

  new_head = merge(head1, head2, m, length-m);

  return new_head;

  } else {
    return head;
  }
}

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

z_LIST merge (z_LIST head1, z_LIST head2, int l1, int l2)  {

  int i,j;
  z_LIST part1 = head1, part2 = head2;
  z_LIST temp_head = NULL, head = NULL;

/*First I let it check what the head of the new list is going to 
be and thus initiating the merging process with either i=1/j=0
or i=0/j=1.*/

  if(part1->nbr < part2->nbr){
    head = part1;
    if(part1->next_el != NULL)  {
      part1 = part1->next_el;
    }
    i=1;
    j=0;
  } else {
    head = part2;
    if(part2->next_el != NULL)  { //The last element of the original list points
      part2 = part2->next_el;     //to NULL. If I would then make part2 = NULL,
    }                             //then there wouldn't be part2->nbr ->lots
    i=0;
    j=1;
  }

  temp_head = head;

  while( (i<l1) || (j<l2) ) {
    if( ((part1->nbr < part2->nbr) && i<l1)||( j>=l2 ))  {
      temp_head->next_el = part1;
      part1 = part1->next_el;
      temp_head = temp_head->next_el;
      if (j>=l2)  { //If j>=l2 then I let merge add one more item of list1
       break;       //since list 1 is already sorted and linked correctly.
      }             //Same below. Should shave off some operations/time?
      i++;
    } else {
      temp_head->next_el = part2;
      part2 = part2->next_el;
      temp_head = temp_head->next_el;
      if (i>=l1)  {
        break;
      }
      j++;
    }
  }

  return head;
}

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

1 Ответ

0 голосов
/ 27 ноября 2010

«Нормальная» структура для фазы слияния сортировки: 

set output list to empty
while (list1 not empty && list2 not empty)
{
    if (list1->headvalue < list2->headvalue
        move head of list1 to output list
    else
        move head of list2 to output list
}
while (list1 not empty)
    move head of list1 to output list
while (list2 not empty)
    move head of list2 to output list

Операция «перемещение» включает обновление указателя на следующий элемент в списке.

Youимеют несколько иную структуру в вашей функции merge().

Также обычно требуется подсчитывать списки.Обычно вы определяете конец списка, используя 'next is null' или 'next is head' в зависимости от того, является ли список чисто линейным или круговым списком.

...