목차
👀, 🤷♀️ , 📜, 📝
이 아이콘들을 누르시면 정답, 개념 부가 설명을 보실 수 있습니다:)
정렬이란?
- 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 (오름차순) 또는 큰 순서부터 (내림차순) 늘어놓은 것임
- 정렬되어 있는 데이터들은 다음과 같은 작업을 수행할 때 응용
① 데이터를 탐색할 때
② 리스트에 있는 다른 항목들을 비교할 때
[장점]
- 안정된 정렬 방법
- 대부분 정렬되어있으면 효율적
[단점]
- 많은 이동 필요 ➡️ 레코드가 큰 경우 불리
📜 안전성이란?
안정성: 동일한 키값을 갖는 레코드들이 정렬 후에도 이들의 상대적 순서가 동일해야 함
안전성 충족 정렬 : 삽입정렬, 버블정렬, 병합정렬 등
📜 레코드란?
레코드: 정렬시켜야 될 대상
- 여러 개의 필드(field)로 이루어짐
- 정렬 키(sort key): 정렬의 기준이 되는 필드
정렬이란 레코드들을 키(key)의 순서로 재배열하는 것
선택정렬
리스트의 숫자중 가장 작은 숫자를 찾아서 왼쪽부터 정렬시켜나가는 방식
수도코드
SELECTIONsort(A)
n = A.length
for j <- 1 to n-1
smallest = j // 처음값 잡아주기
for i = j+1 to n // j뒤에 값을 비교하며 최소값 찾을것임
if A[i]<A[smallest]
smallest = i // 잡아준 처음값 계속 업데이트 하며
// 최솟값 찾으면 빠져나옴
swap A[j],A[smallest]
코드 설명
① 데이터 중에서 가장 작은 값을 찾는다
② 가장 작은 수와 찾는 범위에서 가장 위에 있는 수의 위치를 바꾼다
③ ①②를 반복(범위는 1씩)
시간 복잡도
[최선의 경우]
- 즉 이미 정렬되어있는경우 n-1 번이다(배열 전체를 쭉 살펴봄)
- O(\(n\))
[최악의 경우]
- for문이 2번
- 모든 단계에서 안페놓인 자료 전부 이돌
- O(\(n^2\))
- \[∑_(𝑖=1)^(𝑛−1)▒𝑖=(𝑛(𝑛−1))/2=𝑂(𝑛^2)\]
평가
성능이 좋지 않음
구현
파이썬
def Selectionsort(A):
for j in range(0, len(A)-1):
smallest = j
for i in range(j+1 ,len(A)-1):
if A[i] < A[smallest]:
smallest =i
A[j], A[smallest] = A[smallest], A[j]
자바
public class Selection {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] A = {3,44,38,5,47,15,36,26};
for (int i = 0; i < A.length - 1; i++) {
int smallest = i;
for (int j = i + 1; j < A.length; j++) {
if (A[j] < A[smallest])
smallest = j;
}
int tmp = A[i];
A[i] = A[smallest];
A[smallest] = tmp;
}
// 정렬된 A를 읽어 출력해주는 함수입니다
for(int k = 0; k<A.length-1; k++) {
System.out.println(A[k]);
}
}
}