Day2 : 정렬알고리즘의 개요와 선택정렬 (Selection Sort)

선택정렬의 한계 : 시간이 효율적이지 않다!

 

문제1 : 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

 

가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘 == 선택 알고리즘

1 2 5 8 7 6 4 3 10 9

1 2 3 8 7 6 4 5 10 9

1 2 3 4 7 6 8 5 10 9

1 2 3 4 5 6 8 7 10 9

1 2 3 4 5 6 7 8 10 9

 

=>1 2 3 4 5 6 7 8 9 10

 

 

• 선택 정렬의 시간복잡도 O(N^2)

 

아까 문제를 확인해 볼때

10 + 9 + + …+ 1

=> 10*(10+1)/2

=> 55번의 비교연산을 한 것임

=> N *( N+1) / 2

=>O(N*N)

 

특정 알고리즘의 연산횟수를 나타낸다.