Data Structures: Array Algorithms - Search, Insert, Delete, and Bubble Sort

Search Algorithm 3: Binary Search

• Definition: A sorted array $DATA$ with $N$ elements and a specific $ITEM$ of information are given. This algorithm finds the location $LOC$ of $ITEM$ in $DATA$ or sets $LOC = -1$.

Algorithm Steps

• 1. [Initialize]: Set $BEG := 0$, $END := N - 1$ and $LOC := 0$.

• 2. Repeat Steps 3 to 4: While $BEG \le END$ and $LOC = 0$.

• 3. Set MID: $MID := \lfloor (BEG + END) / 2 \rfloor$.

• 4. If ITEM = DATA[MID]:

  • Then: Set $LOC := MID$.

  • Else if $ITEM < DATA[MID]$:

    • Then: Set $END := MID - 1$.

  • Else:

    • Set $BEG := MID + 1$.

• 5. [Successful?]:

  • If $LOC = -1$:

    • Write: "ITEM is not in the array DATA."

  • Else:

    • Write: "LOC is the location of ITEM."

• 6. Exit.

C++ Implementation

int main() {
    int DATA[10] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int N = 10;
    int ITEM = 23;
    int BEG = 0;
    int END = N - 1;
    int MID;
    int LOC = -1;

    while (BEG <= END && LOC == -1) {
        MID = (BEG + END) / 2;
        if (ITEM == DATA[MID]) 
            LOC = MID;
        else if (ITEM < DATA[MID]) 
            END = MID - 1;
        else 
            BEG = MID + 1;
    }

    if (LOC == -1) 
        cout << "ITEM is not in the array DATA\n";
    else 
        cout << LOC << " is the location of ITEM\n";

    return 0;
}

Execution Trace for Binary Search

• Objective: Search for ITEM = 23 in array DATA = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}.

• Initial Values:

  • $N = 10$

  • $ITEM = 23$

  • $LOC = -1$

  • $BEG = 0$

  • $END = 9$

• Iteration 1:

  • $MID = (0 + 9) / 2 = 4$

  • $DATA[4] = 16$

  • Comparison: $23 > 16$, so $BEG = 4 + 1 = 5$.

• Iteration 2:

  • $MID = (5 + 9) / 2 = 7$

  • $DATA[7] = 56$

  • Comparison: $23 < 56$, so $END = 7 - 1 = 6$.

• Iteration 3:

  • $MID = (5 + 6) / 2 = 5$

  • $DATA[5] = 23$

  • Comparison: $23 = 23$, so $LOC = 5$.

• Result: Exit loop. Display: "5 is the location of ITEM".

Algorithm 4: Insertion into an Array at a Given Location

• Definition: An array $DATA$ with $N$ elements and a specific $ITEM$ and location $LOC$ are given. This algorithm inserts $ITEM$ into $DATA$ at position $LOC$.

Algorithm Steps

• 1. [Initialize]: If $LOC < 0$ or $LOC > N$, then:

  • Write: "Invalid Location."

  • Exit.

• 2. Set K: $K := N - 1$.

• 3. Repeat while K ≥ LOC:

  • Set $DATA[K + 1] := DATA[K]$.

  • Set $K := K - 1$.

• 4. Set DATA[LOC]: $DATA[LOC] := ITEM$.

• 5. Set N: $N := N + 1$.

• 6. Write: Updated array $DATA$.

• 7. Exit.

C++ Implementation

#include <iostream.h>
int main() {
    int DATA[20] = {10, 20, 30, 40, 50};
    int N = 5;
    int ITEM = 25;
    int LOC = 2;
    int K;

    if (LOC < 0 || LOC > N) {
        cout << "Invalid Location\n";
        return 0;
    }

    for (K = N - 1; K >= LOC; K--) {
        DATA[K + 1] = DATA[K];
    }

    DATA[LOC] = ITEM;
    N = N + 1;

    cout << "Updated Array:\n";
    for (K = 0; K < N; K++)
        cout << DATA[K] << '\n';

    return 0;
}

Execution Trace for Insertion

• Target: Insert ITEM = 25 at LOC = 2.

• Initial Array: DATA = {10, 20, 30, 40, 50}, $N = 5$.

• Shifting Steps:

  • $K = 4$: $DATA[5] = DATA[4]$ (Array becomes {10, 20, 30, 40, 50, 50})

  • $K = 3$: $DATA[4] = DATA[3]$ (Array becomes {10, 20, 30, 40, 40, 50})

  • $K = 2$: $DATA[3] = DATA[2]$ (Array becomes {10, 20, 30, 30, 40, 50})

• Loop Ends: $K$ is now less than $LOC$.

• Insertion: $DATA[2] = 25$ (Array becomes {10, 20, 25, 30, 40, 50}).

• Update Count: $N = 6$.

Algorithm 5: Deletion from an Array at a Given Location

• Definition: An array $DATA$ with $N$ elements and a specific location $LOC$ are given. This algorithm deletes the element at position $LOC$.

Algorithm Steps

• 1. [Initialize]: If $LOC < 0$ or $LOC > N - 1$, then:

  • Write: "Invalid Location."

  • Exit.

• 2. Set ITEM: $ITEM := DATA[LOC]$.

• 3. Set K: $K := LOC$.

• 4. Repeat while K < N - 1:

  • Set $DATA[K] := DATA[K + 1]$.

  • Set $K := K + 1$.

• 5. Set N: $N := N - 1$.

• 6. Write: Updated array $DATA$.

• 7. Exit.

C++ Implementation

int main() {
    int DATA[20] = {10, 20, 30, 40, 50};
    int N = 5;
    int LOC = 2;
    int K;

    if (LOC < 0 || LOC > N - 1) {
        cout << "Invalid Location\n";
        return 0;
    }

    for (K = LOC; K < N - 1; K++) {
        DATA[K] = DATA[K + 1];
    }

    N = N - 1;

    cout << "Updated Array:\n";
    for (K = 0; K < N; K++)
        cout << DATA[K] << "\n";

    return 0;
}

Execution Trace for Deletion

• Target: Delete element at LOC = 2.

• Initial Array: DATA = {10, 20, 30, 40, 50}, $N = 5$.

• Shifting Steps:

  • $K = 2$: $DATA[2] = DATA[3]$ (Value 40 moves to index 2; Array: {10, 20, 40, 40, 50})

  • $K = 3$: $DATA[3] = DATA[4]$ (Value 50 moves to index 3; Array: {10, 20, 40, 50, 50})

• Loop Ends: $K$ reached $N - 1$.

• Update Count: $N = 4$.

• Final Result: Array is effectively {10, 20, 40, 50}.

Algorithm 8: Bubble Sort

• Definition: An array $DATA$ with $N$ elements is given. This algorithm sorts $DATA$ in ascending order using the Bubble Sort method.

Algorithm Steps

• 1. [Initialize]: Set $PASS := 0$.

• 2. Repeat Steps 3 to 5: While $PASS \le N - 1$.

• 3. Set K: $K := 0$.

• 4. Repeat while K ≤ N - PASS - 2:

  • If $DATA[K] > DATA[K + 1]$, then:

    • Interchange $DATA[K]$ and $DATA[K + 1]$.

  • Set $K := K + 1$.

• 5. Set PASS: $PASS := PASS + 1$.

• 6. Write: Sorted array $DATA$.

• 7. Exit.

C++ Implementation

#include <iostream.h>
int main() {
    int DATA[10] = {64, 25, 12, 22, 11};
    int N = 5;
    int PASS, K, TEMP;

    for (PASS = 0; PASS < N - 1; PASS++) {
        for (K = 0; K < N - PASS - 1; K++) {
            if (DATA[K] > DATA[K + 1]) {
                TEMP = DATA[K];
                DATA[K] = DATA[K + 1];
                DATA[K + 1] = TEMP;
            }
        }
    }

    cout << "Sorted Array:\n";
    for (K = 0; K < N; K++)
        cout << DATA[K] << "\n";

    return 0;
}

Execution Trace for Bubble Sort

• Initial Data: {64, 25, 12, 22, 11}, $N = 5$.

• Pass 0:

  • Compare 64, 25: Swap → {25, 64, 12, 22, 11}

  • Compare 64, 12: Swap → {25, 12, 64, 22, 11}

  • Compare 64, 22: Swap → {25, 12, 22, 64, 11}

  • Compare 64, 11: Swap → {25, 12, 22, 11, 64}

  • Result of Pass 0: Largest element (64) moved to the end.

• Pass 1:

  • Compare 25, 12: Swap → {12, 25, 22, 11, 64}

  • Compare 25, 22: Swap → {12, 22, 25, 11, 64}

  • Compare 25, 11: Swap → {12, 22, 11, 25, 64}

  • Result of Pass 1: 25 sits in the correct sorted sub-array.

• Pass 2:

  • Compare 12, 22: No swap.

  • Compare 22, 11: Swap → {12, 11, 22, 25, 64}

• Pass 3:

  • Compare 12, 11: Swap → {11, 12, 22, 25, 64}

• Final Result: The array is fully sorted in ascending order: {11, 12, 22, 25, 64}.