알고리즘7 [Algorithm] 병합 정렬(Merge Sort) 정의 퀵정렬과 마찬가지로 분할 정복(Divide and Conquer)법을 사용하여 정렬하는 알고리즘 분할정복(Divice and Conquer) : 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음 결과를 모아서 다시 원래의 문제를 해결하는 방법으로 대게 순환호출을 이용하여 구현한다 분할 시 항상 균등한 크기로 분할한다는 점에서 퀵정렬과 차이가 있다 과정 배열의 길이가 1이상이면 절반으로 잘라 두 부분배열로 분할한다 각 부분배열의 원소들을 서로 비교하며 정렬한다 두 부분배열을 다시 하나의 배열로 합병한다 위 과정을 반복한다 Python 코드(오름차순) temp = [0]*10 def sort(arr, a, mid, b): global temp x = a y = mid+1 idx = a #대소관계를 .. 2021. 1. 25. [Algorithm] 퀵 정렬(Quick Sort) 정의 분할 정복(Divide and Conquer)법을 사용하여 정렬하는 대표적인 알고리즘 분할정복(Divice and Conquer) : 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음 결과를 모아서 다시 원래의 문제를 해결하는 방법으로 대게 순환호출을 이용하여 구현한다 과정(오름차순) 배열내에서 하나의 원소(피벗)을 선택한다 피벗 앞쪽에는 피벗보다 작은값이, 뒤쪽에는 큰값이 오도록 피벗을 기준으로 배열을 둘로 분할한다 분할된 배열을 대상으로 분할이 불가능할 때까지 위 과정을 반복한다 Python 코드(오름차순) Not In-Place def quick_sort(array): n = len(array) if n = end: return key = start i = start+1 j = end wh.. 2021. 1. 24. [Algorithm] 버블 정렬(Bubble Sort) 정의 서로 인접한 두 원소의 대소를 비교하여 조건에 맞지 않다면 자리를 교환(Swap)하며 정렬하는 알고리즘 ex) 오름차순 정렬일경우, 바로 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내기 과정(오름차순) 인접한 두 원소의 대소관계를 비교하여 큰값을 뒤로 보낸다 한 번 회전이 끝날때마다 탐색대상 집합기준 마지막 원소를 제외하고 위 과정을 반복한다 Python 코드(오름차순) def bubble_sort(array): n = len(array) for i in range(n): for j in range(n-i-1): if array[j] > array[j+1]: temp = array[j] array[j] = array[j+1] array[j+1] = temp return array print(b.. 2021. 1. 23. [Algorithm] 삽입 정렬(Insertion Sort) 정의 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 적절한 위치를 찾아 삽입 ex) 각 숫자를 적절한 위치에 삽입하기 과정 정렬할 원소를 기존에 정렬된 원소들 사이의 올바른 자리를 찾아 삽입한다 정렬이 안 된 원소들 중 한 원소를 대상으로 위 과정을 반복한다 Python 코드(오름차순) def insertion_sort(array): n = len(array) for i in range(1,n-1): j = i while array[j] > array[j+1]: temp = array[j] array[j] = array[j+1] array[j+1] = temp j-=1 return .. 2021. 1. 3. 이전 1 2 다음
