Sort Methods

sorts_n2.hpp

#include <vector>

template <class T>
  void bubble_sort(std::vector<T> &vec) {
    //Bubble Sort
    T tmp;
      for (unsigned int i = 0; i < vec.size(); i++) {
        for (unsigned int j = 0; j < vec.size()-1; j++) {
          if (vec[j] > vec[j+1]) {
            tmp = vec[j];
            vec[j] = vec[j+1];
            vec[j+1] = tmp;
          }
        }
      }
  }

template <class T>
  void cocktail_sort(std::vector<T> &vec) {
    //Cocktail Sort or Shacker Sort
    unsigned int left_edge = 0;
    unsigned int right_edge = vec.size() - 1;
    T tmp;
    while (left_edge <= right_edge) {
      for (unsigned int i = left_edge; i < right_edge; i++) {
        if (vec[i] > vec[i+1]) {
          tmp = vec[i];
          vec[i] = vec[i+1];
          vec[i+1] = tmp;
        }
      }
      right_edge -= 1;
      for (unsigned int i = right_edge; i > left_edge; i--) {
        if (vec[i-1] > vec[i]) {
          tmp = vec[i];
          vec[i] = vec[i-1];
          vec[i-1] = tmp;
        }
      }
      left_edge += 1;
    }
  }

template <class T>
  void insertion_sort(std::vector<T> &vec) {
    //Insertion Sort
    //Implementation like Gnome Sort (Stupid Sort)
    T tmp;
    for (unsigned int i = 1; i < vec.size(); i++) {
      for (unsigned int j = i; j > 0; j--) {
        if (vec[j] < vec[j-1]) {
          tmp = vec[j];
          vec[j] = vec[j-1];
          vec[j-1] = tmp;
        } else {
          break;
        }
      }
    }
  }

sorts_n2.py

def selection_sort(a: list):
    length = len(a)
    for i in range(length):
        current_min_i = i
        for j in range(i, length):
            if a[j] < a[i]:
                current_min_i = j
            a[i], a[current_min_i] = a[current_min_i], a[i]

def bubble_sort(a: list):
    length = len(a)
    for i in range(length):
        for j in range(i, length):
            if a[j] < a[i]:
                a[i], a[j] = a[j], a[i]

def shaker_sort(a: list):
    left = 0
    right = len(a) - 1
    while left <= right:
        for i in range(left, right):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
        right -= 1
        for i in range(right, left, -1):
            if a[i] < a[i - 1]:
                a[i], a[i - 1] = a[i - 1], a[i]
        left += 1

def gnome_sort(a: list):
    length = len(a)
    for i in range(1, length):
        j = i
        while j >= 1 and a[j] < a[j-1]:
            a[j], a[j-1] = a[j-1], a[j]
            j -= 1

def insertion_sort(a: list):
    length = len(a)
    for i in range(1, length):
        j = i
        current_min = a[i]
        current_min_i = i
        while j >= 1 and a[j] < a[j-1]:
            current_min = a[j]
            current_min_i = j
            j -= 1
        a[i], a[current_min_i] = tmp, a[i] 

sorts_nlogn.py

def qsort(list_: list):
    if not(list_):
        return []

    pivot = list_[0]
    lesser = qsort([x for x in list_[1:] if x < pivot])
    greater = qsort(list(set(list_[1:]) - set(lesser)))
    return lesser + [pivot] + greater
  
def merge(a: list, b: list):
    a_len = len(a)
    b_len = len(b)
    result = [0] * (a_len + b_len)
    a_idx = 0
    b_idx = 0
    result_idx = 0
    while a_idx < a_len and b_idx < b_len:
      if a[a_idx] <= b[b_idx]:
        result[result_idx] = a[a_idx]
        a_idx += 1
      else:
        result[result_idx] = b[b_idx]
        b_idx += 1
      result_idx += 1
    while a_idx < a_len:
      result[result_idx] = a[a_idx]
      a_idx += 1
      result_idx += 1
    while b_idx < b_len:
      result[result_idx] = b[b_idx]
      b_idx += 1
      result_idx += 1
    return result

def merge_sort(a: list):
    length = len(a)
    if length < 2:
      return a
    middle_idx = length // 2
    left_part = a[:middle_idx]
    right_part = a[middle_idx:]
    merge_sort(left_part)
    merge_sort(right_part)
    result = merge(left_part, right_part)
    for i in range(length):
      a[i] = result[i]