linked_list.cc

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <ctime>

struct LinkedNode {
  int data;
  LinkedNode* next;
  LinkedNode(int val): data(val), next(NULL) {}
};

typedef LinkedNode* LinkedList;

void BuildArray(std::vector<int>& arr) {
  for (int i = 0; i < 10; ++i) {
    arr.push_back(i);
  }
}

void ShuffleArray(std::vector<int>& arr) {
  std::random_shuffle(arr.begin(), arr.end(), [](int i) -> int {
    return std::rand() % i;
  });
}

LinkedList BuildList(std::vector<int> arr) {
  if (arr.empty()) return NULL;
  LinkedList head = NULL;
  LinkedList tail = NULL;
  for (int i = 0; i < arr.size(); ++i) {
    LinkedList node = new LinkedNode(arr[i]);
    if (head == NULL) {
      head = node;
      tail = node;
    } else {
      tail->next = node;
      tail = node;
    }
  }
  return head;
}

void PrintList(LinkedList head) {
  while (head) {
    std::cout << head->data;
    if (head->next) {
      std::cout << "->";
    }
    head = head->next;
  }
  std::cout << std::endl;
}

LinkedList ReverseList(LinkedList& head) {
  if (!head) return NULL;

  LinkedList new_head = NULL;
  LinkedList temp;
  while (head) {
    temp = head->next;
    if (!new_head) {
      new_head = head;
      head->next = NULL;
    } else {
      head->next = new_head;
      new_head = head;
    }
    head = temp;
  }
  return new_head;
};

void BubbleSortExchangeData(LinkedList& head) {
  if (!head) return;

  LinkedList cur, temp;
  LinkedList last_end = NULL;
  while (true) {
    cur = head;
    last_end = NULL;
    bool exchanged = false;

    while (cur && cur != last_end) {
      temp = cur->next;
      if (temp && temp->data < cur->data) {
        std::swap(temp->data, cur->data);
        exchanged = true;
        last_end = temp;
      }
      cur = cur->next;
    }
    if (!exchanged) return;
  }
}

void BubbleSortExchangePointer(LinkedList& head) {
  if (!head) return;

  LinkedList prev, cur, temp;
  LinkedList last_end = NULL;
  while (true) {
    cur = head;
    prev = NULL;
    last_end = NULL;
    bool exchanged = false;

    while (cur && cur != last_end) {
      temp = cur->next;
      if (temp && temp->data < cur->data) {
        if (prev != NULL) {
          prev->next = temp;
        } else {
          head = temp; /* !!! */
        }
        cur->next = temp->next;
        temp->next = cur;
        prev = temp;
        last_end = cur;
        exchanged = true;
      } else {
        prev = cur;
        cur = cur->next;
      }
    }
    if (!exchanged) return;
  }
}

void SelectionSortExchangeData(LinkedList& head) {
  if (!head) return;

  LinkedList ptr1 = head;
  LinkedList ptr2;
  while (ptr1) {
    LinkedList min_pos = ptr1;

    ptr2 = ptr1->next;

    while (ptr2) {
      if (ptr2->data < min_pos->data) {
        min_pos = ptr2;
      }
      ptr2 = ptr2->next;
    }

    if (min_pos != ptr1) {
      std::swap(min_pos->data, ptr1->data);
    }
    ptr1 = ptr1->next;
  }
}

void SelectionSortExchangePointer(LinkedList& head) {
  if (!head) return;

  LinkedList ptr1 = head;
  LinkedList ptr1_prev = NULL;
  LinkedList ptr2, ptr2_prev, min_pos, min_prev, temp;

  /* outer loop: hold the place to set min value */
  while (ptr1) {
    min_pos = ptr1;
    ptr2_prev = ptr1;
    ptr2 = ptr1->next;

    /* inner loop: find the min value and pointer */
    while (ptr2) {
      /* record the min value and pointer */
      if (ptr2->data < min_pos->data) {
        min_pos = ptr2;
        min_prev = ptr2_prev;
      }
      ptr2_prev = ptr2;
      ptr2 = ptr2->next;
    }

    /* pointers exchange */
    if (min_pos != ptr1) {
      temp = min_pos->next;
      if (ptr1 == head) {
        if (ptr1->next != min_pos) {
          min_pos->next = ptr1->next;
          min_prev->next = ptr1;
        } else {
          min_pos->next = ptr1;
        }
        ptr1->next = temp;
        head = min_pos;
      } else {
        if (ptr1->next != min_pos) {
          min_pos->next = ptr1->next;
          ptr1_prev->next = min_pos;
          min_prev->next = ptr1;
        } else {
          min_pos->next = ptr1;
          ptr1_prev->next = min_pos;
        }
        ptr1->next = temp;
      }

      ptr1_prev = min_pos;
      ptr1 = min_pos->next;
    } else {
      ptr1_prev = ptr1;
      ptr1 = ptr1->next;
    }
  }
}

void InsertionSort(LinkedList& head) {
  if (!head) return;
  LinkedList sorted_end = head;
  LinkedList ptr, pre;
  while (sorted_end) {
    pre = sorted_end;
    ptr = sorted_end->next;
    while (ptr) {
      if (ptr->data < sorted_end->data) {
        LinkedList insert_pos = head;
        LinkedList insert_pre = NULL;
        /* find the insertion postion */
        while (insert_pos->data <= ptr->data) {
          insert_pre = insert_pos;
          insert_pos = insert_pos->next;
        }

        /* exchange pointers */
        pre->next = ptr->next;

        if (insert_pos == head) {
          ptr->next = head;
          head = ptr;
        } else {
          insert_pre->next = ptr;
          ptr->next = insert_pos;
        }

        /* update pointers */
        ptr = pre->next;
      } else {
        pre = ptr;
        ptr = ptr->next;
      }
    }
    sorted_end = sorted_end->next;
  }
}

void QuickSort(LinkedList& head) {
  if (!head) return;
}

std::map<void (*) (LinkedList&), std::string> sort_methods = {
  {BubbleSortExchangeData,       "bubble sort with data exchange"},
  {BubbleSortExchangePointer,    "bubble sort with pointer exchange"},
  {SelectionSortExchangeData,    "slection sort with data exchange"},
  {SelectionSortExchangePointer, "slection sort with pointer exchange"},
  {InsertionSort,                "insertion sort"}
};

int main(int argc, const char* argv[]) {
  std::srand(unsigned(std::time(0)));
  std::vector<int> arr;
  BuildArray(arr);

  for (auto it = sort_methods.begin(); it != sort_methods.end(); ++it) {
    std::cout << it->second << std::endl;
    ShuffleArray(arr);
    LinkedList head = BuildList(arr);
    std::cout << "original: ";
    PrintList(head);

    head = ReverseList(head);
    std::cout << "reversed: ";
    PrintList(head);

    it->first(head);
    std::cout << "[sorted]: ";
    PrintList(head);
    std::cout << "======================================" << std::endl;
  }

  return 0;
}