수업시간에 사용하는 정렬은 버블 정렬과 선택정렬 두가지이다. 주로 기본 정렬인 선택 정렬을 사용하는데 자꾸 틀린다. 그래서 다시 한번 정리를 해야겠다...
버블정렬
먼저 버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 예를 들면 첫번째 방과 두번째 방을 비교하는 것이다. 둘을 검사하여 크기가 순서대로 되어있지 않으면 서로 교환한다.
배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 오름차순으로 정렬
- 1 회전
- 첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.
- 2회전
- 첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
- 첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
- 3회전
- 첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
- 첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
- 4회전
- 첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.
버블정렬 C언어 코드
#include<stdio.h>
void bubble_sort(int arr[], int len) {
for (int i = 0; i < len; i++) {
for (int j = 1; j < i; j++) {
if (arr[j] < arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
void main() {
int arr[5] = { 7, 4, 5, 1, 3 };
int len = 5;
bubble_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d\n", arr[i]);
}
}
선택 정렬
선택 정렬은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다.
배열에 9, 6, 7, 3, 5가 있다고 가정
- 주어진 배열 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
- 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
선택정렬 C언어 코드
#include<stdio.h>
void selction_sort(int arr[], int len){
for(int i=0; i<len-1; i++){
for(int j=i+1; j<len; j++){
if(arr[j]<arr[i]){
int tmp=arr[j];
arr[j]=arr[i];
arr[i]=tmp;
}
}
}
}
void main(){
int arr[5]={9, 6, 7, 3, 5};
int len=5;
selction_sort(arr,len);
for(int i=0; i<len; i++){
printf("%d\n",arr);
}
}