Gihyun Kim

Types: Insertion Sort, Selection sort, and Bubble Sort

What Are They?
Sorting algorithms are algorithms used to put the elements in a data set (arrays, ArrayLists, vectors, etc.) in order. For example, if an array is in this format:

1

5

3

7

4

2

6

sorting algorithms can sort this array to look like this:

1

2

3

4

5

6

7

Here is a code in C that does Selection Sort

#include <iostream>
#include <string.h>
using namespace std;
void swap(int *a, int *b) {
    int temp = 0;
    temp = *a;
    *a = *b;
    *b = temp;
}
int main() {
    int N, i, j, min, minIdx, temp;
    int arr[101] = {};
    cout << "Enter the size of the data set: ";
    cin >> N;
    cout << "Enter the values of the data set: ";
    for (i = 0; i < N; i++) {
        cin >> arr[i];
    }
    for(i = 0; i < N-1; i++) {
        min = 100000000;
        minIdx = 0;
        temp = 0;
        for (j = i; j < N; j++) {
            if (arr[j] < min) {
                min = arr[j];
                minIdx = j;
            }
        }
        swap(&arr[minIdx], &arr[i]);
    }
    cout << "Sorted: ";
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0;
}

This is a code in C that does Insertion Sort

#include <iostream>
#include <string.h>
using namespace std;
int N;
void swap(int *a, int *b) {
    int temp = 0;
    temp = *a;
    *a = *b;
    *b = temp;
}
int main() {
    int arr[101], i, j;
    cout << "Enter size of data set: ";
    cin >> N;
    cout << "Enter values in data set: ";
    for (i = 0; i < N; i++) {
        cin >> arr[i];
    }
    for (i = 1; i < N; i++) {
        for (j = i; j > 0; j--) {
            if (arr[j] < arr[j-1]) {
                swap(&arr[j], &arr[j-1]);
            }
        }
    }
    cout << "Sorted: ";
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
    printf("\n");
}

Lastly, this is a code in C++ that does Bubble Sort

#include <iostream>
#include <string.h>
using namespace std;
#define swap(a, b) {int temp = a; a = b; b = temp;}
int main() {
    int N, arr[100];
    cout << "Enter the size of the data set: ";
    scanf("%d", &N);
    cout << "Enter the values of the data set: ";
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < N-i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
    cout << "Sorted: ";
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

Explanation:
Selection sort is a sorting algorithm that divides the data set into two values: sorted and unsorted. It finds the smallest element in the unsorted part of the data set and puts that value at the very front of the unsorted part. The unsorted part then decreased in size by 1 after this process is done to exclude the newly sorted element.
Insertion sort is another sorting algorithm that sorts the values in a data set. It selects the leftmost element of the unsorted part of the data set and finds the right place of that element in the sorted part of the array. As this requires quite a significant number of comparisons, this sorting algorithm tends to be used in data sets that are already somewhat sorted.
Lastly, the bubble sort is a type of sorting algorithm that, although with a simpler code, takes a lot longer to sort and requires a significantly greater number of comparisons which makes it quite an inefficient code. What this code does is that it compares each and every single element of the array and swaps one with another if it is larger. As the process goes on, it places the largest element on the rightmost side of the array, sorting the data set.