Scribd Logo
Upload

Welcome to Scribd!

  • 89 views

    Experiment 1: Aim: Theory

    Uploaded by

    Sachin More
    Riddhi More conducted an experiment on insertion sort. The aim was to implement and analyze insertion sort. Insertion sort works by taking unsorted elements and inserting them into the sorted position in each iteration. The algorithm marks the first element as sorted, then iterates through the unsorted elements, finds the correct place to insert by comparing to sorted elements, and inserts. The program implements insertion sort on an integer array. The analysis found worst case time complexity of O(n^2) when array is reverse sorted, best case of O(n) when already sorted, and average case of O(n^2). Space complexity is O(1).

    Copyright:

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

    Experiment 1: Aim: Theory

    Uploaded by

    Sachin More
    89 views5 pages
    Riddhi More conducted an experiment on insertion sort. The aim was to implement and analyze insertion sort. Insertion sort works by taking unsorted elements and inserting them into the sorted position in each iteration. The algorithm marks the first element as sorted, then iterates through the unsorted elements, finds the correct place to insert by comparing to sorted elements, and inserts. The program implements insertion sort on an integer array. The analysis found worst case time complexity of O(n^2) when array is reverse sorted, best case of O(n) when already sorted, and average case of O(n^2). Space complexity is O(1).

    Original Title

    AOA practical

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Riddhi More conducted an experiment on insertion sort. The aim was to implement and analyze insertion sort. Insertion sort works by taking unsorted elements and inserting them into the sorted position in each iteration. The algorithm marks the first element as sorted, then iterates through the unsorted elements, finds the correct place to insert by comparing to sorted elements, and inserts. The program implements insertion sort on an integer array. The analysis found worst case time complexity of O(n^2) when array is reverse sorted, best case of O(n) when already sorted, and average case of O(n^2). Space complexity is O(1).

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    89 views5 pages

    Experiment 1: Aim: Theory

    Uploaded by

    Sachin More
    Riddhi More conducted an experiment on insertion sort. The aim was to implement and analyze insertion sort. Insertion sort works by taking unsorted elements and inserting them into the sorted position in each iteration. The algorithm marks the first element as sorted, then iterates through the unsorted elements, finds the correct place to insert by comparing to sorted elements, and inserts. The program implements insertion sort on an integer array. The analysis found worst case time complexity of O(n^2) when array is reverse sorted, best case of O(n) when already sorted, and average case of O(n^2). Space complexity is O(1).

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 5

    Riddhi More

    Roll number 33

    Experiment 1

    Aim: Implementation and Analysis of Insertion Sort.


    Theory:
    Insertion sort works similarly as we sort cards in our hand in a card game.

    We assume that the first card is already sorted then, we select an unsorted card. If the
    unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left.
    In the same way, other unsorted cards are taken and put at their right place.

    A similar approach is used by insertion sort.

    Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in
    each iteration.

    Suppose we need to sort the following array.

    1. The first element in the array is assumed to be sorted. Take the second element and
    store it separately in key.

    Compare key with the first element. If the first element is greater than key,
    then key is

    placed in front of the first element. If the first element is greater than key, then key
    is placed in front of the first element

    1|Page
    Riddhi More
    Roll number 33

    2. Now, the first two elements are sorted.

    Take the third element and compare it with the elements on the left of it. Placed it
    just behind the element smaller than it. If there is no element smaller than it, then
    place it at the beginning of the array.

    3. Similarly, place every unsorted element at its correct position.

    Algorithm:

    insertionSort(array)
    mark first element as sorted
    for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
    if current element j > X
    move sorted element to the right by 1
    break loop and insert X here
    end insertionSort

    2|Page
    Riddhi More
    Roll number 33

    Program:
    #include <iostream>
    using namespace std;

    // Function to print an array


    void printArray(int array[], int size) {
    for (int i = 0; i < size; i++) {
    cout << array[i] << " ";
    }
    cout << endl;
    }

    void insertionSort(int array[], int size) {


    for (int step = 1; step < size; step++) {
    int key = array[step];
    int j = step - 1;

    // Compare key with each element on the left of it until an element smalle
    r than
    // it is found.
    // For descending order, change key<array[j] to key>array[j].
    while (key < array[j] && j >= 0) {
    array[j + 1] = array[j];
    --j;
    }
    array[j + 1] = key;
    }
    }

    3|Page
    Riddhi More
    Roll number 33

    Output:
    When the array is already sorted

    When the array is not sorted

    When the array is partially sorted

    4|Page
    Riddhi More
    Roll number 33

    Analysis:
    Time Complexities

    Worst Case Complexity: O(n2)


    Suppose, an array is in ascending order, and you want to sort it in descending order. In this
    case, worst case complexity occurs.

    Each element has to be compared with each of the other elements so, for every nth
    element, (n-1) number of comparisons are made.

    Thus, the total number of comparisons = n*(n-1) ~ n2

    Best Case Complexity: O(n)


    When the array is already sorted, the outer loop runs for n number of times whereas the
    inner loop does not run at all. So, there are only n number of comparisons. Thus, complexity
    is linear.

    Average Case Complexity: O(n2)


    It occurs when the elements of an array are in jumbled order (neither ascending nor
    descending).
    Space Complexity

    Space complexity is O(1) because an extra variable key is used.

    5|Page

    You might also like