#include <iostream>
#include <queue>

using namespace std;


/*                                               KOPIEC                                                                 */


class Heap {
private:
	int* kopiec;
	int capacity;
	int heap_size;
public:
	Heap(int c) {
		kopiec = new int[c];
		capacity = c;
	};

	Heap() {
		kopiec = new int[10];
		kopiec[0] = 12;
		kopiec[1] = 9;
		kopiec[2] = 10;
		kopiec[3] = 7;
		kopiec[4] = 9;
		kopiec[5] = 5;
		kopiec[6] = 9;
		kopiec[7] = 2;
		kopiec[8] = 1;
		kopiec[9] = 3;
		capacity = 10;
		heap_size = 10;
	};

	bool empty() {
		if (heap_size <= 0) {
			return true;
		}
		return false;
	};

	bool full() {
		if (capacity == heap_size) return true;
		return false;
	};

	int left(int i) {
		return 2 * i + 1;
	};

	int right(int i) {
		return 2 * i + 2;
	};

	int parent(int i) {
		return (i - 1) / 2;
	};

	int getSize() {
		return heap_size;
	};

	void setHeapSize(int s);

	int get(int i) {
		return kopiec[i];
	};

	void set(int i, int x) {
		kopiec[i] = x;
	};


	void up(int i) {
		if (i > 0) {
			int ojciec = parent(i);
			if (kopiec[i] > kopiec[ojciec]) {
				int temp = kopiec[i];
				kopiec[i] = kopiec[ojciec];
				kopiec[ojciec] = temp;
				up(ojciec);
			}
		}
	};




	void down(int i) {
		int wiekszy;
		int leftPos = left(i);
		int rightPos = right(i);
		if (leftPos <= heap_size && kopiec[leftPos] > kopiec[i]) {
			wiekszy = leftPos;
		}
		else wiekszy = i;

		if (rightPos <= heap_size && kopiec[rightPos] > kopiec[wiekszy]) {
			wiekszy = rightPos;
		}

		if (wiekszy != i) {
			int temp = kopiec[i];
			kopiec[i] = kopiec[wiekszy];
			kopiec[wiekszy] = temp;
			down(wiekszy);
		}

	};

	friend std::ostream& operator<<(std::ostream& out, Heap& h) {
		for (int i = 0; i < h.capacity; i++) {
			out << "[" << i << "]" << kopiec[i] << endl;
		}
		return out;
	};
};

/*                                               HASZOWANIE										    */


class HashTable1 {
private:
	string* t;
	int capacity;
	int ht_size;
public:
	HashTable1(int c) {
		t = new string[c];
		capacity = c;
		ht_size = 0;
		for (int i = 0; i < c; i++) {
			t[i] = "";
		}
	};

	int hashF(string s) {
		int d = s.length;
		unsigned int suma = 0;
		for (int i = 0; i < d; i++) {
			suma += pow(13, d - i - 1) * s[i];
		}
		return suma % 40;
	};

	void insert(string s) {
		int konflikt = 0;
		int temp;
		temp = hashF(s);
		if (t[temp] != "") {
			++konflikt;
			++temp;
			while (t[temp] != "") {
				++temp;
				temp = temp % 40;
			}
			t[temp] = s;
			ht_size++;
		}
		else {
			t[temp] = s;
			ht_size++;
		}
	};

	string search(string s) {
			int wart;
			wart = hashF(s);
			if (s == t[wart])
				return s;
			else
				for (int i = 0; i < capacity; i++) {
					if (s == t[wart + i])
						return s;
				}
			return "-1";
	};

	int searchs(string s) {
		int wart;
		wart = hashF(s);
		if (s == t[wart])
			return wart;
		else
			for (int i = 0; i < capacity; i++) {
				if (s == t[wart + i])
					return wart + i;
			}
		return -1;
	};

	friend ostream& operator<<(ostream& out, HashTable1& ht); //wypisuje tablicę (z numerami pól), pozostawia puste dla wolnych pól
};



/*                                               SORTOWANIE                                                                 */




void prosteWybieranieString(string tab[], int wielkosc) {
	for (int i = 0; i < wielkosc; i++) {
		int min = i;
		for (int j = i + 1; j < wielkosc; j++) {
			if (tab[min] < tab[j]) {
				min = j;
			}
			string temp = tab[j];
			tab[j] = tab[min];
			tab[min] = temp;
		}
	}

}


void prostaZamianaString(string tab[], int wielkosc) {
	for (int i = 0; i < wielkosc; i++) {
		for (int j = wielkosc - 1; j > i; j--) {
			if (tab[j - 1] > tab[j]) {
				string temp = tab[j];
				tab[j] = tab[j - 1];
				tab[j - 1] = temp;
			}
		}
	}
}

void prosteWstawianieString(string tab[], int wielkosc) {
	for (int i = 1; i < wielkosc; i++) {
		string temp = tab[i];
		int j = i - 1;
		while (j >= 0 && temp < tab[j]) {
			tab[j + 1] = tab[j];
			j--;
			tab[j + 1] = temp;
		}
	}
}


/*											GRAFY							*/

struct edge {
	int s;
	int t;
	int weight;
};

class Graph {
private:
	int** adjMatrix;
	int n;
public:
	Graph(int n, int m, edge edges[], bool directed = true) {
		adjMatrix = new int* [n];
		this->n = n;
		for (int i = 0; i < n; i++) {
			adjMatrix[i] = new int[n];
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				adjMatrix[i][j] = 0;
			}
		}
		for (int i = 0; i < m; i++) {
			adjMatrix[edges[i].s][edges[i].t] = 1;
			if (!directed) {
				adjMatrix[edges[i].t][edges[i].s] = 1;
			}
		}
	};

	int edgeCnt() {
		int edgesCount = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (adjMatrix[i][j] == 1) {
					edgesCount++;
				}
			}
		}
		return edgesCount;
	};

	int nodeCnt() {
		return n;
	};

	void insertEdge(int u, int v) {
		adjMatrix[u][v] = 1;
	};

	void deleteEdge(int u, int v) {
		adjMatrix[u][v] = 0;
	};

	bool check(int u, int v) {
		if (adjMatrix[u][v] == 1)
			return true;
		return false;
	};

	void bfs(int s) {
		bool* isVisited = new bool[n] {false};
		queue<int> q;
		isVisited[s] = true;
		q.push(s);
		cout << "[" << s << "] ";

		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int i = 0; i < n; i++) {
				if (adjMatrix[x][i] == 1 && !isVisited[i]) {
					q.push(i);
					isVisited[i] = true;
					cout << "[" << i << "] ";
				}
			}
		}
	};

	void dfs(int s) {
		static bool* isVisited = new bool[n] {false};
		isVisited[s] = true;
		cout << "[" << s << "] ";

		for (int i = 0; i < n; i++) {
			if (adjMatrix[s][i] == 1 && !isVisited[i]) {
				dfs(i);
			}
		}
	}

	friend ostream& operator<<(ostream& out, Graph& g) {
		for (int i = 0; i < g.n; i++) {
			for (int j = 0; j < g.n; j++) {
				out << "[" << i << "][" << j << "] " << g.adjMatrix[i][j] << endl;
			}
		}
		return out;
	};

	~Graph() {
		delete[]adjMatrix;
	};

	int find(int d[], int S[]) {

	}
};




int main()
{
	string test[] = { "k", "d", "a", "w", "o", "p", "l"};
	prosteWstawianieString(test, 7);
	for (int i = 0; i < 7; i++) {
		cout << "[" << i << "] " << test[i] << endl;
	}


	return 0;
}