Question

In: Computer Science

Q1) Write a program to implement the quick sort algorithm in a one dimensional array? Q2)...

Q1) Write a program to implement the quick sort algorithm in a one dimensional array?

Q2) Write a program to implement the merge sort algorithm in a one dimensional array?

Solutions

Expert Solution

Hello I am adding code for both program in C

Please go through it

Quicksort.c

#include<stdio.h>
void quicksort(int number[25],int first,int last){
   int i, j, pivot, temp;

   if(first<last){
      pivot=first;
      i=first;
      j=last;

      while(i<j){
         while(number[i]<=number[pivot]&&i<last)
            i++;
         while(number[j]>number[pivot])
            j--;
         if(i<j){
            temp=number[i];
            number[i]=number[j];
            number[j]=temp;
         }
      }

      temp=number[pivot];
      number[pivot]=number[j];
      number[j]=temp;
      quicksort(number,first,j-1);
      quicksort(number,j+1,last);

   }
}

int main(){
   int i, count, number[25];

   printf("How many elements are u going to enter?: ");
   scanf("%d",&count);

   printf("Enter %d elements: ", count);
   for(i=0;i<count;i++)
      scanf("%d",&number[i]);

   quicksort(number,0,count-1);

   printf("Order of Sorted elements: ");
   for(i=0;i<count;i++)
      printf(" %d",number[i]);

   return 0;
}

Output

Mergesort.c


#include<stdio.h>
 
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
 
int main()
{
        int a[30],n,i;
        printf("Enter no of elements:");
        scanf("%d",&n);
        printf("Enter array elements:");
        
        for(i=0;i<n;i++)
                scanf("%d",&a[i]);
                
        mergesort(a,0,n-1);
        
        printf("\nSorted array is :");
        for(i=0;i<n;i++)
                printf("%d ",a[i]);
                
        return 0;
}
 
void mergesort(int a[],int i,int j)
{
        int mid;
                
        if(i<j)
        {
                mid=(i+j)/2;
                mergesort(a,i,mid);             //left recursion
                mergesort(a,mid+1,j);   //right recursion
                merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays
        }
}
 
void merge(int a[],int i1,int j1,int i2,int j2)
{
        int temp[50];   //array used for merging
        int i,j,k;
        i=i1;   //beginning of the first list
        j=i2;   //beginning of the second list
        k=0;
        
        while(i<=j1 && j<=j2)     //while elements in both lists
        {
                if(a[i]<a[j])
                        temp[k++]=a[i++];
                else
                        temp[k++]=a[j++];
        }
        
        while(i<=j1) //copy remaining elements of the first list
                temp[k++]=a[i++];
                
        while(j<=j2) //copy remaining elements of the second list
                temp[k++]=a[j++];
                
        //Transfer elements from temp[] back to a[]
        for(i=i1,j=0;i<=j2;i++,j++)
                a[i]=temp[j];
}

Output


Related Solutions

Write a MIPS program that uses an implementation of quick sort to sort an array of...
Write a MIPS program that uses an implementation of quick sort to sort an array of numbers (Translate the following code into (Mars Assembly language). Quicksort Implementation - C int partition(int arr [] , int left , int right) { int i=left, j=right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr [ i ] < pivot) i ++; while (arr [ j ] > pivot) j −−; if (i <= j)...
please write a C program that implements Quick Sort algorithm.
please write a C program that implements Quick Sort algorithm.
Write a program in Java to sort the given array using merge sort, quick sort, insertion...
Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.
Compute the first 4 pivots using quick sort algorithm on an array A=<10,15,17,18,6,120,30,250,95>. Write the content...
Compute the first 4 pivots using quick sort algorithm on an array A=<10,15,17,18,6,120,30,250,95>. Write the content of the array A after each pivot is chosen.
Sorting (quick) Sort the array using quick sort. Write the array content after each pass (i.e.,...
Sorting (quick) Sort the array using quick sort. Write the array content after each pass (i.e., from pass 1 to pass 7). Each pass is defined as the completion of one partition. We always pick the first array element as the pivot for each partition.
Write a MIPS program to implement the Bubble Sort algorithm, that sorts an input list of...
Write a MIPS program to implement the Bubble Sort algorithm, that sorts an input list of integers by repeatedly calling a “swap” subroutine. The original unsorted list of integers should be received from the keyboard input. Your program should first prompt the user “Please input an integer for the number of elements:”. After the user enters a number and return, your program outputs message “Now input each element and then a return:”. For example, if the user enters 8 as...
Write a class VectorInt to implement the concept of one dimensional array of integers with extendable...
Write a class VectorInt to implement the concept of one dimensional array of integers with extendable array size. Your class should support storing an integer at a specific index value, retrieving the integer at a specific index value, and automatically increasing storage for the saved values.
Program in Java Write an algorithm to transfer the elements from queue Q1 to queue Q2,...
Program in Java Write an algorithm to transfer the elements from queue Q1 to queue Q2, so that the contents in Q2 will be in reverse order as they are in Q1 (e.g. if your queue Q1 has elements A, B, and C from front to rear, your queue Q2 should have C, B, and A from front to rear). Your algorithm must explicitly use an additional stack to solve the problem. Write your algorithm in pseudo code first, and...
Use the median of 3 partitioning algorithm (given in the next page) to implement quick sort....
Use the median of 3 partitioning algorithm (given in the next page) to implement quick sort. This algorithm chooses the pivot element as the median of the 3 elements namely: A[p], A[r], and A[(p+r)/2].(Java language) Quicksort(A,p,r) 1 if p 2 N = r- p +1 3 m = Median3(A, p, p + N/2 , r) 4 exchange A[m] with A[r] 5 q = Partition (A,p,r) 6 Quicksort(A,p, q-1) 7 Quicksort(A,q+1,r)
(50’) Implement Quick-Sort algorithm in quickSort.cpp, where you are expected to implement three functions, swap(), partition()...
(50’) Implement Quick-Sort algorithm in quickSort.cpp, where you are expected to implement three functions, swap(), partition() and quickSort(). You are expected to call swap() within partition(), to call partition() within quickSort(), and you are not expected to declare/ implement other additional functions nor change the main() function. OPTIONAL: If you don’t need/ want to use swap() in your implementation, that is fine. Just delete/ comment it. quickSort.cpp #include <iostream> using namespace std;    // A helper function to facilitate swapping...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT