Algorithm/Sorting Algorithm (6) 썸네일형 리스트형 합병 정렬 (Merge Sort) 합병 정렬 : 배열을 좌 우로 나눈 후, 나눈 배열을 정렬하고 다시 붙인다. 퀵 정렬(Quick Sort)과 마찬가지로 재귀 용법을 활용하는 알고리즘이다. 분할 정복 알고리즘 중 하나로, 리스트 길이가 1 이하면 이미 정렬된 것으로 본다. 분할 : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 만든다. 정복 : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합 : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이 때 정렬 결과가 임시 배열에 저장된다. 복사 : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 알게된 개념 1. 리스트 요소 끄집어내기(pop) -> pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다. >>> a = [1,2,3] .. 힙 정렬 (Heap Sort) 힙 정렬 : 힙은 완전 이진트리의 구조를 갖고 있는데, 자식 노드의 값이 부모 노드의 값보다 클 수 없다(작거나 같아야 함)는 조건을 만족해야 한다. 1. 최대 힙을 구성한다. (인덱스의 0번째 값이 최댓값이 된다) 2. 최댓값을 배열의 가장 마지막 위치에 놓는다. (큰 값을 뒤로 보내주는 과정 - 교환) 3. 그 다음 새로운 루트 노드에 대해 최대 힙을 수행한다. 4. 원소의 개수만큼 2~3번의 과정을 반복한다. 주어진 자료 구조에서 힙 성질을 만족하도록 하는 연산을 heapify라고 한다!!! heapify에서는 left = index * 2 +1, right = index * 2 + 2 공식을 만족한다. 파이썬으로 구현한 힙 정렬 def heapify(arr, index, heap_size): la.. 삽입 정렬 (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 다음
