합병 정렬(Merge Sort)이란? 배열을 2개의 하위 배열로 재귀적으로 나눈 후, 다시 각 배열을 합치면서 정렬한다. 분할 정복 (Divide and Conquer)에 해당한다. *분할 정복이란? 문제를 작게 분할한 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘 방법 주어진 배열을 균등한 크기의 2개의 배열로 분할한다. 분할된 부분 배열을 반복해서 2개의 배열로 분할한다. 더 이상 분할할 수 없을 때, 다시 2개의 배열을 합쳐서 정렬한다. ([3], [1] -> [1, 3]) 재귀적으로 정렬된 부분 배열을 하나로 합치면서 전체가 정렬된 배열을 만든다. ([1, 3], [2, 4] -> [1, 2, 3, 4]) 파이썬으로 구현하기 def merge_sort(arr, start, ..

퀵 정렬(Quick Sort)이란? 분할 정복 (Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘 *분할 정복 이란? 문제를 작게 분할한 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘 방법 피봇(pivot)이라는 값을 하나 정한다. (임의로 정할 수 있지만, 여기서는 중간에 있는 값을 하나 정해보자.) 피봇보다 작은 값을 left 배열에, 피봇보다 큰 값을 right 배열에 추가한다. left(피봇보다 작은 값들), 피봇, right(피봇보다 큰 값들) 로 만들어진다. left, right 배열에 대해 위 작업을 재귀적으로 반복한다. 파이썬으로 구현하기 방법1 pivot 보다 작은 값을 왼쪽 배열에, 큰 값을 오른쪽 배열에 추가한다. 각 배열에 대해 ..

버블 정렬이란? 인접한 두 원소를 비교하며 정렬하는 알고리즘 방법 arr = [1,6,4,2,3,5] 1) arr[0]와 arr[1] 를 비교하여 큰 원소를 오른쪽에 위치시킨다. 2) 1번과 동일하게 arr[1]과 arr[2], arr[2]과 arr[3], ... , arr[n-2]과 arr[n-1]를 비교하여 정렬한다. 3) 모두 수행하고 나면 arr[n-1] 위치에는 가장 큰 원소가 위치하게 된다. (이제 arr[n-1]은 비교할 필요가 없다.) 4) arr[n-1]를 제외한 리스트에서 1~2의 작업을 수행한다. 5) 확인해야 하는 원소를 하나씩 줄여나가면서 위 작업을 총 n번 수행한다. 파이썬으로 구현하기 def bubble_sort(arr): n = len(arr) for i in range(..

삽입 정렬 (Insertion Sort) 란? 손 안의 카드를 정렬하는 방법과 유사하다. 2번째 원소부터 시작하여 그 앞(왼쪽) 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 과정 (오름차순) 1. 정렬은 2번째 위치의 값을 temp에 저장한다. 2. temp와 이전에 있는 원소들과 비교하여 이전 값이 더 큰 경우 이전 값을 오른쪽으로 한 칸씩 이동하다가 그렇지 않은 경우 temp를 삽입한다. 3. 1번으로 돌아가 다음 위치의 값을 temp에 저장하고 반복한다. Python Code def insertion_sort(arr): n = len(arr) for i in range(1, n): temp = arr[i] prev = i-1 ..

선택 정렬 (Selection Sort) 란? 해당 순서에 원소를 넣을 위치는 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘. 해당 자리를 선택하고 그 자리에 오는 값을 찾는 방법이다. 과정 (오름차순) 1. 주어진 배열 중에서 최솟값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교환한다. 3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교환한다. 이를 반복한다. Python Code def selection_sort(arr): n = len(arr) index_min = 0 for i in range(n): index_min = i for j in range(i+1, n): # 최소 값의 위치를 찾는다. if arr[j] < arr[index_min]: index_min = j temp =..

버블 정렬 (Bubble Sort) 란? 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 과정 (오름차순의 경우) n : 원소의 개수 1. 1회전에서는, 1번째 원소와 2번째 원소를, 2번째 원소와 3번째 원소를, 3번째 원소와 4번째 원소를 ,... 와 같은 형태로 (n-1)번째 원소와 (n)번째 원소를 비교하여 앞의 원소의 값이 더 크다면, 서로 교환한다. 2. 1회전을 수행하고 나면 가장 큰 원소가 (n)번째 위치로 이동하게 된다. 2회전에서는 (n)번째 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 (n-1)번째 원소가 배열에서 2번째로 큰 원소가 된다. 이런 방법으로 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. Pyt..