본문 바로가기

알고리즘🔍

(4)

[알고리즘] 쉘 정렬 (Shell Sort) 쉘정렬이란, 선택정렬의 인접한 레코드를 바꿔 그룹을 나누어, 그룹마다의 선택정렬을 수행하는 정렬 방식을 통해 느려짐을 완화한 정렬 방식이다. ( 쉘 정렬의 경우 그룹의 크기만큼 레코드 이동이 가능해짐! ) void ShellSort(int A[], int n){ //입력 : A[0:n-1],n: 정렬할 원소의 개수 //출력 : A[0:n-1] : 정렬된 배열 int h,i,j,Value; h=1; do h = 3*h+1; while (h h->4 -> h=1로 진행된다. do { h=h/3; for (i=h; iValue){ A[j]=A[j-h]; j -= h; if (j1); n을 넘지 않는 h값을 찾아서 진행한다. 선..

[알고리즘] 버블정렬(Bubble Sort) 버블정렬은 인접한 데이터들 간의 자리바꿈을 하는 정렬방식이다. void BubbleSort(int A[], int n){ int i; bool Sorted; while (!Sorted){ Sorted= true; for(i=1;iA[i]){ Swap(&A[i-1],&A[i]); Sorted = false; n--; } } } } 최선시간복잡도 : O(n)(이미 정렬이 완료된 배열을 정렬하는 경우) 평균시간복잡도 : O(n^2) 최악시간복잡도 : O(n^2) 제자리성 : 제자리 정렬 (상수 크기 메모리이기 때문에 제자리 정렬이다.) 안정성 : 안정된 정렬 (인접한 레코드만 자리바꿈 : 키값이 같을때 자리가 바뀌지 않기 때문에 안정적이다.)

[알고리즘] 선택정렬 (SelectionSort) 선택정렬은 모든 레코드가 key값으로 표현되어, 한 원소와 나머지 모든 원소를 비교하는 정렬이다. void SelectionSort(int A[], int n){ int i, j,MinIndex; for(i=0;i 복잡도는 입력자료 순서와 무관하다. 평균시간 복잡도=O(n^2) 최악시간 복잡도=O(n^2) 선택정렬의 경우 데이터의 내요ㅛㅇ과 관계없이 항상 마지막 단계까지 모든 비교가 이루어지기 때문에 평균 시간복잡도 == 최악시간복잡도이다. 제자리성 : 제자리 정렬 (주어진 메모리 공간 외에 추가적으로 사용하는 (상수크기) 메모리가 없는 정렬) 안정성 : 불안정한 정렬 (정렬후에 같은 값인 요소의 순서가 보장되지 않는 정렬방식) 인접한 요소와 스와칭이 일러나면 대부분 안정한 정렬이다.(떨어져있는 요소와 ..

[알고리즘] 알고리즘이란? program은 자료구조 + 알고리즘으로 이루어져있다. 예를 들어 최대값 탐색 프로그램을 짠다고 하면 그 안에는 탐색할 요소가 담긴 자료구조(ex. List) + 해당 알고리즘(ex. 순차탐색)이 들어있을 것이다. 이때 자료구조는 쉬운 접근과 수정을 위해 데이터를 조직하고 저장하는 방법이다. 자료구조에는 아래 표와 같이 크게 다섯가지가 있다. List Stack Queue Tree Graph 알고리즘의 유래 알고리즘은 Al-Khowarizmi (알콰리즈미)라는 한 수학자의 이름에서 착안되었다. 알고리즘의 정의 전형적으로 입력을 출력으로 변환하는 일련의 계산 단계를 의미한다. 알고리즘의 두가지 조건 정당성 - 모든 인풋에 대하여 정확한 아웃풋이 나오고 종료되어야 한다. (무한루프는 정당하지 않음) 효율성 ..

이전 1 다음

티스토리툴바