Computer/Algorithm 썸네일형 리스트형 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를 정렬하고.. 이런 식으로 맨 뒤의 원소의 적절한 위치를 찾아서 마지막 원소까지 위치를.. 더보기 All that Sort - [1] Bubble Sort (거품정렬) 찾기(search) 와 정렬(sort)는 뗄래야 뗄 수 없는 존재로 현대 컴퓨팅의 매우 중요한 분야이다. 조금이라도 프로그래밍을 해보았다면, 효율적인 정렬과 찾기 방법이야말로 프로그램 최적화의 첫 단계라는 것을 알 것이다. 그래서 알고리즘 수업 시간에 배웠던 정렬 알고리즘들에 대해 하나씩 점검/정리 해보고자 한다. [1] Bubble Sort (거품정렬) 다들 수영장에서 수영을 해 본 기억이 있을 것이다. 수영하기, 물먹기-_- 등등 다양한 액션이 나오는 가운데 혹 물 속에서 숨을 뱉어보았는가? 자신의 입에서 나온 기체 방울이 점점 커지면서 수면으로 상승하는 것을 보았을 것이다. 이와 동일한 방법이 Bubble Sort 이다. 말 그대로, 거품정렬. 일단 예시를 보자. 4 9 3 6 2 버블 소트는 처음.. 더보기 이전 1 다음
