버블정렬
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
void BubbleSort(vector<int>& vec)
{
int n = vec.size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (vec[j] > vec[j + 1])
{
swap(vec[j], vec[j + 1]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> vec = { 4,2,6,9,1 };
BubbleSort(vec);
for (auto it : vec)
{
cout << it << " ";
}
}
버블 정렬(bubble sort) 알고리즘의 개념 요약
- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
- 선택 정렬과 기본 개념이 유사하다.
버블 정렬(bubble sort) 알고리즘의 구체적인 개념
- 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
- 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
버블 정렬(bubble sort) 알고리즘의 예제
- 배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
선택정렬
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
void SelectedSort(vector<int>& vec)
{
int n = vec.size();
for (int i = 0; i < n; i++)
{
int min = vec[i];
int index = i;
for (int j = i + 1; j < n; j++)
{
if (min > vec[j])
{
min = vec[j];
index = j;
cout << "min: " << min << "index: " << index << endl;
}
}
vec[index] = vec[i];
vec[i] = min;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> vec = { 4,2,6,9,1 };
SelectedSort(vec);
for (auto it : vec)
{
cout << it << " ";
}
}
선택 정렬(selection sort) 알고리즘 개념 요약
- 제자리 정렬(in-place sorting) 알고리즘의 하나
- 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
- 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
- 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.
- …
- 과정 설명
1. 주어진 배열 중에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
선택 정렬(selection sort) 알고리즘의 구체적인 개념
- 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
- 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.
선택 정렬(selection sort) 알고리즘의 예제
- 배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
삽입정렬
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
void InsertionSort(vector<int>& vec)
{
int n = vec.size();
for (int i = 1; i < n; i++)
{
int key = vec[i];
int j = i - 1;
while (j >= 0 && vec[j] > key)
{
vec[j + 1] = vec[j];
j--;
}
vec[j + 1] = key;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> vec = { 4,2,6,9,1 };
InsertionSort(vec);
for (auto it : vec)
{
cout << it << " ";
}
}
삽입 정렬(insertion sort) 알고리즘 개념 요약
- 손안의 카드를 정렬하는 방법과 유사하다.
- 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.
- 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
- 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
삽입 정렬(insertion sort) 알고리즘의 구체적인 개념
- 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
- 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
- 처음 Key 값은 두 번째 자료부터 시작한다.
삽입 정렬(insertion sort) 알고리즘의 예제
- 배열에 8, 5, 6, 2, 4가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
