EvilZone
Programming and Scripting => C - C++ => : 0poitr March 25, 2014, 04:23:12 PM
-
My implementations of some sorting algorithms. You can use them in your code or for educational purposes. The code is mostly uncommented except for the radix sort, so I guess it could be a bit tricky to understand the workings; the variables themselves are descriptive of what they are used for, though.
// ==================================================================//
//
// Sorting algorithms:
// O(n2) Bubble, Selection, Insertion
// O(nlogn) Quick, Merge (both iterative & recursive), Heap
//
// Radix Sort (LSD)
// http://en.wikipedia.org/wiki/Radix_sort#Efficiency
//
// Author: 0poitr @ evilzone.org, 2014
// Permission for use and modification of the code.
//
// For knowledge and some interestng discussion on the algorithms,
// you can consider their wikipedia pages and references.
//
// ==================================================================//
#include <iostream>
#define ULONG unsigned long
#define MIN(a, b) (a) < (b) ? (a) : (b)
#define mergeSortRecursive(x, y, len) mergeSortRecursive_(x, y, len-1);
using namespace std;
// prototype declarations
template <class T> void selectSort(T *a, int size);
template <class T> void bubbleSort(T *a, int size);
template <class T> void insSort(T *a, int size);
template <class T> int partition(T *a, int lb, int ub);
template <class T> void quickSort(T *a, int size);
template <class T> void quickSortRecursive(T *a, int lb, int ub);
template <class T> void reHeap(T *a, int start, int end);
template <class T> void heapSort(T *a, int size);
template <class T> void mergeParts(T *a, int lb, int mid, int ub);
template <class T> void mergeSort(T *a, int size);
template <class T> void mergeSortRecursive_(T *a, int lb, int ub);
template <class T> void display(T *a, int size);
template <class T> void radixSort(T *a, int size);
template <class T> void reNew(T **ptr, int *size);
template <class T> void push(T *a, T data);
template <class T> int pop(T *a);
int stackEmpty();
template <class T> void swap(T *a, int h, int l);
void freeMem(int **b);
// =====================
// auxiliary functions
int stack_top=0;
template <class T> void push(T *a, T data)
{
a[stack_top++] = data;
}
template <class T> int pop(T *a)
{
return a[--stack_top];
}
int stackEmpty()
{
if (!stack_top) return 1;
return 0;
}
template <class T> void swap(T *a, int h, int l)
{
int tmp = a[l];
a[l] = a[h];
a[h] = tmp;
}
// ==================
// selection sort
template <class T> void selectSort(T *a, int size)
{
int i, lowest;
for (i=0; i<size-1; i++) {
lowest = i;
for (int j=i+1; j<size; j++)
if (a[j] < a[lowest]) lowest = j;
if (i!=lowest) swap(a, i, lowest);
}
}
// ==================
// bubble sort
template <class T> void bubbleSort(T *a, int size)
{
for (int i=0; i<size; i++) {
bool work = false;
for (int j=0; j<size-i-1; j++) {
if (a[j] > a[j+1]) {
swap(a, j, j+1);
work = true;
}
}
if (!work) break;
}
}
// ==================
// insertion sort
template <class T> void insSort(T *a, int size)
{
int j, i;
for (i=1; i<size; i++) {
int tmp = a[i];
for (j=i-1; j>=0 && tmp < a[j]; j--)
a[j+1] = a[j];
a[j+1] = tmp;
}
}
// ===================
// quick sort
template <class T> int partition(T *a, int lb, int ub)
{
// considering the middle element as pivot avoids unnecessary
// passes in case array is already sorted. Never suffer O(n2).
swap(a, lb, (lb+ub)/2);
int small_end = lb;
for (int large_end=lb; large_end<ub; large_end++) {
if (a[large_end+1] < a[lb])
swap(a, ++small_end, large_end+1);
}
swap(a, lb, small_end);
return small_end;
}
template <class T> void quickSort(T *a, int size)
{
int lb=0, ub=size, pivot;
int stack[size*2];
push(stack, lb);
push(stack, ub);
while (!stackEmpty()) {
ub = pop(stack);
lb = pop(stack);
if (lb >= ub) continue;
pivot = partition(a, lb, ub);
push(stack, lb);
push(stack, pivot-1);
push(stack, pivot+1);
push(stack, ub);
}
}
template <class T> void quickSortRecursive(T *a, int lb, int ub)
{
if (lb >= ub) return;
int p_end = partition(a, lb, ub);
quickSortRecursive(a, lb, p_end-1);
quickSortRecursive(a, p_end+1, ub);
}
// =================
// heap sort
template <class T> void reHeap(T *a, int start, int end)
{
while (start*2+1 <= end) {
int ch_indx = start*2 +1;
int sw_indx = start;
if (a[sw_indx] < a[ch_indx])
sw_indx = ch_indx;
if (ch_indx+1 <= end && a[sw_indx] < a[ch_indx+1])
sw_indx = ++ch_indx;
if (sw_indx != start)
swap(a, sw_indx, start);
else
return;
start = sw_indx;
}
}
template <class T> void heapSort(T *a, int size)
{
int last_root = (size-2)/2;
while (last_root >= 0) {
reHeap(a, last_root, size-1);
last_root--;
}
int last = size-1;
while (last > 0) {
swap(a, 0, last);
reHeap(a, 0, --last);
}
}
// =================
// mergesort
template <class T> void mergeParts(T *a, int lb, int mid, int ub)
{
T storage[ub-lb+1];
int i, j, k;
//cout<<"lb: "<<lb<<" ub: "<<ub<<endl;
for (i=lb, k=0, j=mid+1; i<=mid && j<=ub; k++)
storage[k] = a[i] < a[j] ? a[i++] : a[j++];
while (i <= mid)
storage[k++] = a[i++];
while (j <= ub)
storage[k++] = a[j++];
j=lb;
for (i=0; i<=ub-lb; i++)
a[j++] = storage[i];
}
template <class T> void mergeSort(T *a, int size)
{
int i,j;
for (i=1; i<=size; i=i*2) {
for (j=0; j<size-i; j=j+i*2)
// mid = (j + j+2*i)/2 = i+j
mergeParts(a, j, j+i-1, MIN(j+2*i-1, size-1));
}
}
template <class T> void mergeSortRecursive_(T *a, int lb, int ub)
{
if (lb >= ub) return;
int mid = (ub+lb)/2;
mergeSortRecursive_(a, lb, mid);
mergeSortRecursive_(a, mid+1, ub);
mergeParts(a, lb, mid, ub);
}
// ===================
// radix sort
#define BASE 10
#define MAX 32
template <class T> void reNew(T **ptr, int *size)
{
T *tmp = new T [*size+MAX];
for (int i=0; i<*size; i++)
tmp[i] = *((*ptr)+i);
delete *ptr;
*ptr = tmp;
(*size) += MAX;
}
void freeMem(int **b)
{
for (int i=0; i<BASE; i++)
delete b[i];
}
template <class T> void radixSort(T *a, int size)
{
int *buckets[BASE]; // BASE number of buckets
int indx_t[BASE][BASE] = { 0 }; // tracks current index for each bucket and bucket size
int i; // indx on row [0], bucket size on [1]
long highest = a[0];
for (i=0; i<BASE; i++) { // initially fixed amount of mem for each bucket
buckets[i] = new T [MAX];
indx_t[1][i] = MAX;
}
for (i=0; i<size; i++)
if (a[i] > highest) highest=a[i];
ULONG m=10, n=1;
ULONG indx;
while (highest*10 >= m) {
// put numbers into buckets
for (i=0; i<size; i++) {
indx = (a[i] % m) / n;
buckets[indx][indx_t[0][indx]++] = a[i];
// if next indx > current size, reallocate mem for bucket
if ( !(indx_t[0][indx] % indx_t[1][indx]) )
reNew(&buckets[indx], &indx_t[1][indx]);
}
// copy back and reset index counters
indx=0;
for (i=0; i<BASE; i++) {
int j = 0;
while (j < indx_t[0][i])
a[indx++] = buckets[i][j++];
indx_t[0][i] = 0;
}
m *= BASE;
n *= BASE;
}
freeMem(buckets);
}
// ===================
// display
template <class T> void display(T *a, int size)
{
for (int i=0; i<size; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
}
// ==================
int main()
{
int data[] = {5,382,132,22,702,52,62,102,52,26};
int len = sizeof(data)/sizeof(data[0]);
display(data, len);
mergeSort(data, len);
//mergeSortRecursive(data, 0, len);
//quickSortRecursive(data, 0, len);
//radixSort(data, len);
display(data, len);
}
-
These can be optimized quite a bit with things like range-for loops and more of some niceties from C++11. Also it looks like you reimplemented std::stack? Why?
-
These can be optimized quite a bit with things like range-for loops and more of some niceties from C++11. Also it looks like you reimplemented std::stack? Why?
My excuse would be, I'm just learning C++. Coming from the lands of bare bones C unaware of most of the facilities it's younger sibling provides. Can you demonstrate some language optimizations you are talking about ?
-
My excuse would be, I'm just learning C++. Coming from the lands of bare bones C unaware of most of the facilities it's younger sibling provides. Can you demonstrate some language optimizations you are talking about ?
iterators:
This is the most efficient for-loop in c++:
for (auto it = vector.begin(), end = vector.end();it != end;++it)
{}
And if you don't need to modify elements it can just be written as:
for (auto object : vector)
{}
which expands to:
for (auto it = vector.begin();end != vector.end();++it)
{
auto object = *it;
<your code here>
}
Other optimizations:
std::stack, std::vector, std::set, std::map
And then there is of course the actual algorithm optimizations, ie. try to get Big-Theta or Big-O (n) or less but really, things like sorting algorithms will be O(n log n) in best case.
-
Even if you need to modify elements, you don't need the full syntax...
for (auto &it : vector)
{
// modify (it) here
}
If using C++11, you can also use constexpr if your compiler supports it.
-
My compiler cries for not supporting anything beyond C++98, and i thought it was the latest release.
With C++11, alot of code can be dropped and even lossing the rik of even more errors/bugs.
Also you might wanna look at the BOOST library which also provides more power and optimization.
-
My compiler cries for not supporting anything beyond C++98, and i thought it was the latest release.
With C++11, alot of code can be dropped and even lossing the rik of even more errors/bugs.
Also you might wanna look at the BOOST library which also provides more power and optimization.
Eh boost can be a bit bloated but I'm slowly changing my mind on it.
Even if you need to modify elements, you don't need the full syntax...
for (auto &it : vector)
{
// modify (it) here
}
If using C++11, you can also use constexpr if your compiler supports it.
I tried doing that before and my compiler just kept on complaining. It might be in the spec, I haven't checked, but I know the latest stable release of clang doesn't support it if it is in the spec.
-
Some BOOST libraries have become implemented by the language by the standards committee AFAIK. I have no problem with most of their libraries.
@bluechill:
http://ideone.com/aiAZVv (http://ideone.com/aiAZVv)
http://coliru.stacked-crooked.com/ (http://coliru.stacked-crooked.com/)
http://gcc.godbolt.org/ (http://gcc.godbolt.org/)
Compiles fine with Clang 3.3... Didn't test 3.4, but you must have not understood how to use the range-based for loop with the auto specifier... OR, perhaps you have to configure Clang a bit more?
Latest stable release doesn't support it? http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2930.html (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2930.html)
Range-based for N2930 Clang 3.0
Was available since 3.0. And the auto type-specifier has been available since 2.9.
Try it without the auto type-specifier:
int main()
{
int arr[] = {1, 2, 3, 4, 5};
for (const int &i : arr)
{
std::cout << i << std::endl;
}
}
-
Some BOOST libraries have become implemented by the language by the standards committee AFAIK. I have no problem with most of their libraries.
@bluechill:
http://ideone.com/aiAZVv (http://ideone.com/aiAZVv)
http://coliru.stacked-crooked.com/ (http://coliru.stacked-crooked.com/)
http://gcc.godbolt.org/ (http://gcc.godbolt.org/)
Compiles fine with Clang 3.3... Didn't test 3.4, but you must have not understood how to use the range-based for loop with the auto specifier... OR, perhaps you have to configure Clang a bit more?
Latest stable release doesn't support it? http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2930.html (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2930.html)
Range-based for N2930 Clang 3.0
Was available since 3.0. And the auto type-specifier has been available since 2.9.
Try it without the auto type-specifier:
int main()
{
int arr[] = {1, 2, 3, 4, 5};
for (const int &i : arr)
{
std::cout << i << std::endl;
}
}
No I was talking about using auto to modify elements. The issue is that for-range loops are supposed to expand out to:
for (iterator it = vec.begin(), end = vec.end();it != end;++it)
{
entry = *it;
.. Your code here ..
}
As you'll note, entry is a dereferenced pointer, ie. a value and adding the & for reference didn't work for modifying elements in Clang 3.4
-
#include <iostream>
#include <iterator>
#include <algorithm>
int main()
{
const int len = 5;
int arr[len] = {1, 2, 3, 4, 5};
for (int *it = arr; it != arr + len; ++it) *it = 1;
std::copy(arr, arr + len, std::ostream_iterator<int>(std::cout, " "));
std::endl(std::cout);
int k = 0;
for (auto &it : arr) it = ++k * 2;
std::copy(arr, arr + len, std::ostream_iterator<int>(std::cout, " "));
std::endl(std::cout);
}
I get output:
1 1 1 1 1
2 4 6 8 10
How do you assume they are supposed to expand to that? If they did, how would you increment a reference which refers to the type data, and not a place in memory to get to the next element? It's not meant to, 100% of the time, expand out to an iterator object. (Below example is essentially proof of that.)
here's a reference http://www.cprogramming.com/c++11/c++11-ranged-for-loop.html (http://www.cprogramming.com/c++11/c++11-ranged-for-loop.html)
Here's a more accurate representation of what a reference based auto range-based for loop looks like:
const int new_value = 7;
for (auto n = &arr[0], last = &arr[len]; n != last; ++n)
{
int &it = *n;
it = new_value;
}
std::copy(arr, arr + len, std::ostream_iterator<int>(std::cout, " "));
std::endl(std::cout);
Modified values pretty easy. :)
Here was the ASM decompiled from a different test:
lea eax,[arr]
mov dword ptr [ebp-34h],eax
mov eax,dword ptr [ebp-34h]
mov dword ptr [ebp-40h],eax
mov eax,dword ptr [ebp-34h]
add eax,14h
mov dword ptr [ebp-4Ch],eax
jmp main+72h (010A53E2h)
mov eax,dword ptr [ebp-40h]
add eax,4
mov dword ptr [ebp-40h],eax
mov eax,dword ptr [ebp-40h]
cmp eax,dword ptr [ebp-4Ch]
je main+82h (010A53F2h)
mov eax,dword ptr [ebp-40h]
mov dword ptr [ebp-58h],eax
jmp main+69h (010A53D9h)
http://en.cppreference.com/w/cpp/language/range-for (http://en.cppreference.com/w/cpp/language/range-for)
-
Back to basic:
Range-for loop basic structure:
for (declaration:expression)
{
//do something
}
expression must represent a sequence like an array, braced initialiser list (c++11 they have begin() and end() functions), or objects like vectors or strings which have begin and end member functions that return iterators.
declarationdefines a variable. It must be possible to convert each element of the sequence (in expression) to the variable's type.
[Now the fun] It is only best that we use auto type specifier to ensure that the types match since this way the compiler will choose it for us.
If we want to write to the elements in the sequence the the loop variable must be a reference type; vector<int> vec = {0, 1, 2, 3, 4}
for (auto &count : vec)
{
count *= 2;
}
On each iteration, count is initialised with the next element in the sequence, then anything in the block is executed against the element with the to change whatever count holds/points to.
It doesn'tnecessarily have to expand to the traditional for.