Merge-sort and quick-sort are two advanced sorting algorithms which can obtain a
ID: 3863173 • Letter: M
Question
Merge-sort and quick-sort are two advanced sorting algorithms which can obtain an average running time complexity of O(n log n). Usually, the actual sorting time depends on the way the elements arranged themselves (We assume the sorting is in an ascending order in this question) Counting the inversions in an array is a way to measure the order. An inversion is a pair of elements (a_i, a_j) such that i a_j. For example, the array {2, 4, 1, 3, 5) has three inversions (2, 1), (4, 1), (4, 3). For a sorted array, the inversion number is 0. Implement a method with time complexity of O(n^2) to count how many inversions there are for a given array. Then print out the number of inversions for array {47, 24, 83, 78, 36, 17, 96, 55} Through using the divide and conquer technique, you can improve the time complexity of counting inversions to O(n logn). Implement a method to count inversions by modifying the code of merge sort. Then print out the number of inversions for array {96, 83, 78, 55, 47, 36, 24, 17}. In QuickSort, the element chosen as the pivot can be any element in an array. Pick the first element as the pivot. For array {47, 24, 83, 78, 36, 17, 96, 55}, write the numbers in the array after each partitioning step. Taking the first partitioning step for example, your answer should be 47 (as the pivot), {36, 24, 17, 47, 78, 83, 96, 55} (as the array after the partitioning step). In the real world, our unsorted data is not necessarily in a random order. The data could be almost sorted (i.e., its inversion number is small). In this situation, using neither the first element nor the last element as the pivot in QuickSort is a good choice. Because the two parts divided by the pivot element is quite uneven, this will make the QuickSort algorithm close to the worst case (O(n^2) in complexity). To avoid this situation, we can choose the pivot more wisely by picking a random element in the array. Implement a quicksort method by using a random element in the array as a pivot.Explanation / Answer
1)
#include <bits/stdc++.h>
int getInvCount(int arr[], int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i+1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;
return inv_count;
}
/* Driver progra to test above functions */
int main(int argv, char** args)
{
int arr[] = {47,24,83,78,36,17,96,55};
int n = sizeof(arr)/sizeof(arr[0]);
printf(" Number of inversions are %d ", getInvCount(arr, n));
return 0;
}
NUMBER OF INVERSION 13
2)
#include <bits/stdc++.h>
int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);
/* This function sorts the input array and returns the
number of inversions in the array */
int mergeSort(int arr[], int array_size)
{
int *temp = (int *)malloc(sizeof(int)*array_size);
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive function that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort(int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right > left)
{
/* Divide the array into two parts and call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left)/2;
/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid+1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}
/* This funt merges two sorted arrays and returns inversion count in
the arrays.*/
int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
/*this is tricky -- see above explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
/* Driver program to test above functions */
int main(int argv, char** args)
{
int arr[] = {96,83,78,55,47,36,24,17};
printf(" Number of inversions are %d ", mergeSort(arr, 5));
getchar();
return 0;
}
NUMBER OF INVERSION IS 10
3)
#include<stdio.h>
#include<stdlib.h>
void QuickSort(int*,int ,int );
int main()
{
int i,j,n,m,*arr;
printf("enter the amount of number to be sort ");
scanf("%d",&n);
printf("enter the values to be sort ");
arr=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
QuickSort(arr,0,n-1);
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
system(" pause");
return 0;
}
void QuickSort(int* arr,int start,int last)
{
int i=start+1,j=last,temp;
if(i>j)
return;
while(i<=j)
{
if(arr[i]<arr[start])
{
i++;
}
if(arr[j]>arr[start])
{
j--;
}
if(i<=j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
temp=arr[start];
arr[start]=arr[j];
arr[j]=temp;
QuickSort(arr,start,j-1);
QuickSort(arr,j+1,last);
}
4)
#include<iostream>
#include<cstdlib>
using namespace std;
int PARTITION(int [],int ,int );
void R_QUICKSORT(int [],int ,int );
int R_PARTITION(int [],int,int );
int main()
{
int n;
cout<<"Enter the size of the array"<<endl;
cin>>n;
int a[n];
cout<<"Enter the elements in the array"<<endl;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cout<<"sorting using randomized quick sort"<<endl;
int p=1,r=n;
R_QUICKSORT(a,p,r);
cout<<"sorted form"<<endl;
for(int i=1;i<=n;i++)
{
cout<<"a["<<i<<"]="<<a[i]<<endl;
}
return 0;
}
void R_QUICKSORT(int a[],int p,int r)
{
int q;
if(p<r)
{
q=R_PARTITION(a,p,r);
R_QUICKSORT(a,p,q-1);
R_QUICKSORT(a,q+1,r);
}
}
int R_PARTITION(int a[],int p,int r)
{
int i=p+rand()%(r-p+1);
int temp;
temp=a[r];
a[r]=a[i];
a[i]=temp;
return PARTITION(a,p,r);
}
int PARTITION(int a[],int p,int r)
{
int temp,temp1;
int x=a[r];
int i=p-1;
for(int j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp1=a[i+1];
a[i+1]=a[r];
a[r]=temp1;
return i+1;
}