본문 바로가기

Algorithm

 (13)
002. 선택 정렬(Selection Sort) 1.알고리즘설명 가장 직관적인 정렬이다. 오름차순 정렬을 한다면, - n개 수에 대해서 가장 작은 값을 찾아서(n-1번 비교) 그 값을 가장 왼편에 놓고(0번 째 자리에), - 나머지 수에 대해서 가장 작은 값을 찾아서 1번 째 자리에 놓고, - 이러한 과정을 수가 끝날 때까지 수행 아래 그림은 정렬되는 모습을 애니메이션으로 보여준다. (출처: wikipedia) 2. 알고리즘 Flow i=0 i가 n-2가되면 종료 i항부터 (n-1)항까지에서 가장 작은 값을 tmp에 저장 tmp = min(data[i] ~ data[n-1]) i항과 tmp를 교환 swap(i, tmp) i를 하나 중가시키고 2로 돌아간다. 3. 소스 코드 inline void swap(int& left, int& right) { in..
001. 정렬(Sorting) 정렬(sorting)은 탐색(searching)과 더불어 컴퓨터를 이용한 문제해결에있어 가장 많이 부닥치는 문제이다. 정렬은 원하는 순서대로 데이터를 배치하는 것으로,{3,4,2,2,1,10}와 같은 6개의 데이터가 있을 때 다음과 같이 정렬될 수있다. 오름차순(ascending order) 정렬: 작은 값에서 큰 값으로 배치 {1,2,2,3,4,10} 내림차순(descending order) 정렬: 큰 값에서 작은 값으로 배치 {10,4,3,2,2,1} 정렬의종류 여러 가지 정렬 방법이 있고,일반적으로 퀵정렬(QuickSort)이 가장 빠르지만, 데이터 특성에 따라(미리 어느정도 정렬되어 있다든지)다른 정렬방법이 좋은 경우도 있다. 선택 정렬(SelectionSort) 삽입 정렬(InsertionSor..
글쓰기에 앞서... 정렬과 탐샘(Sorting and Searching)은 알고리즘의 기본중의 기본이면서, 사실 완벽하게 이해하기 쉽지 않은 분야이다. 여기서는, 정렬과 탐색에 대해 알고리즘 공부의 구색 맞추기 정도가 아닌, 알고리즘을 구성하는 맨 밑바닥부터 원리부터 실제 활용가능한 코드까지 다 다루려고 노력할 것이다. 코드의 작성은 C++로 할 것이다. 실제 현장에서 사용하기 위해서는, 역시 속도 빠른 C 언어 계열을 사용하는 것이 최고다. 버전은 C++ 11 기준.

티스토리툴바