Algorithm

[알고리즘][파이썬/Python] 퀵 정렬 (Quick Sort)

정의 기준 값을 중심으로 작은 원소들은 왼쪽 부분집합으로, 큰 원소들은 오른쪽 부분집합으로 분할하여 정렬하는 방식의 정렬 알고리즘 * 퀵 정렬도 분할과 정복(divide and conquer) 기법을 이용하는 정렬 알고리즘이다. 하지만 병합 정렬과 차이가 있는데, 병합 정렬이 분할 후 정복하는 원리였다면, 퀵 정렬은 정복 후 분할하는 원리의 정렬 알고리즘이다. 우선 기준 값보다 작은 원소들을 왼쪽 부분집합으로, 기준 값보다 큰 원소들은 오른쪽 부분집합으로 구분하는 정복 절차를 밟고, 기준 값을 중심으로 2개의 부분 집합으로 분할한다. 동작 방식 0. 기준 값을 보통 피벗(pivot)이라고 부르며, 선택하는 기준은 다양하겠으나 일반적으로 가장 왼쪽 원소를 피벗으로 지정한다. 본 글에서도 가장 왼쪽 원소를 ..

[알고리즘][파이썬/Python] 병합 정렬 (Merge Sort)

정의 입력 자료를 부분집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 다음에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer) 기법 중 하나로, 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식의 정렬 알고리즘 동작 방식 (2-way 병합, 오름차순 정렬 기준) 0. 일반적으로 정렬한 상태의 자료를 담기 위해 입력 자료의 크기만큼의 새로운 배열(리스트)을 선언해줌. 그러나 해당 포스팅에 기재한 소스코드는 정렬한 원소를 새로운 리스트에 담지 않고 입력값인 기존의 리스트를 재사용했음. 동작 방식에 대한 설명은 새로운 리스트를 선언했다고 가정한 채 진행. 1. 입력 자료를 두 개의 부분집합으로..

[알고리즘][파이썬/Python] 쉘 정렬 (Shell Sort)

정의 - 일정 간격(interval) 떨어져 있는 원소들끼리 부분집합을 구성한 후 각 부분집합의 원소들에 대해서 삽입 정렬을 수행하되, 간격을 줄여가며 삽입 정렬을 반복하여 전체 원소들을 정렬하는 방식의 정렬 알고리즘 * 쉘 정렬은 삽입 정렬의 문제점을 극복하기 위해 개선한 정렬 알고리즘이다. 삽입 정렬의 경우, 주어진 자료의 정렬 상태에 따라 시간 복잡도가 많이 달라졌는데, 역순으로 정렬되어 있는 형태에 가까울수록 비교횟수가 아주 많이 늘어나는 치명적인 문제점이 존재했다. 그래서 Donald L. Shell 은 '간격(interval)'이라는 개념을 도입하여 위 언급한 문제점을 극복해내는 '쉘 정렬'을 고안해냈다. 동작 방식 0. 간격(interval) h = 정렬할 배열(혹은 리스트)의 길이 % 2 ..

[알고리즘][파이썬/Python] 삽입 정렬 (Insertion Sort)

정의 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식의 정렬 알고리즘 동작 방식 0. 정렬할 배열(혹은 리스트)은 두 개의 부분집합 S와 U로 구분 * S (Sorted) : 정렬된 앞부분의 원소들 * U (Unsorted) : 아직 정렬되지 않은 나머지 원소들 1. U의 가장 앞에 있는 원소를 꺼내어 S의 마지막 원소부터 첫 번째 원소까지 대소 비교하며, S 내에 적절하게 삽입될 위치를 탐색 2. 대소 비교가 끝나면, U에서 꺼낸 원소를 탐색한 위치에 삽입 3. 그 결과, S의 원소는 하나 증가하며 U의 원소는 하나 감소 4. U가 공집합이 될 때까지 위 과정을 반복하며 정렬 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Ca..

[알고리즘][파이썬/Python] 선택 정렬 (Selection Sort)

정의 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식의 정렬 알고리즘 동작 방식 1. 반복 시작 시, 시작 index를 최소값의 index로 지정 2. 시작 위치 이후에 있는 모든 원소를 한 번씩 방문하며 최소값과 비교 3. 더 작은 값이 발견될 경우, 해당 값의 index를 최소값의 index로 업데이트 4. 반복이 끝난 후 시작 index와 최소값 index가 다를 경우, 두 index에 위치한 원소들을 교환 5. 위 과정을 반복하면서 정렬 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우 - 비교횟수 : 처음 비교할 때 (n-1)회, 두 번째 비교할 때 (n-2)회, ..., i..

[알고리즘][파이썬/Python] 버블 정렬 (Bubble Sort)

정의 차례로 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식의 정렬 알고리즘 동작 방식 1. 배열(혹은 리스트)의 첫 번째 원소부터 마지막 원소까지 인접 원소 간 대소 비교를 반복하는데, 더 큰 값을 가진 원소가 왼쪽에 있다면 서로 자리를 바꿈 (swap) 2. 위 과정을 반복하여 한 단계가 끝나면 가장 큰 값을 가진 원소가 배열 (혹은 리스트)의 마지막 자리로 정렬되어 있음 3. 한 단계가 끝날 때마다 맨 끝에 위치한 원소는 정렬된 상태이므로 다음 단계에서는 정렬된 원소를 제외하고 대소 비교를 실행 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우 - 비교횟수 : i번째 실행 시 (n-i) 번 비교하므로..

[알고리즘] 정렬의 정의와 분류

정렬의 정의 2개 이상의 자료를 오름차순(ascending)이나 내림차순(descending)으로 재배열하는 것 정렬 방법의 분류 1. 실행 방법에 따른 분류 (1) 비교식 정렬 (Comparative Sort) 비교하고자 하는 각 키 값들을 한 번에 두 개씩 비교하여 교환하는 방식 (2) 분산식 정렬 (Distribute Sort) 키 값을 기준으로 자료를 여러 개의 부분 집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식. ※ 여기서 키(key)란, 자료를 정렬하는 데 사용하는 기준이 되는 특정 값을 의미. 2. 정렬 장소에 따른 분류 (1) 내부 정렬 (Internal Sort) - 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식 - 정렬 속도가 빠르지만 메모리 용량의 제한을 받음..