Question

C++ Programing

Consider the following sorting techniques:

• Bubble Sort

• Insertion Sort

• Selection Sort

• Merge Sort

• Quick Sort

Select any two of the above sorting techniques:

1. Write an algorithm (pseudocode) for the two selected sorting techniques

2. Write two separate C++ programs using user defined functions for each of the selected sorting techniques.

Answer 1

Ques 1.

-------------------Quick Sort Algorithm -------------------

Inside the quickSort(arr, left, right) function:

arr is the array to be sorted.

left is the left bound of arr.

right is the right bound of arr.

1. Check if left is less than right. If yes go to step 2, else exit the function.
2. Create a partition using method partition().
3. Call the quickSort() function recursively in the left subarray from index left to partition - 1.
4. Call the quickSort() function recursively in the right subarray from index partition + 1 to right.

Inside the partition arr, left, right) function:

arr is the array to be sorted.

left is the left bound of arr.

right is the right bound of arr.

1. Set pivot to the last element.
2. Set i = left - 1.
3. Loop from j <- left to right - 1

• If arr[ j ] <= pivot, increment i and swap arr[ i ] and arr[ j ]

4. Loop ends
5. swap arr[ i + 1 ] and arr[ right ]
6. return ( i + 1 )

-----------------------Insertion Sort Algorithm---------------------------

function insertionSort(arr , n)

BEGIN

    // if there is only 1 element in array

    if n <= 1

         return

    // recursively sort the first (n - 1) elements

    insertionSort(arr , n - 1);

    x = n - 1

    temp = arr[n]

    while x >= 0 and arr[x] > temp

    BEGIN

         arr[x + 1] = arr[x]

         j = j - 1

    END

    arr[j + 1] = temp

END

Ques 2.

-----------------Quick Sort----------------

#include<iostream>

#include<fstream>

#include<cstdlib>

using namespace std;

void quicksort(int *,int,int);

int partition(int *,int,int);

int main()

{

    int arr[] = { 8, 7, 6, 5, 4, 3, 2, 1 };

    int n = 8;

    int i;

       

    cout<<"Unsorted Array : ";

    for( i = 0 ; i < n ; i++ )

        cout<<arr[i]<<" ";

       

    quicksort(arr, 0, n - 1);

    cout<<"\nSorted Array : ";

   

    for( i = 0 ; i < n ; i++ )

        cout<<arr[i]<<" ";

       

    return 0;

}

// function to sort using quick sort

void quicksort(int *arr,int p,int r)

{

    int q;

   

    if(p<r)

    {

        // create a partition

        q = partition(arr,p,r);

       

        // sort the left subarray

        quicksort(arr,p,q-1);

        

        // sort the right subarray

        quicksort(arr,q+1,r);

    }

}

int partition(int *arr,int p,int r)

{  

    // set pivot

    int pivot = arr[r];

   

    // set the lindex of lower element

    int j, i = p - 1;

    for (j = p; j <= r - 1; j++ )

    {

        if (arr[j] <= pivot)

        {

            // increment smaller element index

            i++;

           

            // swap the contents of i and j position

            int temp=arr[i];

            arr[i]=arr[j];

            arr[j]=temp;

        }

    }

   

    int temp = arr[i + 1];

    arr[i+1] = arr[r];

    arr[r] = temp;

   

    return i + 1;

}

Sample Output

Unsorted Array87 6543 2 1 Sorted Array 1 2 3 4567 8

--------------------Insertion Sort---------------------

#include<iostream>

#include<fstream>

#include<cstdlib>

using namespace std;

void insertion_sort(int a[], int n);

int main()

{

    int arr[] = { 8, 7, 6, 5, 4, 3, 2, 1 };

    int n = 8;

    int i;

       

    cout<<"Unsorted Array : ";

    for( i = 0 ; i < n ; i++ )

        cout<<arr[i]<<" ";

       

    insertion_sort(arr, n);

    cout<<"\nSorted Array : ";

   

    for( i = 0 ; i < n ; i++ )

        cout<<arr[i]<<" ";

       

    return 0;

}

void insertion_sort(int a[], int n)

{

    int i, j, temp;

       

    for (i = 1; i < n; i++)

    {

        // store the current element in temp

        temp = a[i];

       

        // set j to i - 1

        j = i - 1;

        // all elements greater than temp are

        // shifted 1 position right

        while (j >= 0 && a[j] > temp)

        {

            // shifted 1 position right

            a[j+1] = a[j];

            j--;

        }

       

        a[j + 1] = temp;

    }

}

Sample Output

Unsorted Array87 6543 2 1 Sorted Array 1 2 3 4567 8
​​​​​​​