Playground
#include <iostream> using namespace std; //soedini gi nizite left[] i right[], i smesti go rezultatot vo array[] void merge(int left[], int leftSize, int right[], int rightSize, int array[]); void sort(int array[], int N) { if (N <= 1) return /* void */; //podeli na dva dela [0..M-1, M..N-1] int M = N/2; //od 0 do M-1 ima tocno M elementi int leftSize = M; //od M do N-1 ima tocno N-M elementi int rightSize = N-M; int *left = new int[leftSize]; for (int i=0; i<leftSize; i++) left[i] = array[i]; int *right = new int[rightSize]; for (int i=M; i<N; i++) right[i-M] = array[i]; //podredi gi pomalite delovi sort(left, leftSize); sort(right, rightSize); //soedini gi left[] i right[] vo array[] merge(left, leftSize, right, rightSize, array); //izbrishi gi nizite left[] i right[] (koi gi alociravme dinamicki) delete [] left; delete [] right; } void merge(int left[], int leftSize, int right[], int rightSize, int array[]) { int leftCurrent=0, rightCurrent=0, arrayCurrent = 0; while (leftCurrent < leftSize && rightCurrent < rightSize) { //ima ushte elementi i vo left[] i vo right[] if (left[leftCurrent] < right[rightCurrent]) { //zemi element od levata niza array[arrayCurrent] = left[leftCurrent]; arrayCurrent++; leftCurrent++; } else { //zemi element od desnata niza array[arrayCurrent] = right[rightCurrent]; arrayCurrent++; rightCurrent++; } } while (leftCurrent < leftSize) { //nema vekje elementi vo desnata niza, no ima li vo levata? array[arrayCurrent] = left[leftCurrent]; arrayCurrent++; leftCurrent++; } while (rightCurrent < rightSize) { //nema vekje elementi vo levata niza, no ima li vo desnata? array[arrayCurrent] = right[rightCurrent]; arrayCurrent++; rightCurrent++; } } int main() { int N = 8; int array[] = {2, 7, 5, 6, 4, 8, 1, 3}; sort(array, 8); for (int i=0; i<N; i++) cout << array[i] << " "; return 0; }
Input data
Program output
no input
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!