Write a program to sort a given array of numbers. The sorting algorith

1.	Write a program to sort a given array of numbers. The sorting algorithm should give best performance in every case (best, worst and average). Example : Input : arr = {3, 5, 7, 1, 2, 4, 6} Output : {1, 2, 3, 4, 5, 6, 7}
Answer» Example: Input : arr = {3, 5, 7, 1, 2, 4, 6} Output : {1, 2, 3, 4, 5, 6, 7} Approach: Since we want the sorting algorithm to give the best time complexity in all three cases (that is, best, worst and average), we will implement merge sort to sort the given array of numbers. In merge sort, we divide an array into two HALVES recursively, sort each half and then merge them. Code: #include<bits/stdc++.h>using namespace STD;//function to merge the two sorted halves of the arrayvoid merge(int arr, int start, int mid, int end) { int temp[end - start + 1];// creating a temporary array to store the sorted array int i = start; int j = mid+1; int k = 0; while(i <= mid && j <= end) { if(arr[i] <= arr[j]) { temp[k] = arr[i]; i = i + 1; } else { temp[k] = arr[j]; j = j + 1; } k = k + 1; } //If the first half still has elements, we add them to the temporary array while(i <= mid) { temp[k ++] = arr[i ++]; } //If the second half still has elements, we add them to the temporary array while(j <= end) { temp[k ++] = arr[j ++]; } // We store the sorted order of elements in the original array for(i = start; i <= end; i ++) { arr[i] = temp[i - start] }}// function to sort an array of elementsvoid mergeSort(int arr, int start, int end) { if(start < end) { int mid = (start + end) / 2;// finding the mid INDEX mergeSort(arr, start, mid);// sorting the left side of the array mergeSort(arr, mid+1, end);// sorting the right side of the array merge(arr, start, mid, end);// merging the left and right halves of the array }}int main(){ int arr[] = {3, 5, 7, 1, 2, 4, 6}; int n = sizeof(arr)/ sizeof(arr[0]); mergeSort(arr, 0, n); cout << "The sorted array is : "; for(int i = 0; i < n; i ++) cout << arr[i]; cout << "\n"; return 0;} Output: The sorted array is : 1 2 3 4 5 6 7 Explanation: In the above code, the function merge() merges the two sorted halves of the array. The function mergeSort() recursively breaks the problem into subproblems, sorts each half and then merges the sorted halves by calling the merge() function.

Write a program to sort a given array of numbers. The sorting algorithm should give best performance in every case (best, worst and average). Example : Input : arr = {3, 5, 7, 1, 2, 4, 6} Output : {1, 2, 3, 4, 5, 6, 7}

Answer»

Example:
Input :
arr = {3, 5, 7, 1, 2, 4, 6}
Output :
{1, 2, 3, 4, 5, 6, 7}

Approach:

Since we want the sorting algorithm to give the best time complexity in all three cases (that is, best, worst and average), we will implement merge sort to sort the given array of numbers. In merge sort, we divide an array into two HALVES recursively, sort each half and then merge them.

Code:

#include<bits/stdc++.h>using namespace STD;//function to merge the two sorted halves of the arrayvoid merge(int *arr, int start, int mid, int end) { int temp[end - start + 1];// creating a temporary array to store the sorted array int i = start; int j = mid+1; int k = 0; while(i <= mid && j <= end) { if(arr[i] <= arr[j]) { temp[k] = arr[i]; i = i + 1; } else { temp[k] = arr[j]; j = j + 1; } k = k + 1; } //If the first half still has elements, we add them to the temporary array while(i <= mid) { temp[k ++] = arr[i ++]; } //If the second half still has elements, we add them to the temporary array while(j <= end) { temp[k ++] = arr[j ++]; } // We store the sorted order of elements in the original array for(i = start; i <= end; i ++) { arr[i] = temp[i - start] }}// function to sort an array of elementsvoid mergeSort(int *arr, int start, int end) { if(start < end) { int mid = (start + end) / 2;// finding the mid INDEX mergeSort(arr, start, mid);// sorting the left side of the array mergeSort(arr, mid+1, end);// sorting the right side of the array merge(arr, start, mid, end);// merging the left and right halves of the array }}int main(){ int arr[] = {3, 5, 7, 1, 2, 4, 6}; int n = sizeof(arr)/ sizeof(arr[0]); mergeSort(arr, 0, n); cout << "The sorted array is : "; for(int i = 0; i < n; i ++) cout << arr[i]; cout << "\n"; return 0;}

Output:

The sorted array is : 1 2 3 4 5 6 7

Explanation:

In the above code, the function merge() merges the two sorted halves of the array. The function mergeSort() recursively breaks the problem into subproblems, sorts each half and then merges the sorted halves by calling the merge() function.

Write a program to sort a given array of numbers. The sorting algorithm should give best performance in every case (best, worst and average). Example : Input : arr = {3, 5, 7, 1, 2, 4, 6} Output : {1, 2, 3, 4, 5, 6, 7}

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment