본문 바로가기

Theory

(53)

계수 정렬 (Counting Sort) 계수 정렬은 이름 그대로 배열의 원소를 각각 셈으로써 정렬하는 방식입니다. 데이터의 크기가 제한되어 있고 중복된 데이터가 많을 때 효과적인데요. 배열 [2,4,0,6,1,2,8,4,9] 예를 들어 한 번 살펴보겠습니다. EXAMPLE 계수정렬은 먼저 배열의 가장 작은 값과 큰 값이 모두 담길 수 있는 리스트를 생성합니다. 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 생성한 리스트에 데이터의 값과 동일한 인덱스의 값을 증가시킵니다. 0 1 2 3 4 5 6 7 8 9 1 1 2 0 2 0 1 0 1 1 그 다음에는 리스트의 첫 번째 데이터부터 하나씩 출력합니다. 파이썬 코드 def counting_sort(array): count = [0] * (max(array) - min(a..

퀵 정렬 (Quick Sort) 퀵 정렬은 토니 호어 (Tony Hoare) 가 1959년에 고안한 알고리즘으로 피벗 (pivot) 을 기준으로 좌우를 나누는 특징으로 인해 파티션 교환 정렬 (Partition-Exchange Sort)라고도 불립니다. 퀵정렬은 피벗을 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 계속 나누어 분할해가며 정렬하는데요, 빠르고 효율적으로 최선의 경우 $O(n\log n)$의 시간 복잡도를 가집니다. 그렇다면 맨 처음 단계에서 피벗을 어떻게 설정해야 할까요? 여러 인덱스가 피벗이 될 수 있지만 일반적으로 맨 왼쪽 혹은 맨 오른쪽 인덱스를 피벗으로 설정하게 됩니다. 배열 [2,8,7,1,3,5,6,4]에 대해 왼쪽, 오른쪽 피벗을 살펴보도록 하죠. 왼쪽 피벗 왼쪽 피벗의 경우 left 포인트, right..

삽입 정렬 (Insertion Sort) 삽입 정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 원소들과 비교하여 자신의 위치를 찾아가는 정렬방법입니다. for 문을 통해 배열의 원소를 순회하면서 해당 인덱스의 원소가 찾아갈 위치를 앞부분의 어디에 삽입할 것인가를 찾는 알고리즘인데요, 특이하게도 삽입 정렬은 배열의 두 번째 인덱스부터 루프를 시작합니다. 배열 [8,5,6,2,4] 예를 들어 살펴볼까요? Example 1. 첫 번째 스텝입니다. 두 번째 인덱스인 5부터 for 루프를 시작합니다. 두 번째 인덱스 기준에서는 앞선 인덱스가 첫 번째 인덱스밖에 없으니 첫 번째 원소인 8과 비교를 하고 8이 5보다 크니 둘의 위치를 바꿔줍니다. 2. 두 번째 스텝입니다. 세 번째 인덱스인 6을 기준으로 앞서 첫 번째 스텝에서 정렬되었던 배열에 ..

버블 정렬 (Bubble Sort) 버블 정렬은 정렬 알고리즘 중 가장 비효율적인 알고리즘입니다. 2008년 버락 오바마가 대통령 후보시 접견한 구글 CEO 에릭 슈미트가 "32비트 정수 100만 개를 정렬하는 가장 효율적인 방법은 무엇인가요?"라고 물었을 때, 변호사 출신인 오바마가 이런 대답을 했다고 합니다. "버블정렬은 잘못된 시작일 것 같습니다". 법학을 전공한 오바마조차 이런 말을 한 것은 다음 코드를 보면 매우 자명합니다. 파이썬 코드 from typing import List def bubble_sort(List: array) -> List: for i in range(1, len(array)): for j in range(0, len(array)-1): if array[j] > array[j+1]: array[j], arra..

선택 정렬 (Selection Sort) 선택 정렬은 추가 메모리를 요구하지 않는 제자리 정렬 (in-place sort) 방법 중 하나로 해당 배열의 각 인덱스에 어떤 원소를 넣을지 선택하는 방법입니다. 예를 들어 살펴보기 전에 정렬은 기본적으로 오름차순 정렬을 기본으로 가정합니다. 숫자가 제일 작은 원소가 맨 앞에 오고 제일 큰 원소가 맨 뒤에 가는 식이죠. 내림차순도 가능하고 오름차순의 반대 방향으로 하기 때문에 정렬 원리만 알면 가능합니다. 한 번 배열 [9,6,7,3,5] 예를 들어 살펴볼까요 ? EXAMPLE 첫 번째 인덱스 (현재는 9) 에 넣을 원소를 선택합니다. 이 때, 두 번째 인덱스부터 마지막 인덱스까지 값을 비교해서 가장 작은 값 (3)을 선택하고 첫 번째 인덱스에 넣습니다. 두 번째 인덱스에 넣을 원소를 선택합니다. 이 ..

이전 1 ··· 4 5 6 7 다음

티스토리툴바