Scribd Logo
Upload

Welcome to Scribd!

  • 410 views

    Experiment: 1 Insertion Sort Algorithm: Theory

    Uploaded by

    iG么RayG
    The document describes two sorting algorithms: 1. Insertion sort works by splitting an array into sorted and unsorted parts, selecting elements from the unsorted part and inserting them into the correct position in the sorted part. It has a time complexity of O(n2) and is useful for small data sets or nearly sorted data. 2. Quicksort works by selecting a pivot element and partitioning the array into subarrays based on element values relative to the pivot, and recursively sorting the subarrays. It has average time complexity of O(nlogn).

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Experiment: 1 Insertion Sort Algorithm: Theory

    Uploaded by

    iG么RayG
    410 views6 pages
    The document describes two sorting algorithms: 1. Insertion sort works by splitting an array into sorted and unsorted parts, selecting elements from the unsorted part and inserting them into the correct position in the sorted part. It has a time complexity of O(n2) and is useful for small data sets or nearly sorted data. 2. Quicksort works by selecting a pivot element and partitioning the array into subarrays based on element values relative to the pivot, and recursively sorting the subarrays. It has average time complexity of O(nlogn).

    Original Title

    EXPERIMENT1_2

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes two sorting algorithms: 1. Insertion sort works by splitting an array into sorted and unsorted parts, selecting elements from the unsorted part and inserting them into the correct position in the sorted part. It has a time complexity of O(n2) and is useful for small data sets or nearly sorted data. 2. Quicksort works by selecting a pivot element and partitioning the array into subarrays based on element values relative to the pivot, and recursively sorting the subarrays. It has average time complexity of O(nlogn).

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    410 views6 pages

    Experiment: 1 Insertion Sort Algorithm: Theory

    Uploaded by

    iG么RayG
    The document describes two sorting algorithms: 1. Insertion sort works by splitting an array into sorted and unsorted parts, selecting elements from the unsorted part and inserting them into the correct position in the sorted part. It has a time complexity of O(n2) and is useful for small data sets or nearly sorted data. 2. Quicksort works by selecting a pivot element and partitioning the array into subarrays based on element values relative to the pivot, and recursively sorting the subarrays. It has average time complexity of O(nlogn).

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 6

    EXPERIMENT: 1

    INSERTION SORT ALGORITHM


     
    THEORY:
    Insertion sort is a simple sorting algorithm that works similar to the way you sort
    playing cards in your hands. 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.
    Algorithm 
    To sort an array of size n in ascending order: 
    1: Iterate from arr[1] to arr[n] over the array. 
    2: Compare the current element (key) to its predecessor. 
    3: If the key element is smaller than its predecessor, compare it to the elements before.
    Move the greater elements one position up to make space for the swapped element.
    Example: 
     
    Another Example: 
    12, 11, 13, 5, 6
    Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
    i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12 
    11, 12, 13, 5, 6
    i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13 
    11, 12, 13, 5, 6
    i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one
    position ahead of their current position. 
    5, 11, 12, 13, 6
    i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one
    position ahead of their current position. 
    5, 6, 11, 12, 13 
     
     
     
    Output: 
     
    5 6 11 12 13

    PSEUDOCODE:

    /* Function to sort an array using insertion sort*/


    void insertionSort(int arr[], int n)
    {
        int i, key, j;
        for (i = 1; i < n; i++)
        {
            key = arr[i];
            j = i - 1;
     
            /* Move elements of arr[0..i-1], that are
            greater than key, to one position ahead
            of their current position */
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
    arr[j + 1] = key;
        }
    }
    Time Complexity: O(n2) 
    Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in
    reverse order. And it takes minimum time (Order of n) when elements are already
    sorted.
    Algorithmic Paradigm: Incremental Approach

    Uses: Insertion sort is used when number of elements is small. It can also be useful
    when input array is almost sorted, only few elements are misplaced in complete big
    array.
    EXPERIMENT: 2

    QUICK SORT ALGORITHM

    Pseudocode:

    int partition1(int *a,int start,int end)

    int pivot=a[start],p1=start+1,i,temp;

    for(i=start+1;i<=end;i++)
    {

    if(a[i]<pivot)
    {
    if(i!=p1)
    {
    temp=a[p1];
    a[p1]=a[i];
    a[i]=temp;
    } p1++;
    }
    }

    a[start]=a[p1-1];
    a[p1-1]=pivot;

    return p1-1;
    }

    void quicksort(int *a,int start,int end)


    {
    int p1;
    if(start<end)
    {
    p1=partition(a,start,end);
    quicksort(a,start,p1-1);
    quicksort(a,p1+1,end);
    }
    }

    class QuickSortPart1{
    public int partition(int[] a, int left, int right) {
    int pivot = a[left];
    while(left<=right) {
    while(a[left] < pivot)
    left++;
    while(a[right] > pivot)
    right--;
    if(left<=right) {
    int tmp = a[left];
    a[left] = a[right];
    a[right] = tmp;
    left++;
    right--;
    }
    }
    return left;
    }
    public void recursiveQuickSort(int[] a, int i, int j) {
    int idx = partition(a, i, j);
    if(i < idx-1) {
    recursiveQuickSort(a, i, idx-1);
    }
    if(j > idx) {
    recursiveQuickSort(a, idx, j);
    }
    }

    void printarray(int arr[]){


    int len = arr.length;
    for(int i=0; i<len; i++)
    System.out.print(arr[i]+" ");
    }
    public static void main(String[] args) {
    int arr[] = new int[]{5,8,1,3,7,9,2};
    System.out.print(arr[i]+" ");
    System.out.println("\n");
    QuickSortPart1 ob = new QuickSortPart1();
    ob.recursiveQuickSort(arr, 0, arr.length-1);
    ob.printarray(arr);
    }
    }

    You might also like