quicksort-linkedlist.cpp

#include <climits>
#include <iostream>
#include <stdexcept>

typedef struct Node {
  int   value;
  Node* next;
  Node* prev;

  Node(int value) {
    this->value = value;
    this->next = NULL;
    this->prev = NULL;
  }
} Node;

typedef class LinkedList {
  Node *head;
  Node *tail;

private:
  void validate_index(int index) {
    if (index >= this->size() || index < 0) {
      throw std::invalid_argument(
          "Index " +
          std::to_string(index) +
          " is out of bounds for list of size " + 
          std::to_string(this->size())
      );
    }
  }

public:
  LinkedList() {
    this->head = new Node(INT_MIN);
    this->tail = this->head;
  }

  static LinkedList* from(int arr[], int size) {
    LinkedList* ll = new LinkedList();
    for (int i = 0; i < size; i++) {
      ll->append(arr[i]);
    }
    return ll;
  }

  LinkedList* concat(LinkedList* ll) {
    for (int i = 0; i < ll->size(); i++) {
      this->append(ll->get(i));
    }
    return this;
  }

  void print() {
    std::cout << "[";
    Node *cur_node = this->head;
    while (cur_node->next) {
      cur_node = cur_node->next;
      std::cout << cur_node->value << (cur_node->next ? ", " : "");
    }
    std::cout << "]" << std::endl;
  }

  int size() {
    int size = -1;
    Node *cur_node = this->head;
    while (cur_node) {
      size++;
      cur_node = cur_node->next;
    }
    return size;
  }

  LinkedList* append(int value) {
    Node *new_node = new Node(value);
    tail->next = new_node;
    tail = tail->next;
    return this;
  }

  int get(int index) {
    this->validate_index(index);
    Node* cur_node = this->head;
    int cur_index = -1;

    while (cur_index != index) {
      cur_node = cur_node->next;
      cur_index++;
    }

    return cur_node->value;
  }

  void insert(int index, int value) {
    this->validate_index(index);
    Node* cur_node = this->head;
    Node* prev_node = NULL;
    int cur_index = -1;

    while (cur_index != index) {
      prev_node = cur_node;
      cur_node = cur_node->next;
      cur_index++;
    }

    Node* new_node = new Node(value);
    new_node->next = cur_node;
    new_node->prev = prev_node;
    cur_node->prev = new_node;
    prev_node->next = new_node;
  }

  int remove(int index) {
    this->validate_index(index);
    Node* cur_node = this->head;
    Node* prev_node = NULL;
    int cur_index = -1;

    while (cur_index != index) {
      prev_node = cur_node;
      cur_node = cur_node->next;
      cur_index++;
    }

    int value = cur_node->value;
    prev_node->next = cur_node->next;
    if (cur_node->next) {
      cur_node->next->prev = prev_node;
    }
    delete cur_node;
    return value;
  }

} LinkedList;

LinkedList* _quick_sort(LinkedList* ll) {
  if (ll->size() <= 1) {
    return ll;
  }


  int pivot = ll->remove(0);
  LinkedList* left = new LinkedList();
  LinkedList* right = new LinkedList();

  for (int i = 0; i < ll->size(); i++) {
    if (ll->get(i) <= pivot) {
      left->append(ll->get(i));
    } else {
      right->append(ll->get(i));
    }
  }

  return _quick_sort(left)->append(pivot)->concat(_quick_sort(right));
}

LinkedList* quick_sort(LinkedList* ll) {
  return _quick_sort(ll);
}

int main(){
  int nums[] = {20, 24, 1, 96, 16, 93, 92, 72, 3, 75, 86, 58, 68, 50, 19};
  LinkedList* ll = LinkedList::from(nums, sizeof(nums) / sizeof(nums[0]));
  LinkedList* sorted = quick_sort(ll);

  ll->print();
  sorted->print();
  return 0;
}