백준 2750번: 수 정렬하기

시간복잡도가 O(n^2)인 정렬방법을 사용하기

⚠️모든 배열의 시작 인덱스는 0입니다.

1. 버블소트

ex) 오름차순

크기가 n인 배열이 있을 때,
1. 처음 0번째원소와 1번째 원소를 비교해 0번째 원소가 크다면 두 원소를 swap한다.
2. 계속해서 과정을 반복하여 n-1번째 원소와 n번째 원소까지 비교한다.
3. 총 이 과정을 배열의 크기 n만큼 반복하면 정렬된 결과가 나온다.
4. n(n - 1) / 2

#include <iostream>
using namespace std;

void bubbleSort(int *arr, int size){
    for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size - 1; j++)
        {
            if(arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
    }
}

int main()
{
    int n;
    cin >> n;
    int *arr = new int[n];
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    bubbleSort(arr, n);
    for(int i = 0; i < n; i++)
    {
        cout << arr[i] << endl;
    }
}

2. 삽입정렬

ex) 오름차순

크기가 n인 배열이 있을 때,
1. 1번째 원소를 key로 잡고 key와 0번째 원소를 비교한다.
2. 만약 key가 0번째 원소보다 작다면 0번째 원소를 1번째 원소로 보낸다.
3. key값은 0번째 원소로 넣는다.
4. 2번째 원소를 key로 잡는다.
5. key와 1번째 원소를 비교한다.
6. 만약 key가 1번째 원소보다 작다면 1번째 원소를 2번째 원소로 보낸다.
7. key를 0번째 원소와 비교한다.
8. 만약 key보다 0번째 원소가 작다면 1번째 원소에 key값을 넣는다.
...(이 과정을 n - 1번 반복)...
❗️배열은 앞에서부터 정렬되어 오기 때문에 중간에 8번과 같은 경우가
   오게되면 반복문을 빠져나간다.
   빠져나갔을 때 키 값은 정렬된 배열의 다음 원소로 들어가게 된다.

#include <iostream>
using namespace std;

void insertionSort(int *arr, int size){
    int i, j, key;
    for(i = 1; i < size; i++)
    {
        key = arr[i];
        for(j = i - 1; j >= 0 && key < arr[j]; j--)
        {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = key;
    }
}

int main()
{
    int n = 0;
    cin >> n;
    int *arr = new int[n];
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    insertionSort(arr, n);
    for(int i = 0; i < n; i++)
    {
        cout << arr[i] << endl;
    }

}