#include <iostream>
#include <cstdlib>

using namespace std;

//int Swap(int x,int y){
//   int tmp = x;
//   x=y;
//   y=tmp;
//}

int main(){
    int N=0, data[N], opsi, tmp, key, l=0, r, f=0;;
//    char lanjut;
//    do{
//      cout << "masukkan angka : "; cin >> data[N];
//      cout << "lanjut?[y/n] "; cin >> lanjut;
//      N++;
//    }while(lanjut == 'y' || lanjut == 'Y');
   cout << "batas : ";
   cin >> N;
   for(int i=0;i<N;i++){
      cout << "data ke " << i << " : ";
      cin >> data[i];
   }
    system("clear");
    cout << "data : ";
    for(int i=0; i < N; i++){
      cout<<data[i]<<" ";
    }
    cout << "\nKeyword : "; cin >> key;
    cout << "1. Bubble Sort\n2. Insertion Sort\n3. Selection Sort\n4. Shell Sort\n5. Quick Sort\n";
    cout << "masukkan pilihan : ";cin>>opsi;
    switch(opsi){
      case 1 :
         for(int i=0; i <= N-1; i++){
            for(int j=0; j < N-i-1; j++){
               if(data[j] > data[j+1]){
                  tmp = data[j];
                  data[j] = data[j+1];
                  data[j+1] = tmp;
               }
            }
         }
         break;
      case 2 :
         for(int i=0; i < N; i++){
               int j=i-1;
               int tmp=data[i];
            while(j>=0 && data[j] > tmp){
               data[j+1] = data[j];
               j--;
            }
         data[j+1] = tmp;
         }
         break;
      case 3 :
         int mins;
         for(int i=0; i < N; i++){
         mins=i;
            for(int j = i+1 ; j < N; j++){
               if(data[j]<data[mins]){
                  mins = j;
                  tmp = data[mins];
                  data[mins] = data[i];
                  data[i] = tmp;
               }
            }
         }
         break;
      case 4 :
         for (int gap=N/2; gap>0; gap/=2){
            for (int i=gap; i<N; i+=1){
                  int tmp = data[i];
                  int j;
               for (j=i; j>=gap && data[j-gap] > tmp; j-=gap)
                  data[j] = data[j-gap];
                  data[j] = tmp;
               }
            }
         break;
      case 5 :
         int tmp, pivot=data[(0+N)/2];
         int x=0, y=N;
         while(x<y){
            while(data[x]<pivot)
               x++;
            while(data[y]>pivot)
               y--;
            if(x<y)
            if (x <= y) {
                  tmp = data[x];
                  data[x] = data[y];
                  data[y] = tmp;
                  x++;
                  y--;
            }
         }
         break;
//      case 6 :
//         int awal=0,akhir=N,tengah;
//         int i,j,k;
//         if(awal<akhir){
//            tengah = awal+(akhir-awal)/2;
//            int n1 = tengah-awal+1;
//            int n2 = akhir-tengah;
//            int Awal[n1], Akhir[n2];
//            for (int i=0; i<n1; i++)
//                  Awal[i] = data[awal+i];
//            for (int j=0; j<n2; j++)
//                  Akhir[j] = arr[m + 1+ j];
//                  i = 0, j = 0, k = l;
//                while (i<n1 && j<n2){
//                    if (Awal[i] <= Akhir[j]){
//                        data[k] = Awal[i];
//                        i++;
//                    }
//                    else{
//                        data[k] = Akhir[j];
//                        j++;
//                    }
//                    k++;
//                }
//                while (i<n1){
//                    data[k] = Awal[i];
//                    i++;
//                    k++;
//                }
//                while (j<n2){
//                    data[k] = Akhir[j];
//                    j++;
//                    k++;
//                }
//         }
//         break;
    }
         for(int n=0;n<N;n++){
            cout << data[n] << " ";
         }
   int awal = 0;
    int akhir = N;
    int tengah = (awal+akhir)/2;
    while (awal <= akhir){
        if(data[tengah] < key)
        {
            awal = tengah + 1;

        }
        else if(data[tengah] == key){
            cout << "\nData " << key <<" di temukan di index "<< tengah+1 <<"\n";
            break;
        }
        else{
             akhir = tengah - 1;
        }
        tengah = (awal + akhir)/2;
    }
    if(awal > akhir){
        cout << "\nData "<< key <<" tidak di temukan.";
    }
}