Notebook

 This is an attempt to run odd-even sorting from two threads without using locks. I have used a vector and split the vector logically in two halves if the size is beyond a value (Here as an example kept size 10, that means if the vector size is more than 10, then two threads will spawn and parallelize (on multi-core) sorting on the elements of the vector container. Finally, after sorting each half by two threads, another sorting will be arranged to make it finally sorted.  The Wiki contains the details about Odd-Even sorting. It's a comparison sorting. The below code snippet is a simple approach to odd-even sorting with multi-threading without having locks. No Extra space was allocated/used in this scenario.  void partBySort(std::vector<int>* vec, size_t begIndex, size_t endIndex) {     if (begIndex == endIndex) return;     bool isSorted = false;     while (!isSorted)     {         isSorted = true;         for (size_t i = begIndex; i <= endIndex - 1; i += 2)         {    

 The simplest sorting algorithm is not bubble sort or insertion sort but known as stupid sort aka gnome sort . The time complexity is like a bubble sort. However, the code base size is much smaller. Possibly it offers the smallest code base size in the domain of the sorting algorithm. The details can be found on Wikipedia . Here goes the code: void gnomeSort(std::vector<int>& data) {     int pos = 0;     while (pos < data.size())     {         if (pos == 0 or data[pos] >= data[pos - 1])             pos += 1;         else          {             std::swap(data[pos], data[pos - 1]);             pos -= 1;         }     } } int main() {        std::vector<int> v4 = { 10, 0, 2, 33, 5, 77, 8, 19, 1, 7 };       gnomeSort(v4);       for (auto i: v4)          std::cout << i << " "; } Happy sorting...

 A simple implementation of Bucket Sort, using insertion sort to sort bucket elements.  #include <iostream> #include <cassert> #include <algorithm> #include <vector> template<class FwdIt, class compare = std::less<>> void insertionSort(FwdIt begin, FwdIt end, compare cmp = compare{}) {     for (auto it = begin; it != end; ++it)     {         auto const insertion = std::upper_bound(begin, it, *it, cmp);         std::rotate(insertion, it, std::next(it));         assert(std::is_sorted(begin, std::next(it), cmp));     } } void bucketSort(float arr[], int N) {     std::vector<std::vector<float>> arrBucket(N); // Created N empty buckets     /* Segregating array elements in different buckets*/     for (int i = 0; i < N; ++i)     {         int bucketIndx = N * arr[i];         arrBucket[bucketIndx].push_back(arr[i]);     }     for (int i = 0; i < N; ++i)         insertionSort(arrBucket[i].begin(), arrBucket[i].end()); // Sorting elements in

This is a variation of selection sort, it bring the largest pancake not yet sorted to the top with one flip; take it down to its final position with one more flip; and repeat this process for the remaining pancakes. The algorithm has been discussed in following wiki link: Pancake Sorting The algorithm is visually represented in following link: Pancake Sorting(Visualization) The idea of this sorting is similar to Selection Sort, here taking maximum items one by one and started placing those from last and at the same time reducing the vector size one by one. To place bigger items in order from last using flips two move to their respective positions. Here is the implementation using std::rotate() and std::reverse(). The output: 

This is an effort to implement insertion sort in C++ way using Standard Template Library. The below implementation is for vector of any type. Two STL libraries algorithm has been used. 1. std::lower_bound 2. std::rotate The implementation cross compiler compatible, tested on GNU C++ (5.4.0) and Microsoft C++ (2010). //g++  5.4.0 #include < iostream > #include < algorithm > #include < vector > template< typename T > void insertionSort(std::vector< T > &vec) { typedef typename std::vector< T >::value_type vt; typename std::vector< vt >::iterator itBegin = vec.begin(); typename std::vector< vt >::iterator itEnd = vec.end(); for(typename std::vector< vt >::iterator it = itBegin; it != itEnd; ++it) { typename std::vector ::iterator ins = std::lower_bound(itBegin, it, *it); std::rotate(ins, it, std::next(it)); } } int main() {     int arr[] = {34, 20, 99, 10, 23}; std::vector< int > v(s

In my last article have seen how we can leverage C++ STL to do selection sort on the vector of integers only. However, the selection sort wasn't very generic to accept vectors of any basic type and sort accordingly. The below program was an effort to make the same selection sort (ascending order) implementation for vectors of any type like vectors of integers, doubles, chars, etc. #include < iostream > #include < algorithm > #include < vector > template < class ForwardIterator1, class ForwardIterator2 > void iters_swap (ForwardIterator1 a, ForwardIterator2 b) {     std::swap (*a, *b); } template < typename T > void selectionSort(std::vector< T > &v) { // Selection sort typedef typename std::vector ::value_type vt; typename std::vector ::iterator it = v.begin(); while(it != v.end()) {     typename std::vector ::iterator i_Min = std::min_element (it, v.end()); iters_swap(i_Min, it); ++it; } } int main() {

Selection Sort using Standard Template Libraries (not C++ 11): Selection sort works by finding smallest element from the list unsorted list, swap with leftmost element and proceed until all the elements are in order. Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on. Hence the complexity is  O(N^2) . The C++ implementation is like below: #include < iostream > #include < algorithm > #include < vector > template < class ForwardIterator1, class ForwardIterator2 > void iters_swap (ForwardIterator1 a, ForwardIterator2 b) {      std::swap (*a, *b); } template < typename T > void selectionSort(T &v) { // Selection sort std::vector ::iterator it = v.begin(); while(it != v.end()) {         std::vector ::iterator i_Min = std::min_element(it,