Algorithm (12) 썸네일형 리스트형 삽입 정렬 (Insertion Sort) 삽입 정렬 : 앞에서부터 차례차례 비교해나가면서 자신의 위치를 찾아 삽입하는 것을 의미한다. i for문에서는 0번째 인덱스부터 차례차례 뒤로 가야하기 때문에 인덱스값이 증가하고, 반대로 j for문에서는 현재 선택한 데이터를 배열 속에서 역방향으로 비교해나간다. 만약, 이전 값이 현재 선택한 데이터보다 큰 경우 두 값의 위치를 바꿔주는 과정을 반복한다. 파이썬으로 구현한 삽입정렬 from random import randint def insertion_sort(arr): for i in range(n-1): for j in range(i, 0, -1): if arr[j-1] > arr[j]: arr[j], arr[j-1] = arr[j-1], arr[j] return arr arr = [randint(.. 퀵 정렬 (Quick Sort) 퀵 정렬 : 특정 키 값(pivot)을 중심으로 좌측은 pivot보다 작은 수, 우측은 pivot보다 큰 수가 오도록 서로 교환하는 과정을 의미한다. 왼->오 pivot 보다 큰 값을 찾는 A와 오->왼 pivot 보다 작은 값을 찾는 B로 나누어서 A와 B의 위치를 바꾸는 과정을 계속 반복한다. 이처럼 2개의 서브 리스트가 구성되면 첫 번째 리스트부터 앞의 과정을 반복하는 것이다. 문제를 여러개로 분리해서 수행한 후, 그 해결 결과 값들을 합쳐서 원래의 문제를 해결하는 분할 정복 방식을 따르고 있다. "분할 정복 기법 + 재귀 알고리즘 = 퀵 정렬 알고리즘" 파이썬으로 구현한 퀵 정렬 from random import randint def quick_sort(arr): if len(arr) pivot:.. 선택 정렬 (Selection Sort) 선택 정렬 : 가장 작은 값을 맨 앞으로 이동한 후, 교환하는 방식으로 진행한다. 버블 정렬에서는 인덱스를 이동하면서 지속적으로 교환을 했다면 선택 정렬에서는 가장 작은 데이터를 찾아 한 번만 교환한다. 기준 인덱스가 계속 바뀐다는 점을 알고 있을 것! "최솟값이 저장된 인덱스를 갱신하는 것" 파이썬으로 구현한 선택정렬 from random import randint def selection_sort(arr): for i in range(n-1): minIndex = i for j in range(i+1, n): if arr[minIndex] > arr[j]: minIndex = j # 최저값의 인덱스 저장 arr[i], arr[minIndex] = arr[minIndex], arr[i] # 찾아낸 최솟.. 버블 정렬 (Bubble Sort) 버블 정렬 : 인접한 2개의 데이터를 비교하여 크면 교환하는 과정을 반복하여, 큰 값을 끝 부분에 위치시킨다. 알게된 개념 -> 처음 버블 정렬 코드를 접할 때, C언어로 공부했었는데 'swap' 개념에 대해서 잘 몰랐어서 공부했다! "두 변수의 값을 서로 바꾸기" C언어에서는 두 변수의 값을 서로 바꾸려면 변수가 하나 더 필요하다. 변수에 어떤 값이 대입되면 자신이 가지고 있던 값이 사라지고 새로 대입된 값이 저장되기 때문에 기존에 변수가 가지고 있던 값을 보관하고 싶다면 temp 변수를 하나 더 선언하고 그 변수에 값을 저장해야 한다. 파이썬으로 버블정렬 구현하기 from random import randint def bubble_sort(arr): for i in range(n-1): for j i.. 이전 1 2 다음
