Sorting and Searching

Sorting and searching are fundamental operations in computer science and are important concepts in OODSA.

Sorting

Sorting is the process of arranging elements in a particular order. In OODSA, various sorting algorithms are used to arrange data efficiently. One commonly used sorting algorithm is Bubble Sort.

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Here's an example of implementing Bubble Sort in C++:

1void bubbleSort(std::vector<int>& list) {
2    int n = list.size();
3
4    for (int i = 0; i < n-1; i++) {
5        for (int j = 0; j < n-i-1; j++) {
6            if (list[j] > list[j+1]) {
7                std::swap(list[j], list[j+1]);
8            }
9        }
10    }
11}

Searching

Searching is the process of finding a particular element in a collection of data. In OODSA, various searching algorithms are used to efficiently find elements. One commonly used searching algorithm is Binary Search.

Binary Search is an efficient searching algorithm that works on sorted lists. It repeatedly divides the search space in half, eliminating the half where the target element cannot be present. Here's an example of implementing Binary Search in C++:

1int binarySearch(const std::vector<int>& list, int target) {
2    int left = 0;
3    int right = list.size() - 1;
4
5    while (left <= right) {
6        int mid = left + (right - left) / 2;
7
8        if (list[mid] == target) {
9            return mid;
10        }
11
12        if (list[mid] < target) {
13            left = mid + 1;
14        } else {
15            right = mid - 1;
16        }
17    }
18
19    return -1;
20}

By understanding sorting and searching algorithms, you will be equipped with powerful tools to efficiently organize and retrieve data in the context of object-oriented design and analysis.

Stay tuned for the next lesson on graph algorithms!

xxxxxxxxxx

}

#include <iostream>

#include <vector>

​

void printList(const std::vector<int>& list) {

    for (int number : list) {

        std::cout << number << " ";

    }

    std::cout << std::endl;

}

​

void bubbleSort(std::vector<int>& list) {

    int n = list.size();

​

    for (int i = 0; i < n-1; i++) {

        for (int j = 0; j < n-i-1; j++) {

            if (list[j] > list[j+1]) {

                std::swap(list[j], list[j+1]);

            }

        }

    }

}

​

int binarySearch(const std::vector<int>& list, int target) {

    int left = 0;

    int right = list.size() - 1;

​

    while (left <= right) {

        int mid = left + (right - left) / 2;

​