정렬

1. 버블 소트

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
 
 
int main()
{
     int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
 
    for(int i = 0 ; i < 10 ; i++)
    {
        for(int j = 0 ; j < size-1 ; j++)
        {
            if(arr[j] > arr[j+1])
                swap(arr[j] , arr[j+1]);
        }
    }
 
    for(int i = 0 ; i < 10 ; i++)
        cout << arr[i] << ' ';
 
}

 

2. 삽입정렬

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
 
 
int main()
{
     int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
 
    for (int i = 1; i < size; i++)
    {
        int key = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] > key)
                arr[j + 1] = arr[j];
            else
                break;
        }
        arr[j + 1] = key;
    }
}

3. 선택정렬

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
     int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
 
    for (int i = 0; i < size; i++)    
    {
        int min = i;
        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[min])
                min = j;
        }
        if (i != min)
            swap(arr[i], arr[min]);
    }
 
    for (int i = 0; i < 10; i++)
    {
        cout << arr[i] << " ";
    }
 
}

4. 퀵정렬

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
 
void quick_sort(int left, int right)
{
    if (left >= right)
        return;
 
    swap(arr[left], arr[(left + right) / 2]); // 역순일때의 최악을 피한다.
    int i = left + 1;
    int j = right;
    int pivot = left;
 
    while (1)
    {
        while (i <= right && arr[i] < arr[pivot]) // left는 피벗보다 크거나 같을 때 멈춤
            i++;
        while (j > left&& arr[j] > arr[pivot])
            j--;
 
        if (i <= j) // 이건 부등호 상관 없다.
            swap(arr[i++], arr[j--]);
        else
            break;
    }
    swap(arr[pivot], arr[j]); // pivot 위치와 high를 스왑
 
    quick_sort(left, j - 1);
    quick_sort(j + 1, right);
}
 
int main()
{
    quick_sort(0, 9);
 
    for (int i = 0; i < 10; i++)
        cout << arr[i] << " ";
}

5. 병합정렬

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
int temp[10];
 
void merge(int left, int mid, int right)
{
    int i, j, k;
    i = left;
    j = mid + 1;
    k = left; // sorted
 
    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j]) // 이걸 잘해야 stable이 안깨진다.
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
 
    if (i > mid)
    {
        for (int l = j; l <= right; l++)
            temp[k++] = arr[l];
    }
    else
    {
        for (int l = i; l <= mid; l++)
            temp[k++] = arr[l];
    }
 
 
    for (int l = left; l <= right; l++)
        arr[l] = temp[l];
}
 
 
void merge_sort(int left, int right)
{
    if(left >= right)
        return;
    
    int mid = (left + right) / 2;
    merge_sort(left, mid);
    merge_sort(mid + 1, right);
    merge(left, mid, right);
}
 
 
 
int main()
{
    merge_sort(0, 9);
 
    for (int i = 0; i < 10; i++)
        cout << arr[i] << " ";
}