정렬2

• 

  210628 합병 정렬(merge sort) & 퀵 정렬(quick sort) 합병 정렬(merge sort) : 안정적, 분할 정복 알고리즘(문제를 작은 문제로 분리하고 각각 해결하여 합쳐서 문제를 해결하는 방법) 중 하나 리스트의 길이 0 또는 1이면 정렬된 것으로 취급, 아닌 경우는 비슷한 크기로 잘라 두 개의 리스트로 만듬 각 부분 리스트 재귀적으로 합병 정렬을 통해 정렬함 두 부분 리스트 합병 반복함 단: 만약 배열로 구성한다면 임시 배열 필요 , 제자리 정렬 아님 데이터의 크기가 큰 경우에는 이동 횟수가 많아 매우 비효율적 장 : 안정적인 정렬 방법, 데이터의 분포에 영향 덜 받음, 입력 데이터에 영향 덜 받음 레코드를 연결 리스트로 구성하면, 링크 인덱스만 바꾸면 되기에 데이터의 이동은 무시할 수 있을 정도로 작아짐, 제자리정렬로 구현 가능 큰 데이터 다를 때 연결 리.. 미가공 필기(알고리즘) 2021. 6. 28.

• 210628 선택 정렬(selection sort) 선택 정렬 (selection sort) : 제자리 정렬 알고리즘 중 하나 입력 배열 외의 다른 추가 메모리 필요 없음 주어진 배열에서 최솟값 찾음 그 값을 맨 앞의 값과 교환함 맨 처음 위치를 제외한 배열 범위에서 1~2번 반복 즉 1,2 번이 하나의 사이클로 한번 할때 마다 배열 내의 가장 작은 원소를 맨 앞으로 땡겨오는 작업을 n번하여 정렬하는 방법이다. 장 : 자료의 이동 횟수가 예상 가능함 단 : 불안정함, 값이 같은 레코드가 있는 경우에 상대적 위치가 변경될 수 있음 시간복잡도 배열의 크기 n 이라 하였을 때 비교 횟수 : n-1, n-2, n-1, .... 2, 1 번 교환 횟수 : 한 번 교환할 떄( swap 함수) 3번 => 최대 3(n-1) 번 그러므로 Best (모두 정렬되어 있는 상.. 미가공 필기(알고리즘) 2021. 6. 28.