자료 구조 : Selection Sort, Merge Sort(2) 이번 포스팅에서는 Merge Sort (합병정렬) 에 대해 알아보자. 지난 번에 Selection Sort 보다 좀 더 생각하기 쉬운 정렬 방법으로 생각한다. 우선 Merge Sort에 대해 알아 보기 전에 Merge에 대해 알아보자. Merge 와 Merge Sort 는 서로 같은 뜻 같지만 실제로는 둘이 조금 다르다. 그럼 Merge Algorithm에 대해 그림으로 설명하겠다. 위와 같은 흐름을 반복하는것이 Merge Algorithm의 흐름이다. 이러한 Merge Algorithm을 이용한것이 Merge Sort 이다. Merge Sort에 대한 그림을 보면서 설명 해보겠다. 어떤 배열을 하나씩 하나씩 따로 따로 나눈다음에 서로 2그룹씩 합치면서 점점 올라오면서 정렬하는 것이 Merge Sort의.. 더보기 자료 구조 : Selection Sort , Merge Sort (1) 오늘은 selection sort 와 merge sort 에 대해 알아보는 시간을 가지겠다. Selection Sort의 알고리즘 흐름은 다음과 같다. 어떤 배열이 있으면, 전체에서 제일 작은 값을 앞으로 옮긴다. 그 다음 나머지 부분에서 제일 작은 값을 앞으로 옮긴다. 그렇게 반복해서 결과적으로 정렬된 배열을 만들어 내는 것이다. 간단하게 코드로 작성하면 다음과 같다. Recursive Selection Sort 1 2 3 4 5 6 7 8 9 10 11 12 int sort (int a[], int n) // n 은 배열의 크기 { int i, j, m, t; for (i = 0; i k-1 a[k], .... , a[n-1] 중 최소값을 a[k]로 옮겼음! Invariant : k 번째 루프가 끝난.. 더보기 자료구조 시작 전 알기 (5) Arrays, Algorithms, Complexity, and Recursion 본격적으로 자료구조를 살펴보자. 첫번째로 살펴볼 자료구조는 프로그램 언어를 하나라도 배운 사람이면 이숙한 그 이름 배열이다. 배열에 대해 정리하면 다음과 같다. # Array ( 배열 ) 정의 : 연속된 주소, 동일한 Type 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있따. 사용 : 변화가 없거나 드문 자료 5 3 7 6 4 8 12 이런식으로 연속된 주소에 동일한 타입을 주르륵 붙여 놓은 자료구조이다. 이제 이 배열을 통해서 Binary Search 의 정확성과 속도를 알아보자. 보통 Binary Search의 코드는 다음과 같이 작성될 것이다... 더보기 이전 1 ··· 7 8 9 10 11 12 다음
