We define a simple sorting algorithm as one that sorts n elements into ascending

Question

We define a simple sorting algorithm as one that sorts n elements into ascending order in O(n^2) time. An array A holds N = 3^p integers (for integer p). Consider the following sorting algorithm for the array A: Define two overlapping sub-arrays of A: A_L = A[0, ..., 2/3 N - 1], and A_H = A[1/3 N, ..., N - 1] {For example, if N = 9, Al =^4[0, .... 5] and Ah = .4(3, .... 8]} Sort the elements of A_L l using a simple sorting algorithm. Sort the elements of A_H using a simple sorting algorithm. Sort the elements of A_L using a simple sorting algorithm.. (a) Prove that this algorithm does sort the elements of A into ascending order. (b) Give an equation for the running time of this algorithm. (c) Develop an equation for the running time of an algorithm that applies the above strategy recursively.

Explanation / Answer

#include<iostream>

#include<stdio.h>

#include<fstream>

#include<sstream>

#include<stdlib.h>

#include<string>

#include<map>

#include<vector>

using namespace std;

int *a;

void sorting(int l1, int r1, int l2, int r2) {

int curr=l1;

int i,j;

for(i=l1;i<r1;++i) {

for(j=l2;j<r2;++j) {

if(a[i]<a[j]) {

a[curr++]=i;

break;

}

}

}

for(j=r1;j<r2;++j) a[curr++]=j;

}

static int kk=0;

void sort_call(int l, int r, int c) {

int m=(2*c)/3;

if(m<2) return;

sort_call(l,l+m,m);

sort_call(r-m,r,m);

sorting(l,l+m,r-m,r);

}

int main() {

int n;

cin>>n;

a=(int*)malloc(sizeof(int)*n);

for(int i=0;i<n;++i) a[i]=i;

sort_call(0,n,n);

for(int i=0;i<n;++i) cout<<a[i]<<" ";

}

2. Complexity is O(4n/3)+c*(n^2) (c is a constant integer)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.