Theory/Algorithms (35) 썸네일형 리스트형 삽입 정렬 (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 2 3 4 5 다음
