패스트캠퍼스 챌린지 49일차

[C# 프로그래밍 : 02. 알고리즘 - 02.정렬 알고리즘 - 선택정렬]

 

1.  선택정렬(Selection sort)이란?

• 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식
• 주어진 숫자n개의 리스트에서 가장 작은 최소값을 찾는다
• 최소값을 맨 앞의 값과 교체한다(Swap)
• 교체한 맨 앞의 데이터는 정렬된 것으로 간주하고 다음 인덱스부터 1, 2 행위를 끝까지 반복한다.

 

2. 선택정렬의 특징

• 구현은 단순하지만 비교적 성능이 좋지 않음
• 두개의 for 루프의 실행횟수

 

3. 구현

int[] data = {20,15,1,5,10};
for(int i = 0; i<data.length; i++){
	int min = i;
    for(int j = i+1; j<data.length; j++){
    	if(data[min] >data[j])
        	min = j;
    }
    Swap(ref data[i], ref data[min]);   
}

static void Swap(ref int a, ref int b)
{
	int temp = a;
    a = b;
    b = temp;
}

 

4. Big-O표기법 :

• 알고리즘의 시간 복잡도 표현할 때 쓰임
• 데이터가 다섯 개 정도는 괜찮지만 백만 개 정도 되면 중요해짐..
• 알고리즘 내 연산의 횟수
• 알고리즘 최악의 실행시간 
• 상수는 버림

- 종류

• O(1) : 입력값에 상관없이 상수 1만큼 실행되었을때
• O(log n) : (ex. 이진탐색)
• O(n) : 입력한 n값만큼 반복문 실행. 선형 시간 알고리즘.  
• O(n log n) : 병합 정렬등 효율 좋은 알고리즘이 이에 해당됨
• O(n²)  : 반복문이 두개 중첩되어 실행되면 n*n번 실행됨 (ex. 버블 정렬)

 

 

---

빅오 표기법 잘 이해가 안 가는데 그냥 휙 넘어가셨다.

그래서 다른 블로그를 참고했지만 여전히 좀 약간 이해가 안 가는 부분이 있다.

아무래도 수학이 약해서 그런 것 같다.

다행히 쉽게 설명한 블로그 발견!

https://babbab2.tistory.com/88

https://codermun-log.tistory.com/235

 

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

 

<본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.>

#패스트캠퍼스 #패캠챌린지 #직장인인강 #직장인자기계발 #패스트캠퍼스후기

#C#과유니티로배우는게임개발올인원패키지Online.