// by TheSky233 (www.luogu.com.cn/user/501865)
// 转载请标明出处 qwq
#include <bits/stdc++.h>
using namespace std;
template<typename T> T readIn(){
T x(0),f(0);
char ch=getchar();
while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return f?-x:x;
}
template<typename T> void write(T x){
static char buf[64];
static int tot(0);
if(x<0) putchar('-'),x=-x;
do buf[++tot]=(x%10)+48,x/=10; while(x);
do putchar(buf[tot--]); while(tot);
}
const int N=1e6+5;
int n, arr[N], len;
class Sort{
private:
int a[N];
public:
void readArray(){
n=readIn<int>();
for(int i=1;i<=n;i++) a[i]=readIn<int>();
}
void writeArray(){
for(int i=1;i<=n;i++) write(a[i]),putchar(' ');
}
void SelectionSort(){
for(int i=1;i<=n;i++){
int k=0,arr=(1<<30);
for(int j=i;j<=n;j++)
if(a[j]<arr) arr=a[j],k=j;
swap(a[i],a[k]);
}
}
void BubbleSort(){
for(int i=1;i<=n;i++){
bool flag=0;
for(int j=i+1;j<=n;j++)
if(a[i]>a[j]) swap(a[i],a[j]),flag=1;
if(!flag) break;
}
}
void InsertionSort(){
for(int i=1;i<=n;i++){
int k=a[i];
for(int j=i-1;j>=1;j--){
if(a[j]>k) swap(a[j],a[j+1]);
else break;
}
}
}
void ShellSort(){
int gap=1;
while(gap<n) gap=gap*3+1;
while(gap>=1){
for(int i=gap;i<=n;i++)
for(int j=i;j>=gap && a[j]<a[j-gap]; j-=gap)
swap(a[j],a[j-gap]);
gap/=3;
}
}
void QuickSort(int L,int R){
int tmp=a[(L+R)>>1],i=L,j=R;
do{
while(a[i]<tmp) i++;
while(a[j]>tmp) j--;
if(i<=j) swap(a[i],a[j]),i++,j--;
}while(i<=j);
if(i<R) QuickSort(i,R);
if(j>L) QuickSort(L,j);
}
void Merge(int l,int mid,int r,int *c){
int i=l,j=mid+1;
int L=mid,R=r;
int k=0;
while(i<=L && j<=R){
if(a[i]<a[j]) c[++k]=a[i++];
else c[++k]=a[j++];
}
while(i<=L) c[++k]=a[i++];
while(j<=R) c[++k]=a[j++];
for(int i=1;i<=k;i++) a[l+i-1]=c[i];
}
void MergeSort(int l,int r){
if(l>r || l==r) return;
int mid=(l+r)>>1;
MergeSort(l,mid);
MergeSort(mid+1,r);
Merge(l,mid,r,arr);
}
void put(int x){
arr[++len]=x;
int p=len;
while(p!=1&&arr[p/2]>arr[p]){
swap(arr[p],arr[p/2]);
p/=2;
}
}
int get(){
int p=1,q;
int x=arr[1]; arr[1]=arr[len]; len--;
while(p*2<=len){
if(p*2+1>len||arr[p*2]<arr[p*2+1]) q=p*2;
else q=p*2+1;
if(arr[p]>arr[q]){
swap(arr[p],arr[q]);
p=q;
}
else return x;
}
return x;
}
void HeapSort(){
for(int i=1;i<=n;i++) put(a[i]);
for(int i=1;i<=n;i++) a[i]=get();
}
void CountingSort(){
int l=a[min_element(a+1,a+n+1)-a];
int r=a[max_element(a+1,a+n+1)-a];
int k=r-l+1;
int c[k+5]={0};
for(int i=1;i<=n;i++) c[a[i]-l]++;
int tot=0;
for(int i=0;i<=k;i++)
for(int j=1;j<=c[i];j++)
a[++tot]=i+l;
}
void BucketSort(){
vector<int> bucket[n];
int bucket_size=a[max_element(a+1,a+n+1)-a]/n+1,p=0;
for(int i=0;i<n;i++) bucket[i].clear();
for(int i=1;i<=n;i++) bucket[a[i]/bucket_size].push_back(a[i]);
for(unsigned int d=0;d<n;d++){
for(int i=0;i<bucket[d].size();i++){
int k=bucket[d][i];
for(int j=i-1;j>=0;j--){
if(bucket[d][j]>k) swap(bucket[d][j],bucket[d][j+1]);
else break;
}
}
for(unsigned int i=0;i<bucket[d].size();i++) a[++p]=bucket[d][i];
}
}
void RadixSort(){
int d=(int)log10(a[max_element(a+1,a+n+1)-a])+1;
int cnt[10],radix=1;
for(int i=1;i<=d;i++){
for(int j=0;j<10;j++) cnt[j]=0;
for(int j=1;j<=n;j++){
int k=(a[j]/radix)%10;
cnt[k]++;
}
for(int j=1;j<10;j++) cnt[j]+=cnt[j-1];
for(int j=n;j>=1;j--){
int k=(a[j]/radix)%10;
arr[cnt[k]]=a[j];
cnt[k]--;
}
for(int j=1;j<=n;j++) a[j]=arr[j];
radix*=10;
}
}
}Array;
int opt;
int main(){
Array.readArray();
opt=readIn<int>();
switch(opt){
case 1: {Array.SelectionSort(); break;}
case 2: {Array.BubbleSort(); break;}
case 3: {Array.InsertionSort(); break;}
case 4: {Array.ShellSort(); break;}
case 5: {Array.QuickSort(1,n); break;}
case 6: {Array.MergeSort(1,n); break;}
case 7: {Array.HeapSort(); break;}
case 8: {Array.CountingSort(); break;}
case 9: {Array.BucketSort(); break;}
case 10: {Array.RadixSort(); break;}
}
Array.writeArray();
}