четверг, 13 июня 2013 г.

Insert Sort (Сортировка вставками)


Сортировка вставками:
template <typename T>
void insertSort(T arr[], int left, int right)
{
int j = 0;
for (int i = left; i < right; ++i)
{
j = i;
T tmp = arr[i];
while (arr[j - 1] > tmp && j > 0 )
{
arr[j] = arr[j - 1];
--j;
}
arr[j] = tmp;
}
}

Selection Sort (Сортировка выбором)

Идея: ищем наименьший элемент - ставим на первое место массива, ищем второй наименьший элемент - ставим на второе место и т.д.  Причем кол-во итераций поиска следующего наименьшего элемента равно N - 1, т.к. последний элемент после сортировки предыдущих и так будет на своем месте.

Функция меняющая позиции двух элементов: 


template<typename T>
void mySwap(T &first, T &second)
{
T tmp = first;
first = second;
second = tmp;
}

Сортировка выбором:
template <typename T>
void selectionSort(T arr[], int left, int right)
{
for (int i = left; i < right - 1; ++i)
{
int min = i;
for (int j = i + 1; j < right; ++ j)
{
if (arr[min] > arr[j])
{
min = j;
}
}
mySwap(arr[min], arr[i]);
}
}

пятница, 7 июня 2013 г.

Наибольший общий делитель (greatest сommon divisor)

Функция находит наибольший общий делитель при first > second


int greatestCommonDivisor(int first, int second)
{
if (second == 0)
{
return first;
}
return greatestCommonDivisor(second, first % second);
}

Random Queue (имитация неупорядоченной очереди)

Из данной очереди элементы удаляются в случайном порядке.


#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

template<typename T>
class RandomQueue
{
public:
RandomQueue(int size);
~RandomQueue();

void put(T item);
T get();
bool empty();
private:
T *m_random;
T m_head;
T m_tail;
T m_tmp;
};

template<typename T>
RandomQueue<T>::RandomQueue(int size)
{
m_tmp = size + 1;
m_head = m_tmp;
m_tail = 0;
m_random = new T[size + 1];
}

template<typename T>
RandomQueue<T>::~RandomQueue()
{
delete[] m_random;
}

template<typename T>
void RandomQueue<T>::put(T item)
{
if (m_tail < m_tmp - 1)
{
m_random[m_tail++] = item;
}
else
{
cout << "Queue is fill" << endl;
}
}

template<typename T>
T RandomQueue<T>::get()
{
if(m_tail > 0)
{
T outputItem;
srand(time(0));
m_head = rand()%m_tail;

outputItem = m_random[m_head];
for (int i = m_head; i < m_tail; ++i) //Смещаем все элементы на один влево
{                                                   //Заполняя получившийся пробел
m_random[i] = m_random[i + 1];
}
--m_tail;   //Номер хвоста

return outputItem;
}
}

template<typename T>
bool RandomQueue<T>::empty()
{
return (m_tail == 0);
}

среда, 5 июня 2013 г.

QUEUE (Реализация упрощенной очереди через список)


#include <iostream>
using namespace std;

template<typename T>
class MyQueue
{
public:
MyQueue();

void put(T item);
T get();
bool empty();
private:
struct Node
{
T m_item;
Node *m_next;
Node(T item);
};
Node *m_head;
Node *m_tail;
};

template<typename T>
MyQueue<T>::Node::Node(T item)
{
m_item = item;
m_next = 0;
}

template<typename T>
MyQueue<T>::MyQueue()
{
m_head = 0;
m_tail = 0;
}

template<typename T>
void MyQueue<T>::put(T item)
{
Node *tmp = m_tail;
m_tail = new Node(item);
(0 == m_head) ? m_head = m_tail : tmp->m_next = m_tail;
}

template<typename T>
T MyQueue<T>::get()
{
T tmpItem = m_head->m_item;
Node *tmp = m_head->m_next;

delete m_head;
m_head = tmp;

return tmpItem;
}

вторник, 4 июня 2013 г.

Стек (упрощенная реализация)

в  файле MyStack.h :


#include <iostream>
using namespace std;

template<typename T>
class MyStack
{
public:
MyStack();
MyStack(int size);
MyStack(const MyStack<T> &over);
~MyStack();
MyStack<T>& operator=(const MyStack<T> &over);

T pop();
void push(T item);
bool empty() const;
private:
int m_top;
int m_size;
T *m_stack;
};

template<typename T>
MyStack<T>::MyStack()
: m_top(-1)
, m_size(10) // по умолчанию стек на 10 элементов
{
m_stack = new T[m_size];
}

template<typename T>
MyStack<T>::MyStack(int size)
: m_top(-1)
, m_size(size)
{
m_stack = new T[m_size];
}

template<typename T>
MyStack<T>::~MyStack()
{
delete[] m_stack;
}

template<typename T>
MyStack<T>::MyStack(const MyStack<T> &over)
{
m_top = over.m_top;
m_size = over.m_size;
m_stack = new T[m_size];

for (int i = 0; i <= m_top; ++i)
{
m_stack[i] = over.m_stack[i];
}
}

template<typename T>
MyStack<T>& MyStack<T>::operator=(const MyStack<T> &over)
{
if (this != &over)
{
m_top = over.m_top;
m_size = over.m_size;

delete[] m_stack;
m_stack = new T[m_size];

for (int i = 0; i <= m_top; ++i)
{
m_stack[i] = over.m_stack[i];
}
}
return *this;
}

template<typename T>
T MyStack<T>::pop()
{
if (-1 != m_top)
{
return m_stack[m_top--];
}
else
{
cout << "Stack is empty ";
cout << endl;
}
}

template<typename T>
void MyStack<T>::push(T item)
{
if ( m_top != m_size - 1)
{
m_stack[++m_top] = item;
}
else
{
cout << "Stack is fill ";
cout << endl;
}
}

template<typename T>
bool MyStack<T>::empty() const
{
return (-1 == m_top);
}

main.cpp:


#include "MyStack.h"

int main()
{
MyStack<int> obj1(2);
MyStack<int> obj2;
obj1.push(20);
obj1.push(10);

obj2 = obj1;
cout << obj2.pop() << endl;
cout << obj2.pop() << endl;
return 0;
}

Сортировка списка вставкой

Сортировка довольно медленная О(n в квадрате). Для сортировки большого кол-ва элементов не пойдет. Использовались фиктивные узлы указывающие на головы списков.
Идея  : берем неотсортированный список и по очереди вытаскиваем из него узлы (current). Данный узел помещаем в отсортированный список, который вначале состоит из одного фиктивного узла.

Сортировка списка методом вставки:


void listSort(Node *notSorted, Node *sorted)
{
Node *current; //указывает на узел из неотсортированного списка
Node *nextPosition; //указывает на следующий после текущего
Node *afterWhichInsert; //после которого следует вставка

for (current = notSorted->m_next; current != 0; current = nextPosition)
{
nextPosition = current->m_next; //сохраняем указатель на след. узел
for (afterWhichInsert = sorted; afterWhichInsert->m_next != 0;
                      afterWhichInsert = afterWhichInsert->m_next)
{
if (afterWhichInsert->m_next->m_item > current->m_item)
{
break;
}
}
current->m_next = afterWhichInsert->m_next;
afterWhichInsert->m_next = current;
}
}

main :

int main()
{
srand(time(0));

Node *headNotSorted = new Node(0, 0);  //Фиктивный узел указывает на голову                  неотсортированного списка
Node *headSorted = new Node(0, 0);   //Фиктивный узел указывает на голову отсортированного списка

Node *current = headNotSorted;

for(int i = 1; i < 10; ++i)   //Заполняем список случайными числами
{
current->m_next = new Node(rand()%100, 0);
current = current->m_next;
}
print(headNotSorted->m_next);

listSort(headNotSorted, headSorted);
print(headSorted->m_next);

return 0;
}