알고리즘 썸네일형 리스트형 All that Sort - [3] Selection Sort (선택정렬) 선택정렬! 단도직입적으로 말하면, n번째 자리에 맞는 수를 찾아서 n번째 자리에 넣는 정렬이다. in-place 정렬이고 O(n2)의 복잡도를 가지는데, 위에서 설명한 것처럼, 좀 무식한-_-방법으로 sorting을 하기 때문에 bubble sort 보다 아주 약~간 뛰어나지만 insertion sort 보다는 "일반적으로" 좋지 못한 성능을 보인다. 어찌됐든, pseudocode 를 봅시다. 1 for i = 0 to n-2 do 2 min = i 3 for j = i+1 to n-1 do 4 if (a[j] < a[min]) do 5 min = j 6 if(i != min) do 7 swap a[i] and a[min] 그림에서와 같이 첫자리에 맞는 수 2, 둘째 자리에 맞는 수 3, 그리고 4, 5.. 더보기 All that Sort - [2] Insertion Sort (삽입정렬) 이번에 알고리즘 수업을 Self-Study 로 다시 듣게 된 김에 알고리즘 관련 포스팅을 다시 시작해볼까 한다. Bubble Sort는 사실 정렬이라고 부르기도 민방한 정렬이다. 삽입정렬은 그보다는 조금 더 elegant 한 방법이라 할 수 있다. 우선 pseudocode 를 보자. 1 for i = 1 to n-1 do 2 tmp = a[i] 3 j = i 4 while j > 0 AND a[j-1] > tmp do 5 a[j] = a[j-1] 6 j = j - 1 7 a[j] = tmp 우선 0번 원소는 건너뛰고 1번부터 차근차근히 보면서 가는 것이다. 즉, 1번원소일 때는 0~1을 정렬하고, 2번원소일때는 0~2를 정렬하고.. 이런 식으로 맨 뒤의 원소의 적절한 위치를 찾아서 마지막 원소까지 위치를.. 더보기 이전 1 다음
