선택정렬

15 Jan 2021 in Algorithms

알고리즘 설명

IDEA : 최솟값이나 최댓값을 선택해서 정렬하는 알고리즘

1. 정렬되지 않은 숫자 중 최솟값 선택
2. 선택 된 숫자를 정렬되지 않은 숫자 중 첫번째와 바꾸면 정렬된다.
3. 계속 반복한다.

정확성 증명

오 이런것도 하는구만

수학적 귀납법을 이용

• i 번째 선택한 숫자가 i번째 작은 숫자인지 증명

성능 분석

• 주요 함수가 뭐고, 그걸 몇번 수행하는가?
• 시간 복잡도 : Θ(n^2), 공간 복잡도 : Θ(n)

JAVA 코드

int[] ary = {11,3,5,2,3,4};
int mini;
int ind;
for (int i =0;i<ary.length;i++){
    mini=ary[i];
    ind=i;
    for(int j =i;j<ary.length;j++) {
        if(mini > ary[j]) {
            mini=ary[j];
            ind=j;
        }
    }
    ary[ind]=ary[i];
    ary[i]=mini;
}

어레이 프린트 시 다음과 같이 두개의 방법 사용 가능

1/
for (int i=0;i<ary.length;i++) {
    System.out.print(ary[i] + " ");

}

2/
System.out.println(Arrays.toString(ary));

PYTHON 코드

ary = [11,3,89,1,43,73]

for i in range(0,len(ary)):
  mini=ary[i]
  for j in range(i,len(ary)):
    if(mini>ary[j]):
      mini= ary[j]
      ind = j
  ary[ind] = ary[i]
  ary[i]=mini

print(ary)

JAVA와 Python 다른 점

• 어레이 표시
  • JAVA : {}
  • PYTHON : []
• 어레이의 LENGTH 구하기
  • JAVA : ary.length
  • PYTHON : len(ary)
• ary print 시
  • JAVA :배열의 주소 값이 나옴
  • PYTHON : 원소들이 나옴