Question

CS 209 Data Structure

1. show how to apply a selection sort on 
{45, 11, 50, 59, 60, 2, 4, 7, 10}.

2. show how to apply a Insertion sort on 
{45, 11, 50, 59, 60, 2, 4, 7, 10}.

3. show how to apply a Bubble sort on 
{45, 11, 50, 59, 60, 2, 4, 7, 10}.

4. show how to apply a Merge sort on 
{45, 11, 50, 59, 60, 2, 4, 7, 10}.

5. show how to apply a Quick sort on 
{45, 11, 50, 59, 60, 2, 4, 7, 10}.

implement Selection, Insertion, Bubble sort
implement MergeSort and QuickSort

Answer 1

1)

Selection sort: Find the minimum in the array and place that element at the beginning.

0-{45,11,50,59,60,2,4,7,10} initial array

1-{2 ,45, 11, 50, 59, 60, 4, 7, 10 } 1st loop

2-{2, 4, 45, 11, 50, 59, 60, 7, 10} 2nd loop

......

1.

class selectionsort{
    void sort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n-1; i++) 
        { 
            int min_idx = i; 
            for (int j = i+1; j < n; j++) 
                if (arr[j] < arr[min_idx]) 
                    min_idx = j; 
  

            int temp = arr[min_idx]; 
            arr[min_idx] = arr[i]; 
            arr[i] = temp; 
        } 
    } 
}

2)

Insertion sort: The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

o - {45, 11, 50, 59, 60, 2, 4, 7, 10 }

1 - {11, 45, 50, 59, 60, 2, 4, 7, 10}

2 - {11 , 45 , 50, 59 , 60 , 2, 4, 7, 10}

3 - {11, 45, 50, 59, 60, 2, 4, 7, 10}

4 - {11, 45, 50, 59, 60, 2, 4, 7, 10}

5 - {2, 11, 45, 50, 59, 60, 4, 7, 10}

6 - {2, 4, 11, 45, 50, 59, 60, 7, 10}

...... goes so on

2.

void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++) { 
        key = arr[i]; 
        j = i - 1; 

        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 

3)

Bubble sort: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

o - {45, 11, 50, 59, 60, 2, 4, 7, 10 }

1 - {11, 45, 50, 59, 60, 2, 4, 7, 10}

2 - {11, 45, 50, 59, 60, 2, 4, 7, 10}

3 - {11, 45, 50, 59, 60, 2, 4, 7, 10}

4 - {11, 45, 50, 59, 60, 2, 4, 7, 10}

5 - {11, 45, 50, 59, 2, 60, 4, 7, 10}

6 - {11, 45, 50, 59, 2, 4, 60, 7, 10}

.....

This goes on till the end of the array and this whole process is repeated for another n times where n is the length of the array

3.

class BubbleSort 
{ 
    void bubbleSort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n-1; i++) 
            for (int j = 0; j < n-i-1; j++) 
                if (arr[j] > arr[j+1]) 
                { 
                    // swap arr[j+1] and arr[j] 
                    int temp = arr[j]; 
                    arr[j] = arr[j+1]; 
                    arr[j+1] = temp; 
                } 
    } 
}

Merge Sort: Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

4)
MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

4.

class MergeSort { 
    void merge(int arr[], int l, int m, int r) 
    { 
        int n1 = m - l + 1; 
        int n2 = r - m; 

        int L[] = new int[n1]; 
        int R[] = new int[n2]; 
  
        for (int i = 0; i < n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j = 0; j < n2; ++j) 
            R[j] = arr[m + 1 + j]; 

        int i = 0, j = 0; 

        int k = l; 
        while (i < n1 && j < n2) { 
            if (L[i] <= R[j]) { 
                arr[k] = L[i]; 
                i++; 
            } 
            else { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 

        while (i < n1) { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 

        while (j < n2) { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
    void sort(int arr[], int l, int r) 
    { 
        if (l < r) { 
            int m = (l + r) / 2; 

            sort(arr, l, m); 
            sort(arr, m + 1, r); 
  
            merge(arr, l, m, r); 
        } 
    } 
 
  

5)

Quick Sort:

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1. Always pick the first element as pivot.
2. Always pick the last element as the pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Pseudo code for partition:

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
 
    i = (low - 1)  // Index of smaller element

    for (j = low; j <= high- 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

5.

class QuickSort 
{ 
    int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];  
        int i = (low-1);
        for (int j=low; j<high; j++) 
        { 
            if (arr[j] < pivot) 
            { 
                i++; 
  
                // swap arr[i] and arr[j] 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 

        int temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 
  
        return i+1; 
    } 

    void sort(int arr[], int low, int high) 
    { 
        if (low < high) 
        { 
            int pi = partition(arr, low, high); 
  
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    }