[자료구조] 16 선택정렬
📌정렬 Sorting
주어진 레코드를 원하는 키 필드 값의 순서대로 나열하는 작업
✔️내부 정렬 (Internal Sort)
레코드의 리스트를 주메모리에서 처리
레코드의 수가 메모리에 모두 적재될 정도로 적으면 내부 정렬로 충분
✔️외부 정렬 (External Sort)
하드 디스크와 같은 별도의 보조 기억장치를 사용하여 처리
레코드의 수가 주메모리의 크기보다 많을 경우 외부 정렬 + 내부정렬 필요
❓성능은?
키 값의 비교 횟수, 데이터 이동 횟수에 의해 평가됨
✔️대표적인 내부 정렬 알고리즘 종류
선택 정렬 (Selection Sort)
버블 정렬 (Bubble Sort)
삽입 정렬 (Insertion Sort)
퀵 정렬 (Quick Sort)
쉘 정렬 (Shell Sort)
힙 정렬 (Heap Sort)
기수 정렬 (Radix Sort)
합병 정렬 (Merge Sort)
📌선택 정렬
1. 주어진 원소 집합에서 최소값을 찾는다
2. 최소값을 정렬 리스트로 이동시킨다
3. 그 다음 최소 값을 찾아서 정렬 리스트의 왼쪽에서 오른쪽 방향으로 추가
4. 정렬할 원소가 없을 때까지 반복한다
❗️시간 복잡도 : O(n^2)
최소값, 최대값을 찾는데 n번 비교
이 과정을 n번 반복
👉 알고리즘
for(n개의 원소 각각에 대해 반복)
{
기준 원소를 포함하여 최소/최댓값 탐색
기준 원소와 최소/최댓값 교환
정렬된 원소 제외한 나머지 원소에 대해 반복
}
| 9 | 4 | 5 | 11 | 8 |
| 🔑key | 👆min | 4보다 크니까 min 그대로 | 4보다 크니까 min 그대로 | 4보다 크니까 min 그대로 |
| 4 | 9 | 5 | 11 | 8 |
| 👆min이 넘어왔다 | ||||
| 4 | 9 | 5 | 11 | 8 |
| 🔑key (다음 칸으로) | 👆min | 5보다 크니까 min 그대로 | 5보다 크니까 min 그대로 | |
| 4 | 5 | 9 | 11 | 8 |
| 👆min이 넘어왔다 | ||||
| 4 | 5 | 9 | 11 | 8 |
| 🔑key (다음 칸으로) | 👆min | min 갱신 (11보다 작음) | ||
| 4 | 5 | 8 | 11 | 9 |
| 👆min이 넘어왔다 | ||||
| 4 | 5 | 8 | 11 | 9 |
| 🔑key (다음 칸으로) | 👆min | |||
| 4 | 5 | 8 | 9 | 11 |
#include <stdio.h>
void print_array(int num[], int n);
void selection_sort(int num[], int n);
void main(){
int num[] = { 9, 4, 5, 11, 8 };
selection_sort(num, 5); //원소의 갯수 현재 5개
}
void print_array(int num[], int n){
int i;
for (i=0; i<n; i++){
printf("%d ", num[i]);
}
printf("\n");
}
void selection_sort(int num[], int n){
int i,j,min,temp;
for (i=0;i<n-1;i++){
min=i;
for(j=i+1;j<n;j++){
if(num[min]>num[j]){
min = j;
}
}
temp = num[i];
num[i] = num[min];
num[min] = temp;
print_array(num, n);
}
//print_array(num, n);
}
//결과
4 9 5 11 8
4 5 9 11 8
4 5 8 11 9
4 5 8 9 11
👆최소값 우선 탐색 방법
📌최대값 우선 탐색 방법 코드도 짜보자❗️
왜 자꾸 세그멘테이션 오류가 나냔 말이다 😞😞
이럴땐 진짜 코드 리뷰 해주는 사람 있었으면 제 3자의 입장에서 봐야 좀 아는데 후,,
🙀🙀 똑같은 코드 다시 썼더니 세그멘테이션 오류가 안났다,, 역시 컴퓨터는 오류가 나도 이해가 안되고 안나도 이해가 안돼..
#include <stdio.h>
void print_array(int num[], int n);
void selection_maxsort(int num[], int n);
void main(){
int num[] = { 9, 4, 5, 11, 8 };
selection_maxsort(num, 5); //원소의 갯수 현재 5개
}
void print_array(int num[], int n){
int i;
for (i=0; i<n; i++){
printf("%d ", num[i]);
}
printf("\n");
}
void selection_maxsort(int num[], int n){
int i,j,max,temp;
for (i=n-1;i>0;i--){
max=i;
for(j=i-1;j>=0;j--){
if(num[max]<num[j]){
max = j;
}
}
temp = num[i];
num[i] = num[max];
num[max] = temp;
print_array(num, n);
}
//print_array(num, n);
}
//결과
9 4 5 8 11
8 4 5 9 11
5 4 8 9 11
4 5 8 9 11
👆최댓값 우선 탐색 방법
완벽하게 이해했다 ! 완료 !