oliver-DevLog

합병 정렬(Merge Sort)이란? 비교기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 임시 배열 공간을 활용하여 정렬을 수행한다. 장점 안정적인 정렬 방법이다. 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일) 단점 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다. 합병 정렬 과정 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 2. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 4. 두 ..

퀵 정렬(Quick Sort)이란? 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 분할 정복 알고리즘 중 하나, 매우 빠른 수행속를 가지고 있는 정렬 방법이다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다. 장점 속도가 빠르다. 추가 메모리 공간을 필요로 하지 않는다.(퀵 정렬은 O(logn)만큼 메모리를 필요로 한다.) 단점 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다. 분할 정복(Divide And Qunquer) 방법 1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗..

삽입 정렬(Insertion Sort)이란? 자료의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입하여 정렬한다. 매 순서마다 해당 원소를 삽입해야할 위치를 찾아 해당 위치에 넣는다. 장점 레코드의 수가 적을 경우 다른 복잡한 정렬 방법보다 유리할 수 있다. 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다. 단점 레코드가 많고 크기가 크면 효율적이지 않다. 알고리즘의 순서 이전 레코드보다 작은 레코드를 선택한다. 한단계 씩 레코드를 교환하며 해당 레코드 위치를 찾아 넣는다. 의사 코드 전체적인 의사코드는 다음과 같다. for( i = 0 to n){ for( j = i -1 to 0, 현재 레코드가 키 레코드 보다 큰 경우){ 현재 레코드..

선택 정렬(Select Sort)이란? 제자리 정렬 알고리즘의 하나이다. 정렬되어 있지 않은 데이터에서 가장 작은 값을 뽑아 가장 앞의 데이터와 교환해 나가는 방식이다. 장점 구현이 간단하다. 비교 횟수에 비해 실제 교환 횟수가 적어 많은 교환이 일어나는 자료의 경우 효율적이다. 단점 정렬 시간이 오래걸린다. 알고리즘의 순서 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 의사 코드 전체적인 의사코드는 다음과 같다. for( i = 0 to n - 1){ for(j = i + 1 to n){ if(최소값 보다 작은 a[j]) 최소값이 들어있는 인덱스 저장; } 선택된 가장 작은 값과 a[i] 서로 맞바꾼다.; } ..