반응형 전공지식/ Data structure / Algorithm10 [Sort] 버블정렬 (Bubble Sort) 버블정렬 (Bubble Sort) 버블정렬에 대해서 알아보겠습니다. 버블 정렬은 자기자신 뒤에 오는 요소와 끊임없이 비교하면서, 오름차순일 경우 가장 큰 수가 뒤에서부터 정렬되는 정렬알고리즘입니다. 또한 마지막 Sorting시에는 첫번째 요소를 제외하고 모두 정렬됐기 때문에 자연스럽게 첫번째정렬됩니다. 그림을 보면서 이해해 봅시다. 우선 5와 3을 비교하고 5가 더 크기 때문에 교환합니다.다음 버블인 5와 4를 비교하고 5가 더 크기 때문에 교환합니다. 이제 5와 1을 비교하고 5가 더 크기 때문에 교환한 후 정렬 1회전을 종료합니다. 5가 가장 큰 수였기 때문에 차례대로 진행되는 모든 비교에서 이기고 결국 제일 큰 숫자의 자리인 끝의 자리를 차지하게 됩니다. 다음 2회전을 보겠습니다.3과 4를 비교하고.. 2017. 10. 25. [Sort] 선택정렬 (Select Sort) 선택정렬 (Select Sort) 선택정렬에 알아보겠습니다. 선택정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾고, 정렬 대상 요소와 교환하는 방식이다. 간단히 제일 작은 요소부터 앞에서 부터 차례대로 줄을 서는 것이다. 그림으로 설명해보자. 3회전을 하는 과정이다. 우선 회색으로 칠해져 있는 것은 아직 정렬되지 않은 영역이다.정렬되지 않은 영역 첫번째 부터 차근차근 정렬을 하면 된다. 정렬되지 않은 요소 중 첫번째 요소인 5와 나머지 요소를 비교하여 가장 작은 요소의 index 위치를 찾는다. 찾은 후 교환해주면 된다. 위 원리를 코드로 나타내면 다음과 같다. package Sort; import java.util.Arrays; public class SelectSort { public static .. 2017. 10. 24. [Sort] 삽입정렬 (Insert Sort) 삽입정렬(Insert Sort) 삽입정렬은 정렬한 부분과 정렬하지 않은 부분을 나눈 후 정렬할 대상인 대상을 정렬하지 않은 부분에서 차례대로 꺼내 정렬한 부분의 요소들과 차례대로 비교를 하면서 자신이 삽입될 인덱스를 찾는다. 이 과정에서 정렬된 부분의 요소들이 현대 정렬대상보다 클 경우 한칸씩 뒤로 밀리면서 정렬대상이 들어갈 공간을 마련해준다. (오름차순인 경우) 자 말로하니까 어렵다. 한 단계씩 그림으로 설명해보자. 파란색은 이미 정렬된 영역이라고 하자. 빨간영역은 정렬되지 않은 영역이다.삽입정렬은 기본적으로 0번째 요소는 정렬된 것이라 가정하고 시작한다. 우선 1회전 과정을 살펴보자. 0번째 요소는 정렬됐다고 가정했으니, 1번째 요소 값이 정렬할 대상이다. Temp에 1번째 요소 값인 2를 임시저장한.. 2017. 10. 24. [Algorithm] 이진탐색트리 (미작성) 2017. 10. 6. 이전 1 2 3 다음 반응형
