#include <iostream>
#include <stdlib.h>
#include <cmath>

using namespace std;
const int jdata=1024*1024;

int data[jdata];
int sdata[jdata];

void min(int *data,int &index, int &value){
    index=0; value=data[index];
    for (int i=1; i<jdata; i++)
        if (value>data[i]) {
            value = data[i];
            index =i;
        }
}

void max(int *data,int &index, int &value){
    index=0; value=data[index];
    for (int i=1; i<jdata; i++)
        if (value<data[i]) {
            value = data[i];
            index =i;
        }
}

void selectionsort(int *data, int *sdata, bool asc){
    int index, value;
    for (int i=0; i<jdata; i++){
        if (asc){
            min(data,index, value);
            sdata[i]=value; data[index]=100000000;
        } else {
            max(data,index, value);
            sdata[i]=value; data[index]=-100000000;
        }
    }
}

void optimizedselectionsort(int *data, bool asc){
    int temp;
    for (int i=0; i<jdata-1; i++){
        for (int j=i+1; j<jdata; j++){
            if (asc){
                if (data[i] < data[j]){
                    temp = data[j]; data[j]=data[i]; data[i]=temp;
                }
            else {
                if (data[i] > data[j]){
                    temp = data[j]; data[j]=data[i]; data[i]=temp;
                }
            }
        }
        }
    }
    for (int i=0; i<jdata; i++) cout << data[i] <<endl;
}


void bubblesort(int *data, bool asc){
    int temp;
    for (int i=jdata-1; i>1; i--){
        for (int j=0; j<i; j++){
            if (asc){
                if (data[j]>data[j+1]){
                    temp=data[j]; data[j]=data[j+1];data[j+1]=temp;
                }
            } else {
                if (data[j]<data[j+1]){
                    temp=data[j]; data[j]=data[j+1];data[j+1]=temp;
                }
            }
        }
    }
}

void InsertionSort(int *data) {
      int i, j, tmp;
      for (i = 1; i < jdata; i++) {
            j = i;
            while (j > 0 && data[j-1] > data[j]) {
                  tmp = data[j];
                  data[j] = data[j-1];
                  data[j-1] = tmp;
                  j--;
            }
      }
}

void QuickSort(int *data, int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = data[(left + right) / 2];

      /* partition */
      while (i <= j) {
            while (data[i] < pivot)
                  i++;
            while (data[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = data[i];
                  data[i] = data[j];
                  data[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            QuickSort(data, left, j);
      if (i < right)
            QuickSort(data, i, right);
}




/*
  Fungsi merge untuk menggabungkan 2 buah array yang telah terurut sebelumnya
  Array ini bisa saja berisi hanya 1 element
  INPUT:
     numbers = array integer yang akan diurutkan sebagai hasil penggabungan 2 array
     left, mid, right = posisi kiri, tengah dan kanan array
  OUTPUT:
     Tidak ada, tetapi variable numbers akan berubah
*/
void Merge(int *data, int left, int mid, int right){
  //int * temp = new int [jdata];
  int temp [jdata];
  int i, left_end, num_elements, tmp_pos;

  left_end = (mid - 1);
  tmp_pos = left;
  num_elements = (right - left + 1);

  while ((left <= left_end) && (mid <= right)){
    if (data[left] <= data[mid])
    temp[tmp_pos++] = data[left++];
    else
    temp[tmp_pos++] = data[mid++];
  }

  while (left <= left_end) temp[tmp_pos++] = data[left++];

  while (mid <= right) temp[tmp_pos++] = data[mid++];

  for (i = 0; i < num_elements; i++) {
    data[right] = temp[right];
    right--;
    }
  }

/*
  Fungsi MergeSort untuk mengurutkan array satu bilangan dengan Merge sort
  Array ini bisa saja berisi hanya 1 element
  INPUT:
     numbers = array integer yang akan diurutkan sebagai hasil penggabungan 2 array
     left, mid, right = posisi kiri, tengah dan kanan array
*/
void MergeSort(int *data, int left, int right){
  int mid;

  if (right > left) {               //selama jumlah array masih > 1 lakukan hal ini
    mid = (right + left) / 2;       // bagi menjadi dua bagian
    MergeSort(data, left, mid);  //urutkan masing-masing
    MergeSort(data, (mid + 1), right);

    Merge(data, left, (mid+1), right);  //gabungkan hasilnya.
    }
}




int main(){
    int * data = new int [jdata];
    for (int i=0; i<jdata; i++) data[i]=random()%jdata;

    //testing maximum minimum
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;
    //int val,index;
    //max(data,val,index);
    //cout << "min :" << val << "  index:" << index <<endl;
    //min(data,val,index);
    //cout << "min :" << val << "  index:" << index <<endl;

    //testing selection sort
    //for (int i=1024-32; i<jdata; i++) cout << data[i] <<endl;
    //selectionsort(data,sdata,true);
    //cout <<endl;
    //for (int i=1024-32; i<jdata; i++) cout << sdata[i] <<endl;

    //testing optimizwd selection sort
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;
    //cout <<endl;
    //optimizedselectionsort(data,false);
    //cout <<endl;
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;

    //testing bubble sort
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;
    //bubblesort(data,true);
    //cout <<endl;
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;

    //testing Quick Sort
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;
    //QuickSort(data, 0, jdata - 1);
    //cout <<endl;
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;

    //testing Merge Sort
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;
    //MergeSort(data, 0, jdata - 1);
    //cout <<endl;
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;

    //testing Insertion sort
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;
    InsertionSort(data);
    //cout <<endl;
    //for (int i=0; i<jdata; i++) cout << data[i] <<endl;

    bool urut=true;
    for (int i = 1; i < jdata; i++)    // tampilkan bilangan, uncomment jika diperlukan
        if (data[i-1]>data[i]) {
            urut=false; break;
        }
    if (urut) cout << "data urut"; else cout << "data tidak urut";

}