Array - CSE205: Data Structures and Algorithms | B.Tech CSE Notes PDF | FineNotes4U

One 0

ARRAY

Array are defined as the collection of similar types of data item stored at contiguous memory location.


Types of Array:
  • One-dimensional Array:
  • Multi-dimensional Array: 2D Array (like table) and 3D Array (like cuboid)

1) Representation of Array:


int array[10] = {35, 33, 42, 10, 14, 19, 27, 44, 26, 31}

2) Traversal Operation in an Array:


CODE:

#include <iostream>
using namespace std;

int main(){
    int a[5] = {2,3,5,7,11};
    for(int i=0; i<5; i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

OUTPUT: 

2 3 5 7 11

3) Insertion at the Beginning of Array: 


CODE:

#include <iostream>
using namespace std;

int main(){
    int array[10] = {1,2,3,4,5};
    int newElement = 9;
    int size = 5;
    //Shift elements to the right
    for(int i=size; i>0; i--){
        array[i] = array[i-1];
    }
    
    //Insert new value
    array[0] = newElement;
    
    //Increase the size of the array
    size++;
    
    //Display the updated array
    for(int i=0; i<size ; i++){
        cout<<array[i]<<" ";
    }
    return 0;
}

OUTPUT:

9 1 2 3 4 5

4) Insertion at the End of Array:


CODE:

#include <iostream>
using namespace std;

int main(){
    int array[10] = {1,2,3,4,5};
    int newElement = 9;
    int size = 5;
    
    //Insert new value
    array[size] = newElement;

    //Increase the size of the array
    size++;
    
    //Display the updated array
    for(int i=0; i<size; i++){
        cout<<array[i]<< " ";
    }
    return 0;
}

OUTPUT:

1 2 3 4 5 9

5) Insertion at the Specified Position:


CODE:

#include <iostream>
using namespace std;

int main(){
    int array[10] = {1,2,3,4,5};
    int newElement = 9;
    int insertPosition = 2;
    int size = 5;

    //Shift elements to the right for position
    for(int i=size; i>insertPosition; i--){
        array[i] = array[i-1];
    }

    //Insert the new element
    array[insertPosition] = newElement;

    //Increase the size of the array
    size++;
    
    //Print the updated array
    for(int i=0; i<size; i++){
        cout<<array[i]<<" ";
    }
    return 0;
}

OUTPUT:

1 2 9 3 4 5

6) Deletion at the Beginning of Array:


CODE:

#include <iostream>
using namespace std;

int main(){
    int array[10] = {1,2,3,4,5};
    int size = 5;

    //Shift all element to left
    for(int i=0; i<size-1; i++){
        array[i] = array[i+1];
    }

    //Decrease the size of array
    size--;

    //Print the updated array
    for(int i=0; i<size; i++){
        cout<<array[i]<<" ";
    }
    return 0;
}

OUTPUT:

2 3 4 5

7) Deletion at the End of Array:


CODE:

#include <iostream>
using namespace std;

int main(){
    int array[10]={1,2,3,4,5};
    int size=5;

    //Decrease the size by 1 (logically ignoring the last element)
    size--;

    //Print the updated array
    for(int i=0; i<size; i++){
        cout<<array[i]<<" ";
    }
    return 0;
}

OUTPUT:

1 2 3 4

8) Deletion at the Specified Position


CODE:

#include <iostream>
using namespace std;

int main(){
    int array[10] = {1,2,3,4,5};
    int size = 5;
    int deletePosition = 2;

    //Shift elements to the left for position
    for(int i=deletePosition; i<size-1; i++){
        array[i] = array[i+1];
    }
    
    //Decrease the size by 1 (logically ignoring the last element)
    size--;

    //Print the updated array
    for(int i=0; i<size; i++){
        cout<<array[i]<<" ";
    }
    return 0;
}

OUTPUT:

1 2 4 5

9) Merge Operation in an Array:


CODE:

#include <iostream>
using namespace std;

int main(){
    int array1[] = {9,8,4,1,5};
    int array2[] = {2,0,3,6};

    int size1 = sizeof(array1) / sizeof(array1[0]);
    int size2 = sizeof(array2) / sizeof(array2[0]);

    int mergedArray[size1 + size2];

    for(int i=0; i<size1; i++){
        mergedArray[i] = array1[i];
    }
    for(int i=0; i<size2; i++){
        mergedArray[size1+i] = array2[i];
    }

    //Print the merged array
    for(int i=0; i<size1+size2; i++){
        cout<<mergedArray[i]<<" ";
    }
}

OUTPUT:

9 8 4 1 5 2 0 3 6

10) Array : Linear Searching


CODE:

#include <iostream>
using namespace std;

void linear_search(int array[], int size, int target) {
    for(int i = 0; i < size; i++) {
        if(array[i] == target) {
            cout << "Found target " << target << " at index: " << i << endl;
            return;
        }
    }
    cout << "Target not found in the array." << endl;
}

int main() {
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int target = 5;
    int size = sizeof(array) / sizeof(array[0]);
    linear_search(array, size, target);
    return 0;
}

OUTPUT:

Found target 5 at index: 4

11) Array: Binary Search


CODE:

#include <iostream>
using namespace std;

int binary_search(int array[], int size, int target) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target) {
            return mid;
        }
        else if (array[mid] > target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return -1;
}

int main() {
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int target = 5;
    int size = sizeof(array) / sizeof(array[0]);
    int result = binary_search(array, size, target);
    if (result != -1) {
        cout << "Found target " << target << " at index: " << result << endl;
    } else {
        cout << "Target not found in the array." << endl;
    }
    return 0;
}

OUTPUT:

Found target 5 at index: 4

12) Array: Bubble Sort


CODE:

#include <iostream>
using namespace std;

void bubble_sort(int array[], int size) {
    for (int i = 0; i < size-1; i++) {
        for (int j = 0; j < size - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

int main() {
    int array[] = {1, 5, 2, 1, 9, 0, 6};
    int size = sizeof(array) / sizeof(array[0]);
    bubble_sort(array, size);
    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    return 0;
}

OUTPUT:

0 1 1 2 5 6 9 

13) Array: Insertion Sort


CODE:

#include <iostream>
using namespace std;

void insertion_sort(int array[], int size) {
    for (int i = 1; i < size; i++) {
        int key = array[i]; // Pick the element to insert
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

int main() {
    int array[] = {1, 5, 2, 1, 9, 0, 6};
    int size = sizeof(array) / sizeof(array[0]);
    insertion_sort(array, size);
    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    return 0;
}

OUTPUT:

0 1 1 2 5 6 9 

14) Array: Selection Sort


CODE:

#include <iostream>
using namespace std;

void selection_sort(int array[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < size; j++) {
            if (array[j] < array[min_index]) {
                min_index = j;
            }
        }
        swap(array[i], array[min_index]);
    }
}

int main() {
    int array[] = {1, 5, 2, 1, 9, 0, 6};
    int size = sizeof(array) / sizeof(array[0]);
    selection_sort(array, size);
    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    return 0;
}

OUTPUT:

0 1 1 2 5 6 9 

15) Time & Space Complexity:


  1. Traversal: Visiting each element one by one.

    • Time Complexity: O(n)

  2. Insertion: Adding a new element.

    • At the end: O(1)

    • At a specific position: O(n)

  3. Deletion: Removing an element.

    • From the end: O(1)

    • From a specific position: O(n)

  4. Merging: Combining two arrays into one.

    • Time Complexity: O(n)

  5. Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order.

    • Time Complexity: O(n^2)

  6. Insertion Sort: Builds the sorted array one item at a time by comparing and inserting.

    • Time Complexity: O(n^2)

  7. Selection Sort: Repeatedly selects the smallest element and swaps it with the first unsorted element.

    • Time Complexity: O(n^2)

  8. Linear Search: Checks elements one by one.

    • Time Complexity: O(n)

  9. Binary Search: Only works on sorted arrays, Repeatedly divides the array into halves

    • Time Complexity: O(log n)


🚨Thanks for visiting finenotes4u✨

Welcome to a hub for 😇Nerds and knowledge seekers! Here, you'll find everything you need to stay updated on education, notes, books, and daily trends.

💗 Bookmark our site to stay connected and never miss an update!

💌 Have suggestions or need more content? Drop a comment below, and let us know what topics you'd like to see next! Your support means the world to us. 😍

Tags

Post a Comment

Post a Comment

Previous Post Next Post