본문 바로가기

전체 글119

#015 힙 정렬 # 문제) 아래와 같이 정렬되지 않은 배열이 있을때 힙 정렬을 사용하여 오름차순 정렬하여라. 5 2 4 3 1 힙 정렬의 힙의 특징을 이용하여 정렬하는 방식을 말한다. 힙의 특징은 아래와 같다. 힙은 완전 이진트리 구조를 활용된다. 추가 시에는 맨 마지막 원소에 추가되며 루트 방향으로 올라가면서 부모와 값을 비교해 적절한 위치를 찾는다. 삭제 시에는 최소 힙으로 구성했을 경우, 최소값을 최대 힙으로 구성했을 경우, 최대값을 반환하고 삭제된다. 또한 삭제 후 이진트리 구조를 유지하기 위해 원소의 마지막 값을 root에 위치하여 자식 중 우선순위가 높은 값과 비교하여 원소의 마지막 값의 위치를 찾는다. 즉, 힙 정렬의 경우, 추가시에 정렬이 된 상태로 들어가게 되며 삭제 시에는 최소(또는 최대) 값을 반환하.. 2017. 7. 18.
#014 삽입 정렬 # 문제) 아래와 같이 정렬되지 않은 배열이 있을때 삽입 정렬을 사용하여 오름차순 정렬하여라. 5 2 4 3 1 선택정렬은 방향이 버블과 선택과 다르다. 버블과 선택은 왼쪽에서 오른쪽으로 이동했다면 삽입 정렬은 두번째 부터 시작하여 왼쪽으로 이동하며 삽입될 위치를 찾는다. 만약 왼쪽 값이 더 큰 경우, 왼쪽 값을 현재 인덱스 값에 저장한다. (배열 shift처리) 더이상 왼쪽으로 이동할 수 없거나, 왼쪽값이 더 작다면 삽입할 위치를 찾은 것이므로 해당 위치에 값을 저장한다. int tempValue = 2; 5 2 4 3 1 5 5 4 3 1 2 5 4 3 1 int tempValue = 4; 2 5 4 3 1 2 5 5 3 1 2 5 5 3 1 2 4 5 3 1 int tempValue = 3; 2 4.. 2017. 7. 18.
#013 선택 정렬 # 문제) 아래와 같이 정렬되지 않은 배열이 있을때 선택 정렬을 사용하여 오름차순 정렬하여라. 5 2 4 3 1 선택정렬이란 오름차순 정렬의 경우, 처음 위치부터 시작하여 최소값을 찾아 첫 인덱스 값과 최소값을 swap 한다. 다음 단계에서는 두번째 인덱스부터 시작하여 최소값이 있는 인덱스를 찾아 swap한다. 계속 반복. *붉은 색은 최소값 인덱스 5 2 4 3 1 5 2 4 3 1 5 2 4 3 1 5 2 4 3 1 1 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 2 4 3 5 swap 일어나지 않음. 1 2 4 3 5 1 2 4 3 5 1 2 3 4 5 1 2 3 4 5 swap 일어나지 않음. package dataStructure.sort.selection; public class Se.. 2017. 7. 18.
#012 버블 정렬 # 문제) 아래와 같이 정렬되지 않은 배열이 있을때 버블 정렬을 사용하여 오름차순 정렬하여라. 5 2 4 3 1 버블 정렬이란 인접한 두개의 원소끼리 비교하여 정렬해가는 방법을 말한다. O(n^2) 성능을 가짐. 먼저, 정렬이 진행되는 순서를 보며 규칙성을 찾아보자. 2 5 4 3 1 2 4 5 3 1 2 4 3 5 1 2 4 3 1 5 2 4 3 1 5 2 3 4 1 5 2 3 1 4 5 2 3 1 4 5 2 1 3 4 5 1 2 3 4 5 1회전이 완료되면 맨 마지막 원소는 정렬이 완료 됬다는 것을 알 수 있다. 즉, 정렬이 진행 되는 과정을 보면 회전 수가 진행 될 때마다 비교하는 횟수가 그에 맞게 감소하고 있는 것을 알 수 있다. package dataStructure.sort.bubble; pu.. 2017. 7. 18.

티스토리툴바